I have a list of substitutions like the following:

g = {"A" -> "J", "B" -> "P", "D" -> "N", "E" -> "L", "F" -> "Z", "G" -> "V", "H" -> "U", "I" -> "X", "K" -> "Q", "M" -> "G", "N" -> "M", "O" -> "T", "R" -> "I", "T" -> "H", "V" -> "Y", "W" -> "B", "Y" -> "F"}

Looking at the list you can see various letter "chains". For example, starting with O, there is a chain of letters {O,T,H,U}. (it's not a cycle, because the list contains no substitute for U). I want to find all such chains.

Using Graph as below gives me a figure that contains what I'm looking for, but the result I'm looking for is the following list of lists: {{D,N,M,G,V,Y,F,Z}, {O,T,H,U}, {W,B,P},{R,I,X}, {A,J}, {E,L}, {K,Q}}.

It seems like ConnectedComponents[graphForm] should work, but that gives {{J},{A},{P},{B},{Z},{F},{Y},{V},{G},{M},{N},{D},{L},{E},{U},{H},{X},{I},{Q},{K},{T},{O},{R},{W}}.

I feel like there must be something among the Graph functions that will work, but I haven't found it. Any ideas on how to do this would be very much appreciated.

Here is what I'm doing:

graphForm = 
 Graph[g, VertexLabels -> Placed[Automatic, Center], VertexSize -> .7]

This gives the following figure:

enter image description here


2 Answers 2


{{"F", "Y", "Z", "V", "G", "M", "N", "D"}, {"T", "O", "H", "U"}, {"I", "R", "X"}, {"W", "B", "P"}, {"K", "Q"}, {"A", "J"}, {"E", "L"}}

If you want to have ordered list by direction:

FindHamiltonianPath /@ WeaklyConnectedGraphComponents[g]

{{"D", "N", "M", "G", "V", "Y", "F", "Z"}, {"O", "T", "H", "U"}, {"R", "I", "X"}, {"W", "B", "P"}, {"K", "Q"}, {"A", "J"}, {"E", "L"}}


Documentation says: "For a directed graph, the vertices u and v are in the same component if there is a directed path from u to v and from v to u", so if we make our graph to be undirected at first, this will work:g = Graph@{"A" -> "J", "B" -> "P", "D" -> "N", "E" -> "L", "F" -> "Z", "G" -> "V", "H" -> "U", "I" -> "X", "K" -> "Q", "M" -> "G", "N" -> "M", "O" -> "T", "R" -> "I", "T" -> "H", "V" -> "Y", "W" -> "B", "Y" -> "F"} ConnectedComponents@UndirectedGraph@g

  • 1
    $\begingroup$ Thank you Vital, but this doesn't quite do what I want. When I apply that function to my graph I get {{H,I,T,R,O,Q},{E,S,U,L,X},{A,M,N,Z},{Y,B},{G,J},{D,F}}. The first list is correct, but the second has E going to S, which is backwards. $\endgroup$
    – JAS
    Commented Sep 2, 2022 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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