- #1
mXSCNT
- 315
- 1
Suppose you have a directed acyclic graph (a DAG) G. A total order for G is a list of the nodes in G, such that if there is a path from node A to node B, then A appears before B in the total order.
Define (I don't know if there's already a standard term for this) two nodes V and W to be "apart" if there is no directed path from V to W, and no directed path from W to V.
Define G as "flippable" if there exist two total orders of G, O1 and O2, such that if a node V is apart from a node W, then the order of V and W is switched between O1 and O2 (either V appears before W in O1 and after W in O2, or W appears before V in O1 and after V in O2).
The advantage of this is that if G is flippable, you can tell in constant time whether there is a path from node V to node W, by looking to see whether their order in O1 and O2 is switched.
Most DAGs you draw by by hand seem to be flippable, even somewhat complicated ones. Here's an example of a simple, flippable DAG. (represented by the paths the DAG contains):
a -> c -> f
b -> d -> f
b -> c -> e
O1 = abcedf
O2 = bdacfe
You can verify that O1 and O2 work by listing which nodes are apart from which nodes, and checking their order is switched:
a: b and d
b: a
c: d
d: a, c, and e
e: d and f
f: e
To construct O2 (if you have a valid O1), you just start at the end of O1, and work backwards inserting nodes into O2. Insert each node as far forward into O2 as you can, without inserting it after any of its children. Using the previous example:
O1 = abcedf
Building O2, showing the steps:
f
df
dfe
dcfe
bdcfe
O2 = bdacfe
After quite some time I realized what rule to follow when you are trying to construct O1. If A is apart from B and C, and there is an edge B -> C, and B has already been added to O1, then you can't add A to O1 until C has been added first. It's not hard to realize why this is true, especially after trying a few examples.
It didn't take me that long after realizing that rule to find an example of a non-flippable DAG (I spent some time hoping to find an algorithm to always find O1 and O2 for a DAG - my quest was in vain!) Here is the non-flippable DAG:
A -> D
B -> D
B -> E
C -> E
C -> F
A -> F
The graph is symmetric so I'll start by putting any root node into O1. Let's choose B.
O1=B
From here we have to choose A or C. But if we choose A, we run afoul of our rule, because B and E are apart from A, and B is in O1 but E is not, and B -> E is an edge. If we choose C, the problem is that B and D are apart from C, and B is in O1 but D is not, and B -> D is an edge. Thus, the graph is not flippable.
Certain graphs are flipabble, but tricky, involving dead ends. For example:
A -> C
B -> D -> C
B -> E
Suppose we start with B. Our rule doesn't immediately rule out choosing D or E next, so we might choose D. But now, we can't choose A because of B -> E, and we can't choose E because of D -> C! The problem can be solved by chosing E instead, to get O1=BEDAC. (And O2=ABDCE).
So - what now?
Well, how can we characterize which graphs are flippable? Is there a simple algorithm?
Suppose we define a DAG to be "3-flippable" (or generally "N-flippable") if there are N total orders O1, O2, ..., ON such that if a node A is apart from B, then A appears before B in at least one total order, and A appears after B in at least one other total order. This is almost as good for the original purpose, because that still let's us decide whether there is a path from A to B in a small number of computational steps.
There's definitely some N for which any DAG is N-flippable, since for any two nodes A and B that are apart it is easy to construct a total order where A appears before or after B, if we don't care about the order of the nodes. But we still have the question, what is the minimum N for which a particular DAG is N-flippable? And how can we generate O1, O2, ..., ON?
Also, is the minimum N for which a particular DAG is N-flippable bounded by a constant, or are there DAGs that aren't M-flippable but are M+1-flippable for any M? What's N for the "zigzag" graph
1 -> 2
3 -> 2
3 -> 4
5 -> 4
5 -> 6
7 -> 6
7 -> 8
...
2n+1 -> 2n
2n+1 -> 2n+2
1 -> 2n+2
?
Define (I don't know if there's already a standard term for this) two nodes V and W to be "apart" if there is no directed path from V to W, and no directed path from W to V.
Define G as "flippable" if there exist two total orders of G, O1 and O2, such that if a node V is apart from a node W, then the order of V and W is switched between O1 and O2 (either V appears before W in O1 and after W in O2, or W appears before V in O1 and after V in O2).
The advantage of this is that if G is flippable, you can tell in constant time whether there is a path from node V to node W, by looking to see whether their order in O1 and O2 is switched.
Most DAGs you draw by by hand seem to be flippable, even somewhat complicated ones. Here's an example of a simple, flippable DAG. (represented by the paths the DAG contains):
a -> c -> f
b -> d -> f
b -> c -> e
O1 = abcedf
O2 = bdacfe
You can verify that O1 and O2 work by listing which nodes are apart from which nodes, and checking their order is switched:
a: b and d
b: a
c: d
d: a, c, and e
e: d and f
f: e
To construct O2 (if you have a valid O1), you just start at the end of O1, and work backwards inserting nodes into O2. Insert each node as far forward into O2 as you can, without inserting it after any of its children. Using the previous example:
O1 = abcedf
Building O2, showing the steps:
f
df
dfe
dcfe
bdcfe
O2 = bdacfe
After quite some time I realized what rule to follow when you are trying to construct O1. If A is apart from B and C, and there is an edge B -> C, and B has already been added to O1, then you can't add A to O1 until C has been added first. It's not hard to realize why this is true, especially after trying a few examples.
It didn't take me that long after realizing that rule to find an example of a non-flippable DAG (I spent some time hoping to find an algorithm to always find O1 and O2 for a DAG - my quest was in vain!) Here is the non-flippable DAG:
A -> D
B -> D
B -> E
C -> E
C -> F
A -> F
The graph is symmetric so I'll start by putting any root node into O1. Let's choose B.
O1=B
From here we have to choose A or C. But if we choose A, we run afoul of our rule, because B and E are apart from A, and B is in O1 but E is not, and B -> E is an edge. If we choose C, the problem is that B and D are apart from C, and B is in O1 but D is not, and B -> D is an edge. Thus, the graph is not flippable.
Certain graphs are flipabble, but tricky, involving dead ends. For example:
A -> C
B -> D -> C
B -> E
Suppose we start with B. Our rule doesn't immediately rule out choosing D or E next, so we might choose D. But now, we can't choose A because of B -> E, and we can't choose E because of D -> C! The problem can be solved by chosing E instead, to get O1=BEDAC. (And O2=ABDCE).
So - what now?
Well, how can we characterize which graphs are flippable? Is there a simple algorithm?
Suppose we define a DAG to be "3-flippable" (or generally "N-flippable") if there are N total orders O1, O2, ..., ON such that if a node A is apart from B, then A appears before B in at least one total order, and A appears after B in at least one other total order. This is almost as good for the original purpose, because that still let's us decide whether there is a path from A to B in a small number of computational steps.
There's definitely some N for which any DAG is N-flippable, since for any two nodes A and B that are apart it is easy to construct a total order where A appears before or after B, if we don't care about the order of the nodes. But we still have the question, what is the minimum N for which a particular DAG is N-flippable? And how can we generate O1, O2, ..., ON?
Also, is the minimum N for which a particular DAG is N-flippable bounded by a constant, or are there DAGs that aren't M-flippable but are M+1-flippable for any M? What's N for the "zigzag" graph
1 -> 2
3 -> 2
3 -> 4
5 -> 4
5 -> 6
7 -> 6
7 -> 8
...
2n+1 -> 2n
2n+1 -> 2n+2
1 -> 2n+2
?