Yargi

Yet Another Ruby Graph Library

• http://rubydoc.info/github/blambeau/yargi/master/frames
• http://github.com/blambeau/yargi
• http://rubygems.org/gems/yargi

Yargi provides a powerful mutable digraph implementation. It has been designed to allow full mutability the easy way. A quick tour below.

Unlike {http://rubyforge.org/projects/rgl/ RGL}, Yargi implements graph components through concrete classes, not modules (that is, in a standard-but-closed way). See Digraph, Digraph::Vertex and Digraph::Edge respectively.

Graphs, vertices and edges are markable through a Hash-like API: users can install their own key/value pairs on each graph element. When keys are Symbol objects, accessors are automatically generated to provide a friendly object-oriented API (this feature must be used with care, for obvious reasons).

graph = Yargi::Digraph.new
v1 = graph.add_vertex(:kind => "simple vertex")
puts v1.kind    
# => "simple vertex"

Graph elements (vertices and edges) can be tagged with your own modules (at creation, or later). This is the standard Yargi way to apply a 'select-and-do' feature described below:

# These are node types
module Diamond; end
module Circle; end

# Let build a graph with 5 diamonds
graph = Yargi::Digraph.new
graph.add_n_vertices(5, Diamond) do |v,i|
  v[:color] = (i%2==0 ? 'red' : 'blue')
end

# Let add 5 circles
graph.add_n_vertices(5, Circle)

# connect all diamonds to all circles
graph.connect(Diamond, Circle)  

Yargi helps you finding the nodes and edges you are looking for through a declarative selection mechanism: almost all methods that return a set of vertices or edges (Vertex.out_edges, for example) accept a predicate argument to filter the result, module names being most-used shortcuts. See Yargi::Predicate for details.

# [... previous example continued ...]
graph.vertices(Diamond)                       # selects all diamonds
graph.vertices(Diamond){|v| v.color=='blue'}  # selects blue diamonds only

# Proc variant, find sink states
sink = Yargi.predicate {|v| v.out_edges.empty?}
graph.vertices(sink & Circle)                 # select all Circle sink states (no one)

# Or selection
is_blue = Yargi.predicate {|v| Diamond===v and v.color=='blue'}
graph.vertices(is_blue|Circle)                # select blue diamonds and circles

The selection mechanism always returns arrays ... being instances of Yargi::VertexSet and Yargi::EdgeSet. These classes help you walking your graph easily:

# [... previous example continued ...]
circles = graph.vertices(Diamond).adjacent
puts graph.vertices(Circle)==circles        
# => true

Many graph methods accept sets of vertices and edges as well as selection queries to work. Instead of connecting one source to one target at a time by passing the vertices, describe what you want and Yardi does it. Add, connect, remove, mark, reconnect many vertices/edges with a single method call:

graph.vertices(Diamond).add_marks(:label => '', :shape => 'diamond')
graph.vertices(Circle).add_marks(:label => '', :shape => 'circle')
puts graph.to_dot
graph.remove_vertices(Circle) # remove all circles

Graphs here are mutable, mutable and mutable and this is the reason why Yargi exists. It comes from a project where manipulating graphs by reconnecting edges, removing vertices is the norm, not the exception.

The digraph implementation uses an incident list data structure. This graph library has not been designed with efficiency in mind so that complexities are not documented nor guaranteed. That is not to say that improvements are not welcome, of course.

Yargi is freely available (under a MIT licence) as a 'yargi' gem on {http://rubygems.org/gems/yargi rubygems.org}. Use 'gem install yargi' to install it. The sources are on {http://github.com/blambeau/yargi github}, which is also the place where bugs and issues can be reported.

This work is supported by the {http://www.uclouvain.be/en-ingi.html department of computer science} of the {http://www.uclouvain.be/en-index.html University of Louvain} (EPL/INGI, Universite Catholique de Louvain, UCL, Louvain-la-Neuve, Belgium).

This work was also partially supported by the Regional Government of Wallonia (GISELE project, RW Conv. 616425).