Graph

Common graph functionalities.

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

Graph v0.0.1

Common graph functionalities.

Authors

  • Anton Antonov

License

Artistic-2.0

Dependencies

Hash::Merge:ver<2.0.0>:auth<github:scriptkitties>:api<2>

Test Dependencies

Provides

  • Graph
  • Graph::Complete
  • Graph::Cycle
  • Graph::Grid
  • Graph::Random
  • Graph::Star
  • Graph::Wheel

The Camelia image is copyright 2009 by Larry Wall. "Raku" is trademark of the Yet Another Society. All rights reserved.