3
$\begingroup$

Given a graph that contains source nodes (no inlinks) and sink nodes (no outlinks), is there an efficient way to:

  1. Find and list the source nodes in the graph

  2. Find and list the sink nodes in the graph

  3. Find the minimum and maximum path sets between all source and sink nodes, the length of each path, and list the path sets themselves.

In the example below:

  1. The source nodes are N1, N6, and N9
  2. The sink nodes are N5 and N8 and
  3. For source node N1, the path sets and their lengths to the sink nodes reachable from N1 are {{N1, N8}, {N1, N2, N8}, {N1, N2, N3, N4, N8}} with lengths 2,3,5, respectively.

For source node N6, the path sets and their lengths to the sink nodes reachable from N6 are {{N6, N4, N8}, {N6, N2, N8}, {N6, N3, N4, N8}, {N6, N2, N3, N4, N8}} with lengths 3,3,4,5 respectively and {{N6, N4, N5}, {N6, N3, N4, N5}, {N6, N2, N3, N4, N5}} with lengths 3, 4, 5 respectively. For source node N9, the path sets and their lengths to the sink nodes reachable from N9 are {{N9, N8}, {N9, N7, N8}} with lengths 3,3,4,5 respectively.

edges = {N1 -> N2, N2 -> N3, N3 -> N4, N4 -> N5, N6 -> N2, N6 -> N3, 
 N6 -> N4, N1 -> N8, N2 -> N8, N4 -> N8, N7 -> N8, N9 -> N7, 
 N9 -> N8}
$\endgroup$
2
$\begingroup$

You can use the internal function GraphComputation`SourceVertexList and GraphCompuation`SinkVertexList to get the source and sink vertices, and then use FindPath to get the paths. For your example:

g = Graph @ {N1->N2,N2->N3,N3->N4,N4->N5,N6->N2,N6->N3,N6->N4,N1->N8,N2->N8,N4->N8,N7->N8,N9->N7,N9->N8};

source = GraphComputation`SourceVertexList[g]
sink = GraphComputation`SinkVertexList[g]

{N1, N6, N9}

{N5, N8}

The paths are:

Rule[##] -> FindPath[g, ##, Infinity, All]& @@@ Tuples[{source, sink}]

{(N1 -> N5) -> {{N1, N2, N3, N4, N5}}, (N1 -> N8) -> {{N1, N8}, {N1, N2, N8}, {N1, N2, N3, N4, N8}}, (N6 -> N5) -> {{N6, N4, N5}, {N6, N3, N4, N5}, {N6, N2, N3, N4, N5}}, (N6 -> N8) -> {{N6, N4, N8}, {N6, N2, N8}, {N6, N3, N4, N8}, {N6, N2, N3, N4, N8}}, (N9 -> N5) -> {}, (N9 -> N8) -> {{N9, N8}, {N9, N7, N8}}}

$\endgroup$
1
  • $\begingroup$ Carl: Awesome and very efficient coding; many thanks!! ... prg $\endgroup$ – PRG Jun 23 '20 at 5:05
0
$\begingroup$

You can use VertexInDegree and VertexOutDegree in a directed graph to determine if a node is a source, sink, or link node. I don't know how to get the longest path, but I've found all shortest paths from sources to sinks:

SourceOrSink[g_, node_] := Which[
  VertexOutDegree[g, node] > 0 && VertexInDegree[g, node] == 0, "source",
  VertexInDegree[g, node] > 0 && VertexOutDegree[g, node] == 0, "sink",
  True, "link"
]

edges = {N1 -> N2, N2 -> N3, N3 -> N4, N4 -> N5, N6 -> N2, N6 -> N3, 
   N6 -> N4, N1 -> N8, N2 -> N8, N4 -> N8, N7 -> N8, N9 -> N7, N9 -> N8};

g = Graph[edges];

srcsink = {#, SourceOrSink[g, #]} & /@ DeleteDuplicates[VertexList[g]]
sources = Select[srcsink, #[[2]] == "source" &][[All, 1]];
sinks = Select[srcsink, #[[2]] == "sink" &][[All, 1]];

(* shortest paths from sources to sinks *)
shortestSource2Sink = Outer[FindShortestPath[g, #1, #2] &, sources, sinks]

Results:

{{N1, "source"}, {N2, "link"}, {N3, "link"}, {N4, "link"}, {N5, 
  "sink"}, {N6, "source"}, {N8, "sink"}, {N7, "link"}, {N9, "source"}}

(* shortest paths from sources to sinks *)
{{{N1, N2, N3, N4, N5}, {N1, N8}}, {{N6, N4, N5}, {N6, N2, 
   N8}}, {{}, {N9, N8}}}

You can find all path sets from sources to sinks using Outer[FindPath[g, #1, #2, ∞, All]&, sources, sinks] instead. Also have a look at related problems like FindMaximumFlow.

$\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.