12
$\begingroup$

Keywords: vertex, ancestors, descendants, subgraph, directed graph, flow subtree


So let's say we have a TreeGraph:

opts = Sequence[
   EdgeShapeFunction -> GraphElementData["FilledArrow", "ArrowSize" -> 0.02], 
   VertexLabels      -> "Name"
];

data = RandomInteger[#] -> # + 1 & /@ Range[0, 10];

g = TreeGraph[data, opts]

enter image description here

Question

What's the proper/functional way to get subgraph containing only successors of given node with respect to the flow.

I'm not very familiar with graphs so I have a solution (bottom) but I suppose I'm missing some basic graph related functions.

Example

for 0 it would be the whole graph

for 4 it would be {4->5, 5->8, 8->9}

Problem

I can't find appriopriate function and AdjacencyList/IncidenceList don't respect the direction of the flow:

topV = 4;
HighlightGraph[g, 
  {Style[topV, Blue], AdjacencyList[g, topV, 2], IncidenceList[g, topV, 2]}
]

enter image description here

My brute force but not so stupid solution:

let's cut the inflow! so the AdjacencyList won't leave this way :)

subTreeWF[g, 4] // TreeGraph[#, opts] &

enter image description here

I'm assuming here that the topNode is not the final one, in such case additional check is needed.

subTreeWF[treeGraph_, topNode_] := Module[{edges},
  edges = EdgeList @ treeGraph;
  edges = DeleteCases[  edges, 
     (Rule | DirectedEdge | UndirectedEdge)[_, topNode]
  ];

  IncidenceList[Graph @ edges, topNode, \[Infinity]]

]

g = Graph[RandomInteger[#] -> # + 1 & /@ Range[0, 30], opts];

topV = 5;

HighlightGraph[g, {Style[topV, Blue], subTreeWF[g, topV]}]

enter image description here

$\endgroup$
  • 1
    $\begingroup$ In return for the answer, will you please test my package, to make sure I didn't mess anything up before I release it? :-) $\endgroup$ – Szabolcs Oct 14 '15 at 20:32
  • $\begingroup$ @Szabolcs Ok, will try some things ;) Thanks for the answer. $\endgroup$ – Kuba Oct 14 '15 at 20:41
14
$\begingroup$

You are looking for VertexOutComponent.

VertexOutComponent[g, 4]

gives you the successors of 4. Use Subgraph to get an actual graph out of those. With HighlightGraph, you can also use a subgraph, it will highlight both vertices and edges: HighlightGraph[g, Subgraph[g, VertexOutComponent[g, 4]]].

For visualizing the graph, use GraphLayout -> "LayeredDigraphEmbedding", which will place the root at the topmost position. Some other tree layouts have a "RootVertex" suboptions to achieve this (e.g. for undirected where anything can be the "root").

$\endgroup$
  • $\begingroup$ @Kuba Sorry, I don't understand your question ... $\endgroup$ – Szabolcs Oct 18 '15 at 9:58
  • $\begingroup$ @Kuba Ah, I already got a confirmation in chat that it worked fine on Windows, so no need anymore :-) At least not until the next release $\endgroup$ – Szabolcs Oct 18 '15 at 10:04
5
$\begingroup$

You could also do for example the following for recovering the result as a graph:

HighlightGraph[g, s = Last@Reap@BreadthFirstScan[g, 3, {"FrontierEdge" -> Sow}]]

Mathematica graphics

Graph@@s

Mathematica graphics

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