Crystal Graph Library (CGL)

CGL is a Crystal library for the creation and manipulation of graph data structures.

All graph data structures are based on an adjacency list representation and heavily rely on Crystal Hash data structure.

Features

• Data structures for graphs, digraphs and multigraphs
• Nodes can be anything
• Edges can be weighted and/or hold arbitrary data as labels
• Generic interface for accessing concrete data structures (see CGL::IGraph)
• Generic interface for traversing graphs (iterators, visitor)
• Standard graph algorithms
• Support hypergraphs

Documentation

• API

Installation

1. Add the dependency to your shard.yml:

   dependencies:
     cgl:
       github: RomainFranceschini/cgl
   

2. Run shards install

Usage

Import the CGL module with :

require "cgl"

Directed and undirected graphs types are provided. For each of those, multiple variants are offered so users can carefully select the ones that consume the least memory for their needs.

Undirected graphs

The following classes all implements undirected graphs. They allow self-loop edges that connects a vertex to itself. They ignore multiple edges between two vertices.

• The Graph class implements an undirected graph. Edges cannot be weighted nor labeled.

  g = Graph(Char).new(edges: { {'a','b'}, {'a','f'}, {'f','b'} })
  g.add_edge 'b', 'b'
  g.add_vertex 'e'
  g.order # => 5
  g.size  # => 4
  

• The WeightedGraph class implements an undirected graph where edges can be weighted with a Number::Primitive type.

  g = WeightedGraph(Char, Int32).new(default_weight: 10)
  g.add_edge 'b', 'b', 1
  g.add_edge 'a', 'b'
  g.weight_of('b', 'b') # => 1
  g.weight_of('a', 'b') # => 10
  

• The LabeledGraph class implements an undirected graph where edges can be labeled, e.g. they can hold arbitrary data of any chosen type.

  g = LabeledGraph(String, Char).new(default_label: '👀')
  g.add_edge "hello", "world", label: '👍'
  g.add_edge "hello", "folks", label: '👎'
  g.add_edge "hello", "martians"
  g.label_of("hello", "martians") # => 👀
  

• Finally, the WeightedLabeledGraph class implements an undirected graph where edges can both be weighted and labeled. Yay!

  g = WeightedLabeledGraph(String, Char).new(default_weight: 10, default_label: '👀')
  g.add_edge "hello", "world", weight: 1, label: '👍'
  g.add_edge "hello", "folks", label: '👎'
  

Directed graphs

The following classes all implements directed graphs. They allow self-loop edges, that connects a vertex to itself. They ignore multiple edges between two vertices.

• The DiGraph class implements a directed graph. Edges cannot be weighted nor labeled.

  g = DiGraph(Char).new(edges: { {'a','b'}, {'a','c'}, {'c','b'} })
  

• The WeightedDiGraph class implements a directed graph where edges can be weighted with a Number::Primitive type.

  g = WeightedDiGraph(Char, UInt8).new(default_weight: 1u8)
  

• The LabeledDiGraph class implements a directed graph where edges can be labeled, e.g. they can hold arbitrary data of any chosen type.

  g = LabeledDiGraph(String, Char).new(default_label: '👀')
  g.add_edge "hello", "world", label: '👍'
  

• Finally, the WeightedLabeledDiGraph class implements a directed graph where edges can both be weighted and labeled. Yay!

  g = WeightedLabeledDiGraph(String, Char).new(default_weight: 10, default_label: '👀')
  

Multigraphs and Hypergraphs

TBD

Contributing

1. Fork it (https://github.com/RomainFranceschini/cgl/fork)
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Add some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create a new Pull Request

Contributors

• Romain Franceschini - creator and maintainer