Yet Another Ruby Graph Implementation
Ruby Shell
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Yet Another Ruby Graph Library



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

Quick tour

Digraph, Vertex and Edge

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

Markable pattern

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 =
v1 = graph.add_vertex(:kind => "simple vertex")
puts v1.kind    
# => "simple vertex"

Typed elements

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 =
graph.add_n_vertices(5, Diamond) do |v,i|
  v[:color] = (i%2==0 ? 'red' : 'blue')

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

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

Selection mechanism

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

VertexSet and EdgeSet

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

Mutable graphs

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.

Complexity don't care

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.

Distribution & Credits

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

This work is supported by the { department of computer science} of the { 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).