Data.Graph.InducedTree
- Package
- purescript-hylograph-graph
- Repository
- afcondon/purescript-hylograph-graph
The tree a traverser is forced to build, and everything that is not in it.
A designer sees a graph, in which every edge is equally near to hand and hierarchy is a matter of taste. Anyone walking the graph cannot see it that way: a walk starts somewhere and memory is hierarchical, so what a traverser ends up holding is the shortest-path tree rooted at the start, plus a pile of edges that tree does not explain. That tree is induced by the graph whether the designer looked at it or not, which is why a tool that only ever draws the graph is showing the designer something other than what the walker receives.
Sorting the leftover edges is where the signal is. A back edge is the way out, and its absence is a trap. A forward edge skips levels — a shortcut, directness bought at the cost of taxonomy. A cross edge jumps into a different subtree, which is the interlevel transition that makes where-you-are impossible to reconstruct from how-you-got-here.
The vocabulary is deliberately the classical DFS edge classification applied to a breadth-first tree, because the question here is not "is there a cycle" but "how far from home is this, and how far back" — and only the shortest-path tree answers that.
Extracted from the Glassbox state-machine demo, where it was written against
String-keyed states while Data.Graph.Pathfinding.bfs was undirected and
could not serve. Now that Data.Graph.Algorithms.bfsTree is both directed
and node-polymorphic, this is a general graph concept and belongs here.
#EdgeClass Source
data EdgeClassWhat an edge is, relative to the tree a traverser experiences.
ForwardEdge is in the vocabulary because the vocabulary is the classical
one, but it cannot occur against a breadth-first tree and induce will
never return it. If from is a proper ancestor of to then the edge itself
bounds depth to <= depth from + 1, while the ancestry bounds it below by
the same quantity, so to's parent is from and the edge is a TreeEdge.
A depth-first induce would populate it; a shortest-path one cannot, and the
shortcut it was meant to name shows up as a TreeEdge that shortens the
tree instead. Retained so the classification reads the same as everyone
else's and so a future DFS variant has somewhere to put its answer.
Constructors
Instances
#edgeClassLabel Source
edgeClassLabel :: EdgeClass -> String#induce Source
induce :: forall node. Ord node => node -> SimpleGraph node -> Induced nodeInduce the tree, and classify every edge against it.
#asymmetries Source
asymmetries :: forall node. Ord node => Induced node -> Array { excess :: Int, inCost :: Int, outCost :: Int, state :: node }Nodes that are much harder to leave than to reach.
The single most reliable signature of an awful menu: in by one press, out by four. Reported worst-first, and only where the return actually costs more than the arrival.
#pathFromRoot Source
pathFromRoot :: forall node. Ord node => Induced node -> node -> Array nodeHow you get here from the root, as the tree tells it.
The traverser's own question, and the induced tree is exactly the thing that answers it. Empty for a node the root cannot reach.
An Induced is a search tree with extra fields, so treePath walks it
unchanged; this name exists because the question is worth naming.