Graph

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

Installation

From Zef ecosystem:

zef install Graph

From GitHub:

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

Usage examples

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

TODO

TODO Paths, cycles, flows

• DONE Shortest paths

  • DONE Find shortest path

  • DONE Find Hamiltonian paths

• TODO Flows

  • TODO Find maximum flow

  • TODO Find minimum cost flow

• TODO Distances

  • TODO Graph distance

  • TODO Graph distance matrix

• TODO Longest shortest paths

  • TODO Vertex eccentricity

  • TODO Graph radius

  • TODO Graph diameter

  • TODO Graph center

  • TODO Graph periphery

• TODO Topological paths

  • TODO Topological sort

• TODO Cycles and tours

  • TODO Find shortest tour

  • TODO Find postman tour

  • TODO Find Eulerian cycle

  • TODO Find Hamiltonian cycle

  • DONE Find cycle

    • Just one cycle

    • All cycles

  • 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 Edge contraction

  • TODO Line graph

  • TODO Dual graph

  • TODO Complement 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 Grid graphs

  • DONE Star graphs

  • DONE Wheel graphs

• DONE Construction of random graphs

  • Potentially very complicated, since different kinds of vertex-edge distributions exists.

  • DONE "Simple" random (m, n) graphs with m-vertexes and n-edges between them

• TODO Construction of individual graphs

  • TODO Bull graph

  • TODO Butterfly graph

  • TODO Chavatal graph

  • TODO Diamond graph

  • TODO Durer graph

  • TODO Franklin graph

  • TODO Petersen graph

  • TODO Wagner graph

Tests

• TODO Unit tests

  • DONE Sanity

  • DONE Undirected graphs

  • TODO Directed graphs cycles

• TODO Cross-verification with Mathematica

  • TODO General workflow programming/setup

  • TODO Path finding

  • TODO Cycle finding

Documentation

• DONE Basic usage over undirected graphs

• TODO Basic usage over directed graphs

• TODO Random graphs creation

• TODO Regular graphs creation (Grid, Wheel, etc.)

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.