Graphunk
Graphunk defines simple and fully-tested graph classes in Ruby which you can use to perform graph-theoretical operations.
Defining a Graph
Unweighted Graphs
Graphs are internally represented as a hash, so you can define a graph similarly to how you would define a Hash:
Graphunk::UndirectedGraph.new({
'a' => ['b','c'],
'b' => ['c', 'd', 'e'],
'c' => ['d'],
'd' => ['e'],
'e' => []
})
Each key is a string representing a vertex, and the value is a list of strings which represent neighbor vertices of the key.
In an undirected graph, edges are not represented redundantly, meaning that the edge a-b in the above case is defined by "b" being a member of "a's" list, but "a" is not a member of "b's" list. 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.new({
'a' => ['b','c'],
'b' => ['a'],
'c' => ['d'],
'd' => []
})
Graphs can also be built by individually adding edges and vertices.
graph = Graphunk::UndirectedGraph.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::WeightedUndirectedGraph.new({
'a' => ['b','c'],
'b' => ['c', 'd', 'e'],
'c' => ['d'],
'd' => ['e'],
'e' => []
},
{
['a','b'] => 2,
['a','c'] => 4,
['b','c'] => 1,
['b','d'] => 4,
['b','e'] => 7,
['c','d'] => 4,
['d','e'] => 3
})
You can also build them by adding vertices and edges.
graph = Graphunk::WeightedUndirectedGraph.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:
rspec
Future Work
- More algorithms
- Make the Graph constructor more "safe"
- Support for flow networks
Credits
All code (c) Evan Hemsley 2014
Special thanks to Mitchell Gerrard for inspiring this project.