# 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 Commented Jun 23, 2020 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, #[[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.
The text passage describes a problem related to finding source and sink nodes in a directed graph, as well as finding the minimum and maximum path sets between these nodes. It includes an example with specific nodes and edges, and provides answers to the questions posed.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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 Commented Jun 23, 2020 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, #[[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.
user
The text passage describes a problem related to finding source and sink nodes in a directed graph, as well as finding the minimum and maximum path sets between these nodes. It includes an example with specific nodes and edges, and provides answers to the questions posed.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS