Rand Stats

Graph

zef:antononcube

Graph

Actions Status Actions Status Actions Status

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

Design

Implementation

Visualization

Performance

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

Graph programming

Paths, cycles, flows

Matching, coloring

Operations

Construction

Tests

Documentation

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.