Moose-Algos-Graph is a stand-alone library containing both classical and prototypal graph algorithms, with new algorithms added as needed. Moose-Algos-Graph is designed to be both easy to use and easy to extend, while following the standard implementation of graph algorithms to get proven complexity.
Ease of use is achieved through a simple API to create a graph model from a pool of data, run or extend existing algorithms, and retrieving results. The library API takes inspiration from the Mondrian API to create graph.
The graph library is designed and maintained by Simon Denier.
There are three generic steps followed by all algorithms, with some adaptation for specific cases:
Take for example
MalTarjan, an implementation of Tarjan’s algorithm for detection of strongly connected components in graph.
tarjan := MalTarjan new.
Let’s take as graph data the series of nodes $a to $d, and a couple of node pairs where ($a $b) implies an edge from $a to $b. We project this information in in the tarjan instance to create the graph model:
tarjan nodes: ($a to: $d).
tarjan edges: #(($a $b) ($b $c) ($c $a) ($d $c))
All algorithms compute their results in batch by calling
You can directly ask tarjan for the list of strongly connected components. Each component is itself a collection of nodes:
" -> (($a $b $c) ($d))"
Alternatively, some node representations have a specific API to access result:
bNode := tarjan findNode: $b.
“bNode is the representation of $b in Tarjan”
“true if node is in a component of size bigger than 1
(node in cycle with other nodes)”
“return other nodes from the strongly connected component”
MalGraphAlgorithm is the superclass of all algorithms and defines the generic API to create and access graphs.
edges: aCollection from: aSymbolOrBlock to: aSymbolOrBlock
edges: aCollection from: aSymbolOrBlock toAll: aSymbolOrBlock
edges: aCollection from: aSymbolOrBlock to: aSymbolOrBlock weight: aSymbolOrBlock
You can extend the current library to define a new graph algorithm. This is actually pretty simple as you have just a few rules to respect.
MalGraphEdgeto create dedicated metamodel classes
MalGraphAlgorithmwith your class to implement the main algorithm
MalGraphAlgorithm>>edgeClassto return metamodel classes dedicated to your representation.
MalGraphAlgorithmtakes care of creating a graph model using your representation
MalGraphAlgorithm>>runlaunches the algorithm
An important note: graph algorithms often relies on dedicated data structures to achieve good complexity. A good example is in Tarjan: the algorithm puts nodes on a stack and regularly tests nodes for stack membership. However, testing stack membership by iterating over the stack would ruin the complexity. Instead, Tarjan uses a flag in each node instance to test for stack membership (meaning constant complexity for this operation and guaranteeing the overall linear complexity).
Some algorithms run over nodes while others run over edges (and sometimes on both). Thus it is important to understand which dedicated data structures one must define (or reuse) for a graph algorithm. Fortunately, the library makes it very easy to specify which classes to use to create nodes and edges: graph creation is performed automatically using the specified classes. The default class for node is
MalGraphNode. By default, there is no class to represent an edge, which means that edge representations are not created by the graph. Edges are created only if
#edgeClass returns a class.
MalBreadthFirstSearchPath: finds the shortest path between two nodes by performing a breadth first search.
MalDijkstra: finds the path of minimum weight between two nodes using Dijkstra.
MalDominance: performs a simple dominance-based partitioning of the graph (a node dominates another if it is the sole predecessor node). It is based on the union-find algorithm.
MalGraphStructure: is a utility class to transform a graph into another using parameterized classes for edges and nodes.
#edgeClass:, then runs the algorithm to create a new graph with custom classes
MalHits: performs a Hubs and Authorities algorithm.
MalWeightedHits: performs a Hubs and Authorities algorithm taking into account weighted edges.
MalKruskal: computes the minimal (or maximal) spanning tree of a connected graph with weighted edges (that is, tree of minimal (maximal) weight which connects all nodes in the graph).
MalTarjan: computes strongly connected components.
MalHal: computes layers between nodes by giving them a layer number (naive implementation). All nodes belonging to a strongly connected component are given the same number.
Disjoint-set data structure: see MalDisjointSetNode for a data structure supporting partitioning through union-find algorithm (see Kruskal and Dominance for examples)