# Connected Components of Directed Graph

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:

WeaklyConnectedComponents[Graph[g]]


{{"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

• 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.
– JAS
Commented Sep 2, 2022 at 16:59