Graphunk

Graphunk defines simple and fully-tested graph classes in Crystal which you can use to perform graph-theoretical operations.

Defining a Graph

Unweighted Graphs

Graphs are internally represented as an Array of vertices and an Array of edges:

Graphunk::UndirectedGraph(String).new(
  ["a", "b", "c", "d"],
  [{"a", "b"}, {"a", "c"}, {"b", "c"}]
)

In an undirected graph, edges are not represented redundantly. The add_edge method takes care of ordering automatically.

In a directed graph, the order in an edge matters. A construction of a directed graph might look like this:

Graphunk::DirectedGraph(String).new(
  ["a", "b", "c", "d"],
  [{"a", "b"}, {"a", "c"}, {"b", "a"}, {"b", "d"}]
)

Graphs can also be built by individually adding edges and vertices.

graph = Graphunk::UndirectedGraph(String).new
graph.add_vertex("a")
graph.add_vertex("b")
graph.add_edge("a", "b")

Weighted Graphs

Weighted graphs have an additional property: each edge must specify a numerical weight.

To construct a weighted graph, you must pass in the vertex and edge information as well as the weights:

Graphunk::WeightedDirectedGraph(String).new(
  ["a", "b", "c", "d", "e"],
  {
    {"a", "b"} => 3,
    {"a", "c"} => 6,
    {"a", "e"} => 6,
    {"b", "c"} => 2,
    {"b", "d"} => 7,
    {"c", "d"} => 3,
    {"d", "a"} => 4
  }
)

You can also build them by adding vertices and edges.

  graph = Graphunk::WeightedUndirectedGraph(String).new
  graph.add_vertex("a")
  graph.add_vertex("b")
  graph.add_edge("a", "b", 3)

Now the edge a-b will have a weight of 3.

WeightedDirectedGraph behaves similarly.

Testing

To run the test suite simply execute:

crystal spec

Future Work

• More algorithms
• Make the Graph constructor more "safe"
• Support for flow networks

Credits

All code (c) Evan Hemsley 2014-2018

Special thanks to Mitchell Gerrard for inspiring this project.