Finding Source and Sink Nodes and Paths in a Directed Graph

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}

You can use the internal function GraphComputationSourceVertexList and GraphCompuationSinkVertexList 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 = GraphComputationSourceVertexList[g]
sink = GraphComputationSinkVertexList[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}}}

• Carl: Awesome and very efficient coding; many thanks!! ... prg
– PRG
Jun 23 '20 at 5:05

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",
]

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, #[] == "source" &][[All, 1]];
sinks = Select[srcsink, #[] == "sink" &][[All, 1]];

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

Results: