Topological sort question
Hi, everyone. Here is an introduction of topological sort program,
I'm wondering whether this "layer" is just an alias to the well known "vertex" or "node", or there are other more profound meanings ?
I also have a preliminary idea, but not sure whether it is feasible.
1. First, use an array to store all the integer layers in order
2. For every constraint, adjust the mentioned elements's index if necessary.
(e.g the original sequence is 1 2 3 4 5, when encountering 1 > 3, which is false for now, swap 1 & 3. Resulting in 3 2 1 4 5, and so on.)
3. After processing all the constraints, show the result.
However, this idea seems not using the concept of Topology.
Thx for your help in advance !
| There's an input file indicating the layer constraints in the following format: 5 1 2 3 4 5 3 1 > 3 5 > 2 3 > 4 Which means there are five layers, with indexes 1, 2, 3, 4, and 5, respectively. Also, there are three constraints, indicating “the first layer should be above the third layer”, “the fifth layer should be above the second layer”, and “the third layer should be above the fourth layer”. Then, you have to output the sequence 4 3 1 2 5 that can satisfy the constraints. Note that the sequence is not unique. There could be many correct sequences. You just need to output one of them. |
I'm wondering whether this "layer" is just an alias to the well known "vertex" or "node", or there are other more profound meanings ?
I also have a preliminary idea, but not sure whether it is feasible.
1. First, use an array to store all the integer layers in order
2. For every constraint, adjust the mentioned elements's index if necessary.
(e.g the original sequence is 1 2 3 4 5, when encountering 1 > 3, which is false for now, swap 1 & 3. Resulting in 3 2 1 4 5, and so on.)
3. After processing all the constraints, show the result.
However, this idea seems not using the concept of Topology.
Thx for your help in advance !
Last edited on
Layer has no meaning at all, well none which specifically implies say vertex.
The question could have said plates, tiles, cards, or any number of other objects that could be equally arranged into a 'below' and 'above' sequence.
Your idea looks feasible.
The question could have said plates, tiles, cards, or any number of other objects that could be equally arranged into a 'below' and 'above' sequence.
Your idea looks feasible.
initial sequence: 1 2 3 4 5
Let us say, we have two constraints, a and b.
a. 3 > 4, swap 3 and 4, to get 1 2 4 3 5
b. 1 > 3, swap 1 and 3, to get 3 2 4 1 5, but this violates constraint a.
Let us say, we have two constraints, a and b.
a. 3 > 4, swap 3 and 4, to get 1 2 4 3 5
b. 1 > 3, swap 1 and 3, to get 3 2 4 1 5, but this violates constraint a.
you have to build it from the rules, and back-fill it? Or that may be one way?
*1*3*4* pattern is required for the above, anything else is filler.
eg 51234 is ok, I believe?
or for the orig example
*1*3*4*5*2* //one of several
*1*3*4* pattern is required for the above, anything else is filler.
eg 51234 is ok, I believe?
or for the orig example
*1*3*4*5*2* //one of several
Last edited on
If I understand the problem, it seems like the example output fails the third constraint, so is not a valid answer. Am I missing something?
4 < 3 < 1; 2 < 5
alll constraints are respected
> However, this idea seems not using the concept of Topology.
each layer is a node
each constraint is an edge
your task is to traverse the directed acyclic graph(s)
alll constraints are respected
> However, this idea seems not using the concept of Topology.
each layer is a node
each constraint is an edge
your task is to traverse the directed acyclic graph(s)
| 4 < 3 < 1; 2 < 5 alll constraints are respected |
OK. I think I get it now. I totally misunderstood the premise.
I thought the constraints referred to the indexes (base-1) of the output list such that output[1] > output[3], etc.
I will go back to lurking now.
Topic archived. No new replies allowed.