ARCcore.graph Algorithms Reference

-Home

-Documentation

-ARCcore

-graph

-Algorithms

+DirectedGraph

-Algorithms

Examples

Digraph Transpose

Digraph Breadth-First

Digraph Depth-First

Digraph Traversals

ARCcore.graph Bundled Algorithms Reference

Documentation and reference for graph algorithms bundled with ARCcore.graph.

Documentation and reference for graph algorithms bundled with ARCcore.graph.

*"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.

Depending on your requirements, there are other open source JavaScript graph libraries that provide single-call graph algorithm functions
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.

Encapsule/holism v0.0.26

Documents Under Contruction