1
$\begingroup$

Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.

$\endgroup$
3
$\begingroup$

For ease of writing, I'm going to say "component" instead of "strongly connected component." This should cause no confusion, since it's the only kind of component we're interested in.

Let $G$ be your directed graph. Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$. Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.

Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink. So, we need to find the longest paths in $H$. We can't just produce a list of them because there might be exponentially many. So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.

  • Topologically sort the vertices.
  • Set $\ell(x) = 0$ for each sink $x$.
  • Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\,\{\ell(y_1), \dots, \ell(y_k)\}$ for each vertex $x$ with out-neighbours $y_1, \dots, y_k$.

Note that the topological ordering guarantees that we've already computed $\ell(y_i)$ for each out-neighbour $y_i$. When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.

Now, produce a graph $H'$ from $H$ as follows.

  • Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
  • Let $m = \max\,\{\ell(x)\mid x\text{ is a source in }H\}$ (this is the length of the longest path in $H$).
  • Iteratively delete every source $y$ with $\ell(y)<m$.

$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$). In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.

Now, produce a graph $G'$ from $G$ as follows.

  • Delete from $G$ any component $C$ such that $h(C)\notin H'$.
  • Delete from $G$ any edge from component $C_1$ to component $C_2$ if there is no edge $(h(C_1),h(C_2))$ in $H'$.

Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$. The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.

Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.

$\endgroup$
  • $\begingroup$ L(x) != L(y+1) or L(x) != L(y)+1? Also in the labeling what should we do when a node is not a sink and none of its out neighbors has a label. $\endgroup$ – sudomakeinstall2 Nov 14 '15 at 14:35
  • $\begingroup$ $\ell(x)\neq \ell(y)+1$: thanks for spotting the typo. I've clarified the labelling: if you can't label a vertex at this iteration, leave it until later. You'll always be able to find at least one vertex where all out-neighbours are already labelled, so something will get labelled at each iteration. $\endgroup$ – David Richerby Nov 14 '15 at 14:49
  • 1
    $\begingroup$ Well, given that $H$ is a DAG you can topologically sort it and follow the topological order to label the nodes in linear time instead of having to do many iterations over the graph. $\endgroup$ – Bakuriu Nov 14 '15 at 17:03
  • $\begingroup$ @Bakuriu Could you explain how a topological sort helps? I'm not seeing it. $\endgroup$ – David Richerby Nov 14 '15 at 17:10
  • $\begingroup$ If you follow the topological ordering you always know the values $\ell(y_i)$ assigned to the out-neighbours because you have already labelled them by construction. $\endgroup$ – Bakuriu Nov 14 '15 at 17:13

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.