1
$\begingroup$

The code below computes the connected components of the undirected graph and sorts them according to the directed graph. It is possible since by (the real) definition of edges, the subgraph generated by any connected component will always be a path graph. Or said differently, the undirected graph is a disjoint union of path graphs.

edges = Uncompress[FromCharacterCode[
Flatten[ImageData[Import["http://i.stack.imgur.com/ujaNL.png"],"Byte"]]]]

sortedComps = With[{dirGraph = DirectedEdge @@@ edges,
 comps = ConnectedComponents[UndirectedEdge @@@ edges]},
      FindHamiltonianPath[Subgraph[dirGraph, #]] & /@ comps];

The evaluation is horribly slow. How to compute sortedComps more efficiently?

$\endgroup$
4
$\begingroup$

I think this is what you after, if no, you can tell me

TopologicalSort /@ WeaklyConnectedGraphComponents[DirectedEdge @@@ edges]
| improve this answer | |
$\endgroup$

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.