Project

directed_graph

0.01
No commit activity in last 3 years
No release in over 3 years
directed_graphmrpowers/directed_graphHomepageDocumentationSource CodeBug TrackerWiki
Topological sorting, shortest path, and json exports for directed acyclic graphs
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
 Popularity
Downloads
16,667
Stars
14
Forks
1
Watchers
7
 Releases
Current version
0.6.1
Total releases
7
First release
2015-10-04
Latest release
2017-09-01
 Issues
Open Issues
2
Closed Issues
0
Total Issues
2
Issue Closure Rate
0%
 Pull Requests
Open Pull Requests
1
Closed Pull Requests
0
Merged Pull Requests
1
Pull Request Acceptance Rate
50%
 Development
Primary Language
Ruby
Licenses
MIT
Average date of last 50 commits
2015-12-18
Reverse Dependencies
1

 Dependencies

Development

bundler
~> 1.10
rake
~> 10.0
rspec
>= 0

Runtime

pry
>= 0
simple-graph
>= 0
 Project Readme

directed_graph

The directed_graph gem is useful for modeling directed, acyclic, unweighted graphs. It provides methods to topologically sort graphs, find the shortest path between two vertices, and render the graphs and json for client-side graphing.

The following graph will be used to demonstrate the functionality of the directed_graph gem.

graph_example

The Graph class should be instantiated with an array of edges:

# create the vertices
@root = Vertex.new(name: "root")
@a = Vertex.new(name: "a")
@b = Vertex.new(name: "b")
@c = Vertex.new(name: "c")
@d = Vertex.new(name: "d")
@e = Vertex.new(name: "e")

# The first argument is the origin_vertex
# and the second is the destination_vertex
@ra = Edge.new(origin_vertex: @root, destination_vertex: @a)
@ab = Edge.new(origin_vertex: @a, destination_vertex: @b)
@bc = Edge.new(origin_vertex: @b, destination_vertex: @c)
@bd = Edge.new(origin_vertex: @b, destination_vertex: @d)
@ae = Edge.new(origin_vertex: @a, destination_vertex: @e)
@de = Edge.new(origin_vertex: @d, destination_vertex: @e)
@edges = [@ra, @ab, @bc, @bd, @ae, @de]
@graph = Graph.new(@edges)

The @graph object can be used to get a topological sorted array of the vertices:

@graph.sorted_vertices # [@root, @a, @b, @d, @e, @c]

Here is an awesome blog post on topological sorting in Ruby with the TSort module.

The @graph object can also be used to calculate the shortest path between two vertices:

@graph.shortest_path(@root, @e) # [@root, @a, @e]
@graph.shortest_path(@root, Vertex.new(name: "blah")) # nil because the "blah" vertex doesn't exist
@graph.shortest_path(@d, @a) # nil because the graph is directed and can't be traversed in the wrong direction

The @graph object can be used to calculate the longest path between two vertices:

@graph.longest_path(@root, @e) # [@root, @a, @b, @d, @e]
@graph.longest_path(@a, @c) # [@a, @b, @c]
@graph.longest_path(@d, @a) # returns [] when the path doesn't exist

The @graph object can be used to generate a graphml file

require 'color-generator'

generator = ColorGenerator.new saturation: 0.3, lightness: 0.75

# Set the color and label of each vertex
#
@graph.vertices.each do |vertex|
  color = generator.create_hex
  label = vertex.name

  vertex.data[:graphics]  = {:fill=>["##{color}"], :label=>[label], :group=>color}
end

# Generate a graphml file
# Import this file into program like yEd to size nodes and layout graph
File.open("output.graphml", "w+") { |f| f.write(@graph.to_graphml())}

Installation

Add this line to your application's Gemfile:

gem 'directed_graph'

Require the gem in your code:

require 'directed_graph'

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/MrPowers/directed_graph.

License

The gem is available as open source under the terms of the MIT License.