zef:antononcube

# 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".
• 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(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)
``````

``````\$graph.mermaid(d=>'TD')
``````
``````graph TD
5 --- 1
5 --- 12
3 --- 2
3 --- 4
3 --- 8
6 --- 2
6 --- 7
1 --- 7
10 --- 2
10 --- 9
4 --- 2
4 --- 9
7 --- 2
2 --- 12
2 --- 8
12 --- 11
``````

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 : ([1 5 12 2 7 1])
``````

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])
``````

## 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`.
• TODO Disjoint graphs
• The graphs can be disjoint as long as the components have edges.
• I.e. the class `Graph` does not support "lone vertices."
• 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)
• TODO Vertex tags support
• TODO Has vertex
• TODO Edges
• DONE Edge list
• DONE Edge dataset
• DONE Edge count
• DONE Delete edge(s)
• TODO Edge tags support
• TODO Has edge
• TODO Matrix representation
• Sparse matrices are needed before "seriously" considering this.
• Sparse matrices should be easy to create using the (already implemented) edge dataset.

### 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 diameter
• DONE Graph center
• DONE Graph periphery
• TODO Topological paths
• TODO Topological sort
• TODO Cycles and tours
• DONE Find cycle
• Just one cycle
• All cycles
• TODO Find shortest tour
• TODO Find postman tour
• 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

### Operations

• TODO Unary graph operations
• TODO Reversed graph
• TODO Complement graph
• TODO Make undirected
• Can be implemented as `Graph.new(\$g, :!directed)`.
• But maybe it is more efficient to directly manipulate `adjacency-list`.
• TODO Make directed
• That is just a flag change. (Of `\$!directed`.)
• TODO Edge contraction
• TODO Line graph
• TODO Dual graph
• TODO Binary graph operations
• TODO Disjoint union of graphs
• TODO Cartesian product of graphs
• TODO Tensor product of graphs
• TODO Strong product of graphs
• TODO Lexicographic product of graphs

### Tests

• TODO Unit tests
• DONE Sanity
• DONE Undirected graphs
• DONE Vertex removal
• DONE Edge removal
• 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.)
• TODO Random graphs creation

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

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

### Videos

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