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

- For example,
- 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...)

- Has to be done from the very beginning of the development.
- 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.

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

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 8 3 4 9 10]
```

Here we find a cycle:

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

```
# find-cycle : ([2 3 8 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])
```

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

### 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 Graph distance
- 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

- DONE Find cycle
- 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`

.

- Can be implemented as
- DONE Make directed
- It is not just a flag change of
`$!directed`

. - Implement the methods:
`Whatever`

, "Acyclic", "Random".

- It is not just a flag change of
- TODO Edge contraction
- TODO Vertex 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

### 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 Construction of random graphs
- Since different kinds of vertex-edge distributions exists, separate distributions objects are used.
- See
`Graph::Distribution`

.

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

- This was the first version of
- DONE Watts–Strogatz model distribution
- DONE Uniform distribution

- Since different kinds of vertex-edge distributions exists, separate distributions objects are used.
- 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

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