ARCcore.graph Algorithms Reference
Login
-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.

"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

Introduction

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.

Transform Algorithms

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.

Traversal Algorithms

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

Digraph Transpose - DirectedGraph Transpose Algorithm Reference
ARCcore.graph.DirectedGraph transpose tranformation algorithm.
Digraph Breadth-First - DirectedGraph Breadth-First Traversal Algorithm Reference
ARCcore.graph.DirectedGraph breadth-first visit/search traversal algorithm.
Digraph Depth-First - DirectedGraph Depth-First Traversal Algorithm Reference
ARCcore.graph.DirectedGraph depth-first visit/search traversal algorithm.
Digraph Traversals - DirectedGraph Traversal Algorithms Reference
Initializing and controlling traversal algorithm state.
Encapsule Project, Seattle WA
Copyright © 2018 Chris Russell
Sat Dec 15 2018 04:09:03 GMT-0500 (EST)

Encapsule/holism v0.0.26
Documents Under Contruction