Repository files navigation

RGL is a framework for graph data structures and algorithms.

The design of the library is much influenced by the Boost Graph Library (BGL)which is written in C++. Refer tohttps://www.boost.org/libs/graph/doc forfurther links and documentation on graph data structures and algorithms andthe design rationales of BGL.

A comprehensive summary of graph terminology can be found in the graph sectionof theDictionary of Algorithms and Data Structures athttps://www.nist.gov/dads/HTML/graph.html orWikipedia.

• GitHub Repository
• API Reference generated from master branch
• API Reference athttps://rubydoc.info for the latest release

This document concentrates on the special issues of the implementation inRuby. The main design goals directly taken from the BGL design are:

• An interface for how the structure of a graph can be accessed using ageneric interface that hides the details of the graph data structureimplementation. This interface is defined by the module {RGL::Graph},which should be included in concrete classes.

• A standardized generic interface for traversing graphs{RGL::GraphIterator}

RGL provides some general purpose graph classes that conform to thisinterface, but they are not meant to be theonly graph classes. As in BGLI believe that the main contribution of the RGL is the formulation of thisinterface.

The BGL graph interface and graph components are generic in the sense of theC++ Standard Template Library (STL). In Ruby other techniques are available toexpress the generic character of the algorithms and data structures mainlyusing mixins and iterators. The BGL documentation mentions three means toachieve genericity:

• Algorithm/Data-Structure Interoperability
• Extension through Function Objects and Visitors
• Element Type Parameterization
• Vertex and Edge Property Multi-Parameterization

The first is easily achieved in RGL using mixins, which of course is not asefficient than C++ templates (but much more readable :-). The second one iseven more easily implemented using standard iterators with blocks or using thestream module. The third oneis no issue since Ruby is dynamically typed: Each object can be a graphvertex. There is no need for a vertex (or even edge type). In the currentversion of RGL properties of vertices are simply attached using hashes. Atfirst there seems to be not much need for the graph property machinery.

RGL current contains a core set of algorithm patterns:

• Breadth First Search {RGL::BFSIterator}
• Depth First Search {RGL::DFSIterator}

The algorithm patterns by themselves do not compute any meaningful quantitiesover graphs, they are merely building blocks for constructing graphalgorithms. The graph algorithms in RGL currently include:

• Topological Sort {RGL::TopsortIterator}
• Connected Components {RGL::Graph#each_connected_component}
• Strongly Connected Components {RGL::Graph#strongly_connected_components}
• Transitive Closure {RGL::Graph#transitive_closure}
• Dijkstras Shortest Path Algorithm {RGL::DijkstraAlgorithm}
• Bellman Ford Algorithm {RGL::BellmanFordAlgorithm}

RGL currently provides two graph classes that implement a generalizedadjacency list and an edge list adaptor.

• {RGL::AdjacencyGraph}
• {RGL::ImplicitGraph}

The AdjacencyGraph class is the general purposeswiss army knife of graphclasses. It is highly parameterized so that it can be optimized for differentsituations: the graph is directed or undirected, allow or disallow paralleledges, efficient access to just the out-edges, fast vertex insertion andremoval at the cost of extra space overhead, etc.

The concepts of IncidenceGraph, AdjacencyGraph and VertexListGraph(seeIncidenceGraph) arebundled in RGL's base graph module. Most methods of IncidenceGraphshould be standard in the base module Graph. The complexity guaranteescan not necessarily provided (seeBGL's Graph Concepts).

% gem install rgl

or download the latest sources from thegitrepository.

If you are going to use the drawing functionalities installGraphviz.

Checkout RGL git repository and go to the project directory. First, installRGL dependencies with bundler:

% bundle install

After that you can run the tests:

% rake test

% irb -Ilibirb> require 'rgl/adjacency'irb> dg=RGL::DirectedAdjacencyGraph[1,2 ,2,3 ,2,4, 4,5, 6,4, 1,6]# Use DOT to visualize this graph:irb> require 'rgl/dot'irb> dg.write_to_graphic_file('jpg')"graph.jpg"

The result:

You can control the graph layout by passing layout parameters towrite_to_graphic_file. SeeTestDot::test_to_dot_digraph_with_options for an example using a feature implemented by LiaSkalkos (seePR #41).

irb> dg.directed?trueirb> dg.vertices[5, 6, 1, 2, 3, 4]irb> dg.has_vertex? 4true

Every object could be a vertex (there is no class Vertex), even the classobjectObject:

irb> dg.has_vertex? Objectfalseirb> dg.edges.sort.to_s"(1-2)(1-6)(2-3)(2-4)(4-5)(6-4)"irb> dg.to_undirected.edges.sort.to_s"(1=2)(1=6)(2=3)(2=4)(5=4)(6=4)"

Add inverse edge (4-2) to directed graph:

irb> dg.add_edge 4,2

(4-2) == (2-4) in the undirected graph:

irb> dg.to_undirected.edges.sort.to_s"(1=2)(1=6)(2=3)(2=4)(5=4)(6=4)"

(4-2) != (2-4) in directed graphs:

irb> dg.edges.sort.to_s"(1-2)(1-6)(2-3)(2-4)(4-2)(4-5)(6-4)"irb> dg.remove_edge 4,2true

Check whether a path exists between vertices 1 and 5

irb> require 'rgl/path'irb> dg.path?(1, 5)true

Topological sort is implemented as an iterator:

require 'rgl/topsort'irb> dg.topsort_iterator.to_a[1, 2, 3, 6, 4, 5]

A more elaborated example showingimplicit graphs:

require 'rgl/implicit'def module_graph  RGL::ImplicitGraph.new { |g|    g.vertex_iterator { |b|      ObjectSpace.each_object(Module, &b)    }    g.adjacent_iterator { |x, b|      x.ancestors.each { |y|        b.call(y) unless x == y || y == Kernel || y == Object      }    }    g.directed = true  }end

This function creates a directed graph, with vertices being all loadedmodules:

g = module_graph

We only want to see the ancestors of {RGL::AdjacencyGraph}:

require 'rgl/traversal'tree = g.bfs_search_tree_from(RGL::AdjacencyGraph)

Now we want to visualize this component of g with DOT. We therefore create asubgraph of the original graph, using a filtered graph:

g = g.vertices_filtered_by {|v| tree.has_vertex? v}g.write_to_graphic_file('jpg')

creates the following graph image with DOT:

This graph shows all loaded RGL modules:

Look for more inexamples directory.

The default graph will use standard DOT output visuals.

If you wish to configure the styling of the diagram, module {RGL::DOT} adds the methods {RGL::Graph#set_edge_options} and {RGL::Graph#set_vertex_options} for this purpose. You can use any options from the {RGL::DOT::NODE_OPTS} and {RGL::DOT::EDGE_OPTS} constants in {RGL::DOT}. Use the exact option name as an argument in your method call.

You can also configure the overall appearance of the graph by passing a hash of options from {RGL::DOT::GRAPH_OPTS} to the output method. The example below shows styling of vertices, edges and setting some basic graph options.

The available options are described in theGraphViz DOT Spec

require'rgl/adjacency'require'rgl/dot'graph=RGL::DirectedAdjacencyGraph['a','b','c','d','a','c']graph.set_vertex_options('a',label:'This is A',shape:'box3d',fontcolor:'green',fontsize:16)graph.set_vertex_options('b',label:'This is B',shape:'tab',fontcolor:'red',fontsize:14)graph.set_vertex_options('c',shape:'tab',fontcolor:'blue')graph.set_edge_options('a','b',label:'NotCapitalEdge',style:'dotted',dir:'back',color:'magenta')graph.set_edge_options('a','c',weight:5,color:'blue')graph_options={"rankdir"=>"LR","labelloc"=>"t","label"=>"Graph\n (generated#{Time.now.utc})"}graph.write_to_graphic_file('png','graph',graph_options)

Many thanks to Robert Feldt which also worked on a graph library(https://rockit.sf.net/subprojects/graphr) who pointed me to BGL and many othergraph resources.

Robert kindly allowed to integrate his work on graphr, which I did not yetsucceed. Especially his work to output graphs forGraphViz is much more elaborated than the minimalsupport in dot.rb.

Jeremy Siek one of the authors of the nice bookThe Boost GraphLibrary kindly allowed to use the BGLdocumentation as acheap reference for RGL. He and Robert also gave feedbackand many ideas for RGL.

Dave Thomas forRDoc which generated what youread and matz for Ruby. Dave included in the latest version of RDoc (alpha9)the module {RGL::DOT} which is used instead of Roberts module to visualizegraphs.

Jeremy Bopp, John Carter, Sascha Doerdelmann, Shawn Garbett, Andreas Schörk, DanČermák, Kirill Lashuk and Markus Napp for contributing additions, test cases andbugfixes. The complete list of contributers ishere.

• See {file:CHANGELOG.md} for major/breaking updates.
• Tocontribute, please read {file:.github/CONTRIBUTING.md} first.
• Pleaseopen an issue if anythingis missing or unclear in this documentation.

RGL is Copyright (c) 2002,2004,2005,2008,2013,2015,2019,2020,2022,2023 by HorstDuchene. It is free software, and may be redistributed under the {file:LICENSE}and terms specified in the LICENSE file.