Module

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 EdgeClass

What 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

#Induced Source

type Induced node = { children :: Map node (Array node), classes :: Map (Tuple node node) EdgeClass, depth :: Map node Int, parent :: Map node node, returnCost :: Map node Int, root :: node, unreachable :: Array node }

The shortest-path tree rooted at root, plus a verdict on every edge.

#induce Source

induce :: forall node. Ord node => node -> SimpleGraph node -> Induced node

Induce the tree, and classify every edge against it.

#classOf Source

classOf :: forall node. Ord node => Induced node -> node -> node -> Maybe EdgeClass

#depthOf Source

depthOf :: forall node. Ord node => Induced node -> node -> Maybe Int

#returnCostOf Source

returnCostOf :: forall node. Ord node => Induced node -> node -> Maybe Int

#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 node

How 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.