6
$\begingroup$

So I have a directed graph that looks something like:

graph

I'm trying to make an algorithm that can go through all the vertices and tell me whether we have any path from an upper case letter to its lowercase version, or a path from a lowercase letter to its upper case version. In the above example, we have a path from C to c. We also have a path from B to b, from a to A, from E to e, and from G to g. I'd like the algorithm to find at least one of these paths.

The algorithm can stop looking if it just finds one such case where this happens. Each vertex points to at most one different vertex, so the out-degree of every vertex is either zero or one. I'm trying to get this done efficiently (linear time) and can put whatever extra information in the vertices to do it. I've been attempting to use the DFS algorithm to do it because you can work with ancestry but I'm not sure if it works for specific vertex relationships efficiently.

I'm aware that DFS can use discovery time and finish time to find if a vertex is the ancestor of another, and that this is used for cycle detection. I'm basically wondering if there is an efficient way to check if a specific node (that isn't necessarily part of a cycle) is the ancestor of another specific node. Unless, of course, this is unnecessary and there is a better way to go about it.

$\endgroup$
  • $\begingroup$ If the number of vertices is small, then practically speaking you can use DFS to calculate, for each vertex, which letters reach it. This uses a short bit-vector. As a general solution this is only quadratic in the number of vertices, though. $\endgroup$ – Yuval Filmus Jul 31 '16 at 19:25
  • $\begingroup$ Merged the accounts together so I can edit/comment. I've clarified the wording so that it's consistent with the example given (lower case to its upper case version or vice-versa, not lower-case to any upper-case and vice-versa). $\endgroup$ – barb Jul 31 '16 at 19:48
  • $\begingroup$ Could you also insert info about how you store vertices and how the graph is created (you have static one, dynamically added?). The rest is clear now. $\endgroup$ – Evil Jul 31 '16 at 22:02
  • $\begingroup$ @YuvalFilmus, Re-opened now! Thanks for pinging me. I read through the question, and it previously wasn't clear to me whether it was talking about edges or paths. The edit helped, and I edited it further based on the comments. Hopefully it's now clear and ready to get some good answers! $\endgroup$ – D.W. Jul 31 '16 at 22:09
  • 1
    $\begingroup$ @Evil So, lets say the graph is created from a sequence of statements that represent one vertex pointing to another. So for the above example: a->c, A->b, b->g, B->c, c->D, C->B, d->b, D->g, E->f, F->e, F->A, g->A, G->D I can turn this into a graph and add whatever additional information I like to each vertex or edge. This will likely be stored as an adjacency list because I aim to get the algorithm running in linear time with respect to vertices and edges. $\endgroup$ – barb Aug 1 '16 at 0:15
1
$\begingroup$

Observation: Each weakly connected component can contain at most 1 cycle, and every vertex in such a cycle is reachable from every vertex in the weakly connected component. That's because every vertex that participates in a cycle exhausts its single out-edge by connecting to the next vertex in the cycle, so the only other edges that can be incident on any vertex in this cycle must be in-edges from other vertices.

In more detail: Suppose to the contrary that a single component contains 2 cycles: Then either they are vertex-disjoint or not. In the former case, there must be an undirected path of edges (i.e., a path in the graph where edge orientation has been forgotten) connecting the two cycles. But the first and last edges in this undirected path must be "outwards" (i.e., the first must be an in-edge to the first cycle, and the last must be an in-edge to the second cycle), implying that some vertex on the path must have 2 out-edges, so this case cannot happen. In the latter case, let the two cycles be $C_1$ and $C_2$, and w.l.o.g. suppose $|C_1| \geq |C_2|$. Let $uv$ be an edge in $C_1$ such that $u \in C_1 \cap C_2$ but $v \notin C_2$. (Such an edge must exist if $C_1 \neq C_2$.) Then $u$ must have a successor $w \neq v$ in $C_2$; but this immediately implies that $u$ has outdegree at least 2, so this cannot happen either.

Algorithm phase 1: Detecting a cycle

So, starting at any vertex and successively traversing the single out-edge can only give one of two possible outcomes:

  1. We reach a vertex with no out-edge. In this case, the component has no cycle.
  2. We reach a vertex we have seen before. In this case, the component has a single cycle consisting of all vertices visited since the last time the final vertex was visited. In a $k$-vertex component, the cycle vertices can be identified in $O(k)$ time by numbering the vertices in visitation order and gathering them together in a subsequent pass.

To simplify notation I'll label the vertices with positive and negative integers, instead of upper- and lower-case letters. We will maintain a counter $c_i$ for each pair of vertices $i, -i$: at the end of the algorithm, $c_i = 2$ if and only if at least one of the vertices $i$ and $-i$ can reach the other by some path.

If a cycle was detected, we can start at any vertex in the cycle and continue following out-edges until we hit the first vertex again, incrementing $c_{|i|}$ for each vertex $i$ encountered. Also, we (at least conceptually) create a new vertex $x$ to represent "the cycle", and as we proceed through each vertex $v$ in the cycle, we change every non-cycle edge $uv$ to $ux$. (Conceptually) delete the cycle vertices, and set $z = x$.

If no cycle was detected, set $z$ to the last vertex we found, say $i$, which by construction has no out-edge. Increment $c_i$.

Observe that since any cycle has been deleted, the component is now a tree with all edges directed toward $z$.

Algorithm phase 2: Reverse DFS

We now perform a DFS starting at $z$ and proceeding "against" the direction of each edge. During this traversal:

  • Upon entering a vertex $i$: If $c_{|i|} < 2$, then increment it.
  • Upon leaving a vertex $i$: If $c_{|i|} = 1$, then decrement it.

This asymmetric increment/decrement scheme ensures that, whenever we discover a path from the root $z$ that contains both vertices in a pair, the discovery (which is recorded as a count of 2) "sticks", while OTOH whenever we discover that no path from the root $z$ through some vertex $i$ also contains $-i$, the discovery of $i$ is "forgotten" -- this has the important effect of not recording as matched any pair $i, -i$ that occur in the same component but such that neither is the ancestor of the other.

The above can all be implemented to take linear time in the number of edges within a component, so the overall time to process the graph is $O(|V|+|E|)$.

$\endgroup$
  • $\begingroup$ @D.W.: I mean a "weakly" connected component. That is, my claim at the top is that every such "weakly" connected component contains at most one cycle (and thus, as it happens, at most one nontrivial (2-or-more-vertex-containing) strongly connected component). $\endgroup$ – j_random_hacker Sep 30 '16 at 17:01
0
$\begingroup$

I would begin with a simple insight: Why plain dfs fail to solve this problem?, if you want to find a path from $A$ to $a$ then the dfs might fail because a node that belongs to the $A \to a$ path its already visited in the dfs search.

Then if we are looking for a path from $A$ to $a$ the problem we need to solve is that if we found a node $x$ that is already visited, how to know if $x$ actually leads to $a$ in a path we have explore before in the dfs search?

A DFS search forms DFS Spanning trees, roughly they are the trees that are formed as we tranverse the graph until we have no more options, it is at tree because we are marking nodes as visited so there are no cycles. It is important to understand that there may be more than one DFS spanning tree because is possible that certains node may not be reachable from all the nodes (taking a look at dfs spanning tree definitions will make clearer that point). Following that fact, we can say that every node will belong to exactly one DFS Spanning tree, so if we store all the DFS Spanning trees it will be linear in space, and transversing all will be linear in time (more on that next).

What we have so far is that we need to check if from $b$ we reach $a$, the way we do it is by looking at the DFS Spanning tree of $b$!, its trivial to see that the DFS Spanning tree where $b$ belongs its already computed at that moment because $b$ is already visited :) the trick is that we need to somehow store it as the dfs search is performed (its more a implementation detail).

We are almost there!, all reduces to this: how do we check that $a$ is a descendant of $b$ in its DFS Spanning tree?, well its trivial to do it in linear time but that would turn our algorithm quadratic (and the whole point of this question is to solve it in linear time), we can use the LCA (lowest common ancestor), if the LCA of $b$ and $a$ is $b$ then for sure $a$ is a descendant of $b$ in the tree!, compute LCA for two given nodes its linear but shockingly we can do it in log time and in constant time as well!, that is not a trivial task but is completely possible. Check this.

Another thing to keep in mind is that cycles are almost a problem in every stratagy, so you may consider to avoid them by computing strongly connected components first in linear time and then clustering the nodes in a single node.

$\endgroup$
  • $\begingroup$ I've edited the answer with a whole different approach. $\endgroup$ – bones.felipe Aug 1 '16 at 3:25
  • $\begingroup$ Your claim that every node belongs to a single DFS tree is baffling. $\endgroup$ – Yuval Filmus Aug 1 '16 at 6:04
  • $\begingroup$ Why?, if a node is visted only once it will only belong to a dfs tree. $\endgroup$ – bones.felipe Aug 1 '16 at 14:55
  • $\begingroup$ There are many possible DFS spanning trees. I'm assuming you take only one per connected component, and then the total size is indeed linear. It might be simpler to just assume that the graph is connected, since different connected components can be handled separately. $\endgroup$ – Yuval Filmus Aug 1 '16 at 14:58
  • $\begingroup$ Perhaps you should write a pseudocode of your algorithm, rather than a list of "hints". $\endgroup$ – Yuval Filmus Aug 1 '16 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.