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.

Using a graph algorithm

There are three generic steps followed by all algorithms, with some adaptation for specific cases:

1. Initializing the algorithm (creating the graph)
2. Running the algorithm
3. Retrieving results

Take for example MalTarjan, an implementation of Tarjan’s algorithm for detection of strongly connected components in graph.

|tarjan|
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))
	 from: #first 
	 to: #second.

All algorithms compute their results in batch by calling #run.

tarjan run.

You can directly ask tarjan for the list of strongly connected components. Each component is itself a collection of nodes:

tarjan stronglyConnectedComponents.
 " -> (($a $b $c) ($d))"

Alternatively, some node representations have a specific API to access result:

|bNode|
bNode := tarjan findNode: $b.
“bNode is the representation of $b in Tarjan”
bNode isInCycle.
“true if node is in a component of size bigger than 1
 (node in cycle with other nodes)”
bNode cycleNodes.
“return other nodes from the strongly connected component”

API of MalGraphAlgorithm

Class MalGraphAlgorithm is the superclass of all algorithms and defines the generic API to create and access graphs.

Creation

nodes: aCollection
edges: aCollection from: aSymbolOrBlock to: aSymbolOrBlock
edges: aCollection from: aSymbolOrBlock toAll: aSymbolOrBlock
edges: aCollection from: aSymbolOrBlock to: aSymbolOrBlock weight: aSymbolOrBlock

Access

nodes
edges
graph
findNode:
findNode:ifAbsent:
findEdge:

Creating a new graph algorithm

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.

1. subclass MalGraphNode and/or MalGraphEdge to create dedicated metamodel classes
2. subclass MalGraphAlgorithm with your class to implement the main algorithm
3. override MalGraphAlgorithm>>nodeClass and/or MalGraphAlgorithm>>edgeClass to return metamodel classes dedicated to your representation. MalGraphAlgorithm takes care of creating a graph model using your representation
4. by convention, MalGraphAlgorithm>>run launches the algorithm
5. depending on your algorithm, you may need other parameters as well as methods to access results

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.

Current library

MalBreadthFirstSearchPath: finds the shortest path between two nodes by performing a breadth first search.

• send #runFrom: startNode to: endNode, which returns the path.

MalDijkstra: finds the path of minimum weight between two nodes using Dijkstra.

• send #runFrom:to:, which returns the minimal weight of the path
• send #backtrack after running to get the path
• send #reset to perform a new run on the same graph

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.

• send #run
• query results through MalDominanceNode instances

MalGraphStructure: is a utility class to transform a graph into another using parameterized classes for edges and nodes.

• configure MalGraphStructure with #nodeClass: and #edgeClass:, then runs the algorithm to create a new graph with custom classes

MalHits: performs a Hubs and Authorities algorithm.

• query results through MalHitsNode instances

MalWeightedHits: performs a Hubs and Authorities algorithm taking into account weighted edges.

• query results through MalWeightedHitsNode instances

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

• send #maxSpanningTree to configure the algorithm to compute the maximal spanning tree (default is #minSpanningTree)
• send #run, returns the collection of edges making the tree

MalTarjan: computes strongly connected components.

• send #run
• send #stronglyConnectedComponents to get the collection of all strongly connected components (each component is a collection of nodes)
• or query results through instance of MalTarjanNode

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.

• send #run
• query results through MalHalNode instances

Disjoint-set data structure: see MalDisjointSetNode for a data structure supporting partitioning through union-find algorithm (see Kruskal and Dominance for examples)