text: # 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.
explanation: The document describes a problem related to finding source and sink nodes in a directed graph, as well as the minimum and maximum path sets between these nodes. It includes a detailed example and a solution using graph functions in a programming environment (likely Mathematica). The document contains both a question and an answer.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document describes a problem related to finding source and sink nodes in a directed graph, as well as the minimum and maximum path sets between these nodes. It includes a detailed example and a solution using graph functions in a programming environment (likely Mathematica). The document contains both a question and an answer.
  
  Label: question-and-answer