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-list), that keeps from-to-weight relationships.
  - For example, $g.adjacency-list<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')

graph TD
10 --- 2
10 --- 9
2 --- 3
3 --- 4
3 --- 8
2 --- 4
2 --- 7
12 --- 2
2 --- 8
2 --- 6
1 --- 5
1 --- 7
6 --- 7
12 --- 5
11 --- 12
4 --- 9

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 : [10 9 4 3 8 2 6 7 1 5 12 11]

Here we find a cycle:

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

# find-cycle : ([2 3 4 2])

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.

TODO

Main, core features

TODO Object methods
- DONE Str and gist methods
- DONE Deep copy
- DONE Creation from another graph.
- TODO Ingest vertexes and edges of another Graph object
- TODO Comparison: eqv and ne.
DONE Disjoint graphs
- The graphs can be disjoint as long as the components have edges.
- Related, the class Graph does supports "lone vertices."
  - They have empty adjacency values.
TODO Vertexes
- DONE Vertex list
- DONE Vertex count
- DONE Vertex degree
- DONE in-degree, edges-at
- DONE out-degree, edges-from
- DONE Delete vertex(es)
- DONE Add vertex
- DONE Has vertex
- TODO Vertex tags support
TODO Edges
- DONE Edge list
- DONE Edge dataset
- DONE Edge count
- DONE Add edge
- DONE Delete edge(s)
- DONE Has edge
- TODO Edge tags support
TODO Matrix representation
- Sparse matrices are needed before "seriously" considering this.
- Sparse matrices should be easy to create using the (already implemented) edge dataset.
- DONE Adjacency matrix (dense)
- TODO Adjacency matrix (sparse)
- Incidence matrix (dense)
- Incidence matrix (sparse)

Graph programming

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.
Breadth first scan / traversal
- Scan a graph in a breadth-first order.

Paths, cycles, flows

DONE Shortest paths
- DONE Find shortest path
- DONE Find Hamiltonian paths
  - For both the whole graph or for a given pair of vertexes.
  - Algorithms:
    - Backtracking, method => 'backtracking')
    - Application Warnsdorf's rule for backtracking, :warnsdorf-rule
    - Angluin-Valiant (probabilistic), method => 'random'
TODO Flows
- TODO Find maximum flow
- TODO Find minimum cost flow
TODO Distances
- DONE Graph distance
  - See shortest path.
- TODO Graph distance matrix
  - Again, requires choosing a matrix Raku class or package.
DONE Longest shortest paths
- DONE Vertex eccentricity
- DONE Graph radius
- DONE Graph diameter
- DONE Graph center
- DONE Graph periphery
DONE Weakly connected component
DONE Strongly connected component
- DONE Tarjan's algorithm
- TODO Kosaraju's algorithm
DONE Topological sort
- Using Tarjan's algorithm
TODO Cycles and tours
- DONE Find cycle
  - Just one cycle
  - All cycles
- TODO Find shortest tour
- TODO Find postman tour
  - DONE Eulerian and semi-Eulerian graphs
  - TODO General graphs
- TODO Find Eulerian cycle
- TODO Find Hamiltonian cycle
- TODO Find cycle matrix
TODO Independent paths
- DONE Find paths
- TODO Find edge independent paths
- TODO Find edge vertex paths

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

TODO Unary graph operations
- DONE Reversed graph
- DONE Complement graph
- DONE Subgraph
  - For given vertices and/or edges.
- DONE Neighborhood graph
  - For given vertices and/or edges.
- DONE Make undirected
  - Can be implemented as Graph.new($g, :!directed).
  - But maybe it is more efficient to directly manipulate adjacency-list.
- DONE Make directed
  - It is not just a flag change of $!directed.
  - Implement the methods: Whatever, "Acyclic", "Random".
- TODO Edge contraction
- TODO Vertex contraction
- TODO Line graph
- TODO Dual graph
TODO Binary graph operations
- DONE Union of graphs
- DONE Intersection of graphs
- DONE Difference of graphs
- DONE Disjoint union of graphs
- TODO Product of graphs (AKA "box product")
  - TODO Cartesian
  - TODO Co-normal
  - TODO Lexicographic
  - TODO Normal
  - TODO Rooted
  - TODO Strong
  - TODO Tensor

Construction

DONE Construction of (regular) graphs
- DONE Complete graphs
- DONE Cycle graphs
- DONE Hypercube graphs
- DONE Grid graphs
- DONE Knight tour graphs
- DONE Star graphs
- DONE Path graphs
- DONE Wheel graphs
- DONE Indexed graphs
- DONE Hexagonal grid graphs
DONE Construction of random graphs
- Since different kinds of vertex-edge distributions exists, separate distributions objects are used.
  - See Graph::Distribution.
- DONE Barabasi-Albert distribution
- DONE Bernoulli distribution
- DONE de Solla Price's model distribution
- DONE "Simple" random (m, n) graphs with m-vertexes and n-edges between them
  - This was the first version of Graph::Random.
  - Refactored to be done via the uniform graph distribution.
- DONE Watts–Strogatz model distribution
- DONE Uniform distribution
TODO Construction of individual graphs
- TODO Bull graph
- TODO Butterfly graph
- TODO Chavatal graph
- TODO Diamond graph
- TODO Durer graph
- TODO Franklin graph
- DONE Petersen graph
- TODO Wagner graph
Creation from
- Adjacency matrix (dense)
- Adjacency matrix (sparse)
- Incidence matrix (dense)
- Incidence matrix (sparse)

Tests

TODO Unit tests
- DONE Sanity
- DONE Undirected graphs
- DONE Vertex removal
- DONE Edge removal
- DONE Bipartite graph check
- TODO Directed graphs cycles
TODO Cross-verification with Mathematica
- DONE General workflow programming/setup
- TODO Path finding
- TODO Cycle finding

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