Graph

Graph theory algorithms, parameterized- and random graphs.

Graph

Raku package for (discrete mathematics) graph data structures and algorithms.

For a quick introduction see the video "Graph demo in Raku (teaser)", [AAv1], (5 min.)

Remark: This package is not for drawing and rendering images. It is for the abstract data structure graph.

Installation

From Zef ecosystem:

zef install Graph

From GitHub:

zef install https://github.com/antononcube/Raku-Graph.git

Design and implementation details

Motivation

Needless to say, Graph theory is huge.
- But certain algorithms like path and cycle finding are relatively easy to implement and are fundamental both mathematics-wise and computer-science-wise.
Having fast shortest path finding algorithms in graphs should be quite a booster for geography related projects.

Design

The central entity is the Graph class.
Graph is as generic as possible.
- Meaning it is for directed graphs.
- Undirected graphs are represented as directed graphs.
  - I.e. with twice as many edges than necessary.
- The current graph representation is with hash-of-hashes, (adjacency-map), that keeps from-to-weight relationships.
  - For example, $g.adjacency-map<1><2> gives the weight of the edge connecting vertex "1" to vertex "2".
- The vertexes are only strings.
  - Not a "hard" design decision.
  - More general vertexes can be imitated (in the future) with vertex tags.
    - This is related to having (in Raku) sparse matrices with named rows and columns.
Since I know Mathematica / Wolfram Language (WL) very well, many of the method names and signatures are strongly influenced by the corresponding functions in WL.
- I do not follow them too strictly, though.
- One reason is that with Raku it is much easier to have and use named arguments than with WL.

Implementation

I was considering re-programming Perl5’s "Graph", [JHp1], into Raku, but it turned out it was easier to write the algorithms directly in Raku.
- (To me at least...)
The classes creating special graphs, like, grid-graph, star-graph, etc., are sub-classes of Graph with files in the sub-directory "Graph".
- See usage of such classes here.

Visualization

Visualizing the graphs (the objects of the class Graph) is very important.
- Has to be done from the very beginning of the development.
  - (Again, for me at least...)
The class Graph has the methods dot, graphml, mermaid, and wl for representing the graphs for GraphViz, GraphML, Mermaid-JS, and Wolfram Language (WL) respectively.
Mermaid's graph nodes and edges arrangement algorithm can produce "unexpected" images for the standard, parameterized graphs.
- Like, "grid graph", "cycle graph", etc.

Performance

So far, I have tested the path finding algorithms on "Graph" on small graphs and moderate size graphs.
- The largest random graph I used had 1000 vertexes and 1000 edges.
- Mathematica (aka Wolfram Language) can be 500 ÷ 10,000 faster.
- I hope good heuristic functions for the "A* search" method would make find-shortest-path fast enough, for say country / continent route systems.
  - With the larger, 1,000-vertex random graphs finding paths with the method "a-star" is ≈50 faster than with the method "dijkstra".
    - See here.
Setting up comprehensive performance profiling and correctness testing is somewhat involved.
- One main impediment is that in Raku one cannot expect and specify same random numbers between different sessions.

Usage examples

Here we create a dataset of edges:

my @edges =
        { from => '1', to => '5', weight => 1 },
        { from => '1', to => '7', weight => 1 },
        { from => '2', to => '3', weight => 1 },
        { from => '2', to => '4', weight => 1 },
        { from => '2', to => '6', weight => 1 },
        { from => '2', to => '7', weight => 1 },
        { from => '2', to => '8', weight => 1 },
        { from => '2', to => '10', weight => 1 },
        { from => '2', to => '12', weight => 1 },
        { from => '3', to => '4', weight => 1 },
        { from => '3', to => '8', weight => 1 },
        { from => '4', to => '9', weight => 1 },
        { from => '5', to => '12', weight => 1 },
        { from => '6', to => '7', weight => 1 },
        { from => '9', to => '10', weight => 1 },
        { from => '11', to => '12', weight => 1 };

@edges.elems;

# 16

Remark: If there is no weight key in the edge records the weight of the edge is taken to be 1.

Here we create a graph object with the edges dataset:

use Graph;

my $graph = Graph.new;
$graph.add-edges(@edges);

# Graph(vertexes => 12, edges => 16, directed => False)

Here are basic properties of the graph:

say 'edge count   : ', $graph.edge-count;
say 'vertex count : ', $graph.vertex-count;
say 'vertex list  : ', $graph.vertex-list;

# edge count   : 16
# vertex count : 12
# vertex list  : (1 10 11 12 2 3 4 5 6 7 8 9)

Here we display the graph using Mermaid-JS, (see also, [AAp1]):

$graph.mermaid(d=>'TD')

Here we find the shortest path between nodes "1" and "4":

say 'find-shortest-path : ', $graph.find-shortest-path('1', '4');

# find-shortest-path : [1 7 2 4]

Here we find all paths between "1" and "4", (and sort them by length and vertex names):

say 'find-path : ' , $graph.find-path('1', '4', count => Inf).sort({ $_.elems ~ ' ' ~ $_.join(' ') });

# find-path : ([1 7 2 4] [1 5 12 2 4] [1 7 2 3 4] [1 7 6 2 4] [1 5 12 2 3 4] [1 7 2 10 9 4] [1 7 2 8 3 4] [1 7 6 2 3 4] [1 5 12 2 10 9 4] [1 5 12 2 8 3 4] [1 7 6 2 10 9 4] [1 7 6 2 8 3 4])

Here we find a Hamiltonian path in the graph:

say 'find-hamiltonian-path : ' , $graph.find-hamiltonian-path();

# find-hamiltonian-path : [11 12 5 1 7 6 2 10 9 4 3 8]

Here we find a cycle:

say 'find-cycle : ' , $graph.find-cycle().sort({ $_.elems ~ ' ' ~ $_.join(' ') });

# find-cycle : ([10 2 4 9 10])

Here we find all cycles in the graph:

say 'find-cycle (all): ' , $graph.find-cycle(count => Inf).sort({ $_.elems ~ ' ' ~ $_.join(' ') });

# find-cycle (all): ([2 3 4 2] [2 3 8 2] [2 6 7 2] [10 2 4 9 10] [2 4 3 8 2] [1 5 12 2 7 1] [10 2 3 4 9 10] [1 5 12 2 6 7 1] [10 2 8 3 4 9 10])

Graph plotting

Graph formats

The class Graph has the following methods of graph visualization:

wl for making Wolfram Language graphs
dot for visualizing via Graphviz using the DOT language
graphml for GraphML visualizations
mermaid for Mermaid-JS visualizations

Visualizing via DOT format

In Jupyter notebooks with a Raku kernel graph visualization can be done with the method dot and its adverb ":svg".

First, install Graphviz.

On macOS the installation can be done with:

brew install graphviz

Here a wheel graph is made and its DOT format is converted into SVG format (rendered automatically in Jupyter notebooks):

use Graph::Wheel;
Graph::Wheel.new(12).dot(:svg)

For more details see notebook "DOT-visualizations.ipynb".

Visualizing via D3.js

In Jupyter notebooks with a Raku kernel graph visualization can be done with the function js-d3-graph-plot of the package "JavaScript::D3".

The visualizations with "JavaScript::D3" are very capricious. Currently they:

Do not work with JupyterLab, but only with the "classical" Jupyter notebook.
Work nicely with the Jupyter notebook plugin(s) of Visual Studio Code, but often require re-loading of the notebooks.

The points above were the main reasons to develop the DOT format visualization. Most of the documentation notebooks show the graphs using both "JavaScript::D3" and DOT-SVG.

CLI

The package provides the Command Line Interface (CLI) script graph-creation that can be used to create graphs and export them to different formats. For example:

graph-creation Grid --rows=3 --columns=2 --format=dot

# graph {
# "1_0" [pos="0,1!"];
# "1_1" [pos="1,1!"];
# "2_0" [pos="0,2!"];
# "0_0" [pos="0,0!"];
# "2_1" [pos="1,2!"];
# "0_1" [pos="1,0!"]
# "1_0" -- "2_0" 
# "2_0" -- "2_1" 
# "1_1" -- "2_1" 
# "1_0" -- "1_1" 
# "0_1" -- "1_1" 
# "0_0" -- "1_0" 
# "0_0" -- "0_1" 
# }

TODO

Main, core features

Graph programming

TODO Depth first scan / traversal
- Scan a graph in a depth-first order.
- This is already implemented, it has to be properly refactored.
  - See Depth-First Search (DFS) named (private) methods.
TODO Breadth first scan / traversal
- Scan a graph in a breadth-first order.

Paths, cycles, flows

Matching, coloring

DONE Check is a graph bipartite
DONE Hungarian algorithm for bipartite graphs
- At tum.de
TODO Perfect match for bipartite graphs
TODO Matching edges

Operations

Construction

CLI

Tests

Documentation

DONE Basic usage over undirected graphs
TODO Basic usage over directed graphs
DONE Regular graphs creation (Grid, Wheel, etc.)
- Notebook with a gallery of graphs
DONE Random graphs creation
DONE DOT language visualizations