"Begin at the beginning," the King said very gravely. "and go on till you come to the end: then stop." - Lewis Carroll, Alice in Wonderland
ARCcore.graph bundles a small collection of powerful functions that operate on the data contained in a
DirectedGraph container in useful ways.
Terminology, naming, and conventions used here are
taken from Chapter 23 "Elementary Graph Algorithms" of the book
Introduction To Algorithms (MIT Press).
The magic of graph algorithms is that deep insight can be derived from watching and analyzing how specific graph algorithms traverse specific
graph interconnect typologies. However, graph traversal algorithms are hard to implement due to their complexity and most implementations
are purpose-built, and/or have little facility for embedded re-use or extension in contexts their authors didn't anticipate.
ARCcore.graph addresses this problem by copying the Boost Graph Library (BGL)'s fantastic use of the visitor pattern to encapsulate the
specific goal strategies of graph traversal algorithms. The resulting API makes trivial re-use cases trivial and advanced use cases possible.
that may better suit your needs. I couldn't find any that were as flexible and extensible as the
BGL with which I was familiar.
So, I built ARCcore.graph to feel like the BGL. And, then wrote a lot of tests.
If you find a problem, please report it!
In situations where you need to write your own custom algorithms, or derive sophisticated results from vertex, edge, and topology it makes
sense to re-use the core visitor algorithms included here as the basis for your own complex data masterpiece. Or, write your own
algorithms in this style using the
DirectedGraph container's API to separate your concerns.
Once you get used to the style, there's really just no substitute for the BGL visitor API style traversal algorithms.
There are two types of algorithms included: transforms and traversals.
See: Digraph Transpose (others coming as I have time to document them)
Transform algorithms generate new a
DirectedGraph container instance from existing container(s) applying some prescribed filter,
or transformation to the vertex and/or edge lists. Source
DirectedGraph instance(s) are not mutated.
See: Digraph Breadth-First, Digraph Depth-First, Digraph Traversals
Traversal functions are miniature agent processes that traverse the topology of a
DirectedGraph container issuing callbacks to your
derived client code at specified event points (See also: visitor pattern).
Think of your graph as a maze with edge hallways and vertex intersections.
As the algorithmic agent walks through the maze it keeps track of where it's been so as to be able to dig itself out of corners and dead-ends.
(See also: graph coloring).
Each algorithm implements a different specific agent with its own goal strategies for "running the maze."
Keeping track of traversal state is the primary function of the traversal algorithms bundled with this library. Typically, you will not
have to worry very much about it at all and the visitor pattern callbacks will be the center of your attention.
However, if you're building really advanced derived algorithms you should read Digraph Traversals that details
how traversal state is managed and explains how you can control it in your derived code.
Bundled Algorithms Reference