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

Loading

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

Here we find a cycle:

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

# find-cycle : ([2 6 7 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 to main reason to develop the DOT format visualizations. 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.
• 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
• 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
  • TODO 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

---

References

Articles

[Wk1] Wikipedia entry, "Graph (discrete mathematics)".

[Wk2] Wikipedia entry, "Graph theory".

[Wk3] Wikipedia entry, "Glossary of graph theory".

[Wk4] Wikipedia entry, "List of graphs" (aka "Gallery of named graphs.")

[Wk5] Wikipedia entry, "Hamiltonian path".

Packages

[AAp1] Anton Antonov, WWW::MermaidInk Raku package, (2023), GitHub/antononcube.

[AAp2] Anton Antonov, Proc::ZMQed Raku package, (2022), GitHub/antononcube.

[AAp3] Anton Antonov, JavaScript:3 Raku package, (2022-2024), GitHub/antononcube.

[JHp1] Jarkko Hietaniemi, Graph Perl package, (1998-2014), MetaCPAN.

Videos

[AAv1] Anton Antonov, "Graph demo in Raku (teaser)", (2024), YouTube/@AAA4Prediction.

[AAv2] Anton Antonov, "Graph neat examples in Raku (Set 1)", (2024), YouTube/@AAA4Prediction.

[AAv3] Anton Antonov, "Sparse matrix neat examples in Raku", (2024), YouTube/@AAA4Prediction.