Message Boards Message Boards

Subpaths in a Graph

Posted 9 years ago

Let L be a list of pairs -- e.g., L = { {1,2}, {3,4}, {2,1}, {4,5}, {9,10}, {5,8} } -- where pair {t,h} denotes the directed arc from node t to h. Let G be the digraph determined by these arcs.

I want the "disconnected components" of G but want the nodes in G-order. Neither ConnectedComponents(G) nor WeaklyConnectedComponents(G) yield this. So, for L above the answer is { {1,2,1}, {3,4,5,8}, {9,10} } (I'd change {1,2,1} to be {1,2}).

Although VertexInDegree and VertexOutDegree (applied to the output of WeaklyConnectedComponents) easily dispatch this task, I'm hoping there's a slicker easier way that avoids the need to view L as a graph -- if you see one, I'm all ears. I've unsuccessfuly tried GatherBy and MatchQ.

Thanks!

POSTED BY: Bruce Colletti
Posted 9 years ago

Tech Support said to check out FindClusters (really neat). It works for this example whose output correctly groups the arcs into the associated subpaths:

L = {{1, 2}, {3, 4}, {2, 1}, {4, 5}, {9, 10}, {5, 8}};
FindClusters[L, DistanceFunction -> (Abs[Last@#1 - First@#2] &)]

{{{1, 2}, {2, 1}}, {{3, 4}, {4, 5}, {5, 8}}, {{9, 10}}}

Unfortunately, it fails for this example that puts all arcs into one list:

L = {{1, 2}, {3, 4}, {2, 1}, {4, 5}, {7, 8}, {5, 6}, {8, 9}, {11, 12}, {12, 13}, {13, 14}, {16, 17}, {30, 50}};
FindClusters[L, DistanceFunction -> (Abs[Last@#1 - First@#2] &)]

{{{1, 2}, {3, 4}, {2, 1}, {4, 5}, {7, 8}, {5, 6}, {8, 9}, {11, 12}, {12, 13}, {13, 14}, {16, 17}, {30, 50}}}

How could DistanceFunction be modified to correctly handle both examples?

POSTED BY: Bruce Colletti
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract