monora / rgl Goto Github PK
View Code? Open in Web Editor NEWRGL is a framework for graph data structures and algorithms in Ruby.
Home Page: https://monora.github.io/rgl/
License: Other
RGL is a framework for graph data structures and algorithms in Ruby.
Home Page: https://monora.github.io/rgl/
License: Other
Hi - thanks for supporting a great library.
We're thinking of using rgl on one of our projects and we were wondering whether it's thread safe?
Thanks
The following test currently fails for bfs_iterator:
def test_bfs_stream_protocol
it = @dg.bfs_iterator(1)
assert_true(it.at_beginning?)
it.set_to_end()
assert_true(it.at_end?)
it.set_to_begin()
# Initial state is not correctly set. Therefor this check fails:
assert_true(it.at_beginning?)
end
Either the documentation is incomplete or I'd expect a depth_first result in the case below:
Is there any code which does sort the edges to force the desired result?
require 'rgl/adjacency'
require 'rgl/traversal'
# sample graph DAG, two roots:
#1
# 2
# 3
#4
# 5
# 6
graph = RGL::DirectedAdjacencyGraph[
# starting with a non root node
5,6, 4,5,
1,2, 2,3
]
graph.depth_first_search {|v|
puts v
}
# output:
# || 6
# || 5
# || 4
# || 3
# || 2
# || 1
# I'd expect it to start with either 1 or 4
I've just recently started using this to automatically generate some overview diagrams for file relationships but I'm running into some problems with placing the nodes in a human readable way. I find subgraphs over and over to possibly be the solution. Does the library in the current state support subgraphs and/or clustered nodes? The documentation is not conclusive on this.
Hi!
I tried to use:
visitor = @rgl_graph.dfs_iterator(@root_vertex_id)
visitor.attach_distance_map(@rgl_edge_weights)
visitor.set_examine_vertex_event_handler { |v|
puts ">>> Visitor: #{v}"
}
@rgl_graph.depth_first_search(visitor) {
puts ">>> DFS handler: #{v}"
}
But if fails with an exception saying
undefined method `handle_start_vertex' for #<RGL::DFSIterator:0x000000010f5f08d8 @graph=#<RGL::DirectedAdjacencyGraph:0x000000010f5f1a08 @edgelist_class=Set, @vertices_dict={"1039ea5f-2b61-450a-8f38-16d9443295ca"=>#<Set: {}>, "9fbc9bdb-0270-4f64-8e7a-864d2ce7f17c"=>#<Set: {"1039ea5f-2b61-450a-8f38-16d9443295ca"}>}>, @color_map={"1039ea5f-2b61-450a-8f38-16d9443295ca"=>:GRAY}, @start_vertex="1039ea5f-2b61-450a-8f38-16d9443295ca", @waiting=["1039ea5f-2b61-450a-8f38-16d9443295ca"], @distance_map=[{["9fbc9bdb-0270-4f64-8e7a-864d2ce7f17c", "1039ea5f-2b61-450a-8f38-16d9443295ca"]=>8.73408059691218}], @examine_vertex_event_handler=#<Proc:0x000000010f5f0540
Which leads to:
Line 182 in 731c562
When I use content of depth_first_search
method directly (minus handle_start_vertex
part) it looks like it works
@rgl_graph.each_vertex do |u|
unless visitor.finished_vertex?(u)
@rgl_graph.depth_first_visit(u, visitor) { |v|
puts ">>> DFS handler: #{v}"
}
end
end
I'm trying to figure out how to use this method with no luck. I'm a bit new to Ruby but as far as I can tell AdjacencyGraph
should mix in this method by virtue of inheriting from DirectedAdjacencyGraph
and its mix-ins. Here is a session of me trying to make a trivial graph and then access the method:
[1] pry(main)> require 'rgl/adjacency'
=> true
[2] pry(main)> RGL::AdjacencyGraph
RGL::AdjacencyGraph
[2] pry(main)> g = RGL::AdjacencyGraph.new
=> #<RGL::AdjacencyGraph:0x000055820af89cd8 @edgelist_class=Set, @vertices_dict={}>
[3] pry(main)> g.add_edge(:a, :b)
=> #<Set: {:a}>
[4] pry(main)> g.add_edge(:b, :d)
=> #<Set: {:b}>
[5] pry(main)> g
=> #<RGL::AdjacencyGraph:0x000055820af89cd8 @edgelist_class=Set, @vertices_dict={:a=>#<Set: {:b}>, :b=>#<Set: {:a, :d}>, :d=>#<Set: {:b}>}>
[6] pry(main)> g.add_edge(:b, :c)
=> #<Set: {:b}>
[7] pry(main)> g.add_edge(:c, :e)
=> #<Set: {:c}>
[8] pry(main)> g.edges
=> [(a-b), (b-d), (b-c), (c-e)]
[9] pry(main)> g.bellman_ford_shortest_paths
NoMethodError: undefined method `bellman_ford_shortest_paths' for #<RGL::AdjacencyGraph:0x000055820af89cd8>
from (pry):9:in `__pry__'
I'm also not sure how edge_weights_map
is specified.
Suppose we have the following graph containing 3 vertices:
class Person
attr_reader :name
def initialize(name)
@name = name
end
def to_s
name
end
end
dg=RGL::DirectedAdjacencyGraph.new
dg.add_vertex(Person.new("Alice"))
dg.add_vertex(Person.new("Bob"))
dg.add_vertex(Person.new("Alice"))
When the graph is visualised via dg.write_to_graphic_file('jpg')
it has only two vertices:
Ruby 3.2 ist released:
https://www.ruby-lang.org/en/news/2022/12/25/ruby-3-2-0-released/
I ran the below example from the readme verbatim, and I did not got a graph.jpg
file, instead it created a graph.dot
file.
irb> 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"
We have been asked to review the licences of gems we use. Can we get clarification of the licence for rgl
? Thank you!
David Inman filed this bug at rubyforge
http://rubyforge.org//tracker/?func=detail&atid=511&aid=29788&group_id=110
Conditions:
irb(main):001:0> require 'rgl/implicit'
=> true
irb(main):002:0> def module_graph
irb(main):003:1> RGL::ImplicitGraph.new { |g|
irb(main):004:2* g.vertex_iterator { |b|
irb(main):005:3* ObjectSpace.each_object(Module, &b)
irb(main):006:3> }
irb(main):007:2> g.adjacent_iterator { |x, b|
irb(main):008:3* x.ancestors.each { |y|
irb(main):009:4* b.call(y) unless x == y || y == Kernel || y == Object
irb(main):010:4> }
irb(main):011:3> }
irb(main):012:2> g.directed = true
irb(main):013:2> }
irb(main):014:1> end
=> nil
irb(main):015:0> g = module_graph
ArgumentError: comparison of RGL::Edge::DirectedEdge with RGL::Edge::DirectedEdge failed
from /home/davei/.gem/ruby/1.9.3/gems/rgl-0.4.0/lib/rgl/base.rb:193:in sort' from /home/davei/.gem/ruby/1.9.3/gems/rgl-0.4.0/lib/rgl/base.rb:193:in
to_s'
from /usr/pack/ruby-1.9.3-jn/x86_64-Linux-2.6/bin/irb:12:in `
code snippet from base.rb:
# Utility method to show a string representation of the edges of the graph.
def to_s
edges.sort.to_s # <<<<----- line 193 >>>>
end
This looks like a fantastic piece of work. I'm excited to use it.
Thanks,
Dave
There have been a handful of changes since the last tagged version, and a v0.6.0 would be nice.
Would it be possible to bump the algorithms gem to 6.x? I think they added support for JRuby. It would be awesome to have this great gem available for JRuby as well.
> @monora This causes a downgrade from v3.0.1 to v0.3.0. Was that intentional?
No, but it is fixed by PR #119. I will release a new version containing the fix. Thank you!
Originally posted by @monora in #112 (comment)
hello . i work with big tree in multi level marketing with php with model it work good but i have issue for big tree about 1M branch , do you can help me or way for work with fast speed ?
There is some really strange error in dijkstra_shortest_path (or I am missing something very obvious).
irb(main):001:0> require 'rgl/adjacency'
=> true
irb(main):002:0> require 'rgl/dijkstra'
=> true
irb(main):003:0> g = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32, 32,58, 58,44, 44,53]
=> #<RGL::AdjacencyGraph:0x00000001c6ff88 @edgelist_class=Set, @vertices_dict={2=>#<Set: {53, 3}>, 53=>#<Set: {2, 44}>, 3=>#<Set: {2, 8, 28, 39}>, 8=>#<Set: {3, 35}>, 28=>#<Set: {3}>, 39=>#<Set: {3, 12}>, 29=>#<Set: {58, 10}>, 58=>#<Set: {29, 32, 44}>, 35=>#<Set: {8}>, 12=>#<Set: {39}>, 10=>#<Set: {29}>, 62=>#<Set: {15}>, 15=>#<Set: {62, 32}>, 32=>#<Set: {15, 58}>, 44=>#<Set: {58, 53}>}>
irb(main):004:0> g.dijkstra_shortest_path(Hash.new(1),53,62)
=> nil
But there is a path [53, 44, 58, 32, 15, 62]. I tried to minimalize the graph furher, but strangely after removing any edge it suddenly behaves correctly (either finds path or not when there is not one).
PS: I can fork the repo and request pull with the test, if it helps.
It seems to me that the README is somehow outdated. Namely first example did not generate any jpg for me (only dot text file) and second one returned (after dg.edges.sort.to_s
) something like
"[#<RGL::Edge::UnDirectedEdge:0x000000029867f8 @source=1, @target=2>, #<RGL::Edge::UnDirectedEdge:0x00000002986618 @source=3, @target=4>, #<RGL::Edge::UnDirectedEdge:0x00000002986438 @source=5, @target=6>]"
instead of textual representation of the graph.
A bug reported by Sean Harger:
require 'rgl/adjacency'
require 'rgl/dot'
g = RGL::AdjacencyGraph[1,2]
g.write_to_graphic_file
Error: graph.dot:1: syntax error near line 1
context: >>> subgraph <<< RGL__AdjacencyGraph {
=> "graph.png"
Reproduced with ruby version 1.9.3 and RGL 0.4.0
I botched both the code and the test. Pull request coming.
When i try to install it via gem install rgl
, my version is 0.5.1.
It still has problems with heap fixed in master. So, is there a plan for release ?
I see it mentioned in the examples, but I couldn't find it in the code...
thanks
Hi there,
We're using rgl
in one of our apps, but it appears the Enumerable extension in lib/rgl/enumerable_ext.rb
is breaking some unrelated libraries ๐ข.
The underlying problem is that you'd normally expect length
to be an idempotent method (e.g. calling 'some string'.length
doesn't change the string), and this assumption is present in various libraries, including the AWS SDK (that's where we are having issues ๐, but it's likely this isn't the only library that calls #length
): https://github.com/aws/aws-sdk-ruby/blob/589f8cd569d3c365189945dd2e7a10bc9df775ea/lib/aws/s3/data_options.rb#L100
This turns out to be a problem when you provide an enumerable whose inject
method isn't idempotent.
In our case, we're passing an IO Pipe to the AWS SDK, which is enumerable. As a result, the AWS SDK calls #length
on the pipe since it appears to respond to that method (because #length
is defined by RGL), and then the pipe ends up exhausted when it later tries to read from it (and bad things ensue).
This method appears to be only used on TopsortIterator
; perhaps it could be defined there (or in GraphIterator
if it's moe generally useful)?
Thanks!
At the end of the README.md there's the text
RGL is Copyright (c) 2002,2004,2005,2008,2013,2015,2019
by Horst Duchene. It is free software, and may be redistributed
under the terms specified in the README file of the Ruby distribution.
but it does not really specify, whether the "free software"
is licensed under something as restrictive as the GPL or
is it licensed under something BSD-like. I suggest the use of
The idea is that at each source code there is a
special string, a license label, as part of the source code header.
That label duplicates the human-readable license information.
For example, for one of the variants of the BSD license the string is:
SPDX-License-Identifier: BSD-3-Clause-Clear
As of 2020_12_04 the list of different license IDs can be found from
In the current implementation the user will use the methods set_vertex_options
and set_edge_options
location in dot.rb
to set the options for the respective element of the graph. For this to work properly the user needs to initialize two procs and two hashes with all the options they want to use.
require 'rgl/adjacency'
require 'rgl/dot'
graph = RGL::DirectedAdjacencyGraph['a', 'b', 'b', 'c']
graph.add_edge('a', 'b')
graph.add_edge('a', 'c')
# Vertex Settings
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')
# Edge Settings
graph.set_edge_options('a', 'b', label: 'NotCapitalEdge', style: 'dotted', direction: 'back', color: 'yellow')
graph.set_edge_options('a', 'c', weight: 5, color: 'blue')
# puts @vertex_options
# puts @edge_options
get_vertex_setting = proc { |v| graph.vertex_options[v] }
get_edge_setting = proc { |b, e| graph.edge_options[graph.edge_class.new(b, e)] }
# To configure more options, add the respective keys and the proc call here
# Then provide the respective key:value to set_vertex_options
# Any hard coded values for a key will be applied to all nodes
vertex_options = {
'label' => get_vertex_setting,
'shape' => get_vertex_setting,
'fontcolor' => get_vertex_setting,
'fontsize' => get_vertex_setting
}
# To configure more options, add the respective keys and the proc call here
# Then provide the respective key:value to set_edge_options
# Any hard coded values for a key will be applied to all edges
edge_options = {
'label' => get_edge_setting,
'dir' => get_edge_setting,
'color' => get_edge_setting,
'style' => get_edge_setting,
'weight' => get_edge_setting,
'constraint' => get_edge_setting,
'headlabel' => get_edge_setting,
'taillabel' => get_edge_setting
}
# Options
dot_options = { 'edge' => edge_options, 'vertex' => vertex_options }
graph.write_to_graphic_file('png', 'graph', dot_options)
We should move vertex_options
and edge_options
and the respective procs somewhere into the initialize phase for the graph so they get populated with all valid options automatically and the user does not have to concern themselves with it and just pass the respective option combination to the methods. I have not yet found the right place in the classes where this would apply to all graph types and can be used properly.
Several class comments are overwritten by a comment line of the previous
class/module in the same file.
Fix: classes and modules in the same should be separated with at least two blank
lines!
The following code
g = RGL::AdjacencyGraph[9,14, 13,19, 17,20, 2,25, 10,25, 4,25, 23,25, 22,25, 9,22, 13,21, 6,17, 2,7, 3,10, 4,11, 5,23]
g.dijkstra_shortest_path(Hash.new(1),25,14)
fails with "RuntimeError: Couldn't delete node from stored nodes hash" with backtrace:
# /var/lib/gems/2.1.0/gems/algorithms-0.6.1/lib/containers/heap.rb:236:in `pop'
# /var/lib/gems/2.1.0/gems/rgl-0.5.1/lib/rgl/dijkstra.rb:64:in `relax_edges'
# /var/lib/gems/2.1.0/gems/rgl-0.5.1/lib/rgl/dijkstra.rb:32:in `shortest_path'
# /var/lib/gems/2.1.0/gems/rgl-0.5.1/lib/rgl/dijkstra.rb:141:in `dijkstra_shortest_path'
I appreciate this library exists, but I could not use it
ruby-3.2.2
Rails 7.1.2
Mac M1
rails new testrgl --api --skip-action-mailer --skip-action-cable --skip-test --skip-active-record
gem install rgl
irb/rails console
require 'rgl'
=> .rvm/rubies/ruby-3.2.2/lib/ruby/site_ruby/3.2.0/rubygems/core_ext/kernel_require.rb>:38:in `require': cannot load such file -- rgl (LoadError)
RGL # or any RGL constant
=> (irb):1:in `<main>': uninitialized constant RGL (NameError)
I was too clever by half in thinking that the reverse graph doesn't need to mirror unconnected vertices. It does.
Pull request coming.
Hi there,
Just curious if you had plans to make a new Rubygems release?
We have a library we'd like to open-source that depends on rgl, but would like to ensure that users that adopt this library don't run into this (fixed) bug: #36 ๐
Thanks!
When I execute the snippet from https://github.com/monora/rgl/blob/master/README.md#optional-configuring-graphviz-dot-output-options I get the follwing error
dot.rb:6:in `<main>': undefined method `set_vertex_options' for #<RGL::DirectedAdjacencyGraph:0x00000001044a3e18 @edgelist_class=Set, @vertices_dict={"a"=>#<Set: {"b", "c"}>, "b"=>#<Set: {}>, "c"=>#<Set: {"d"}>, "d"=>#<Set: {}>}> (NoMethodError)
graph.set_vertex_options('a', label: 'This is A', shape: 'box3d', fontcolor: 'green', fontsize: 16)
What am I missing?
require 'rgl/adjacency'
require 'rgl/dot'
puts RGL::DirectedAdjacencyGraph["a", "b"].to_dot_graph
Output:
digraph RGL__DirectedAdjacencyGraph {
70319033367680 [
fontsize = 8,
label = a
]
70319033367400 [
fontsize = 8,
label = b
]
70319033367680 -> 70319033367380 [
fontsize = 8
]
}
Note the extra node; the "b" node is given a new name in the edge definition.
This happens because the adjacency list for each vertex is stored as a Set. Set uses Hash as internal storage, and Hash copies non-frozen string keys. Therefore when "b" is added to the adjacency list of "a," a new object is created. The DOT module (dot.rb) uses the Ruby object ID as the node name and therefore generates two "b" nodes.
dot.rb should probably be changed not to use object_id, for consistency with the rest of the library.
[Ruby License](../LICENSE).
Should be:
{file:LICENSE}
same as in README
Also fix formatting.
The keywords node, edge, graph, digraph, subgraph, and strict (case insensitive) cause syntax errors in the DOT format when they're used as labels.
The DOT language documentation notes that: 'There is no semantic difference between abc_2 and "abc_2", or between 2.34 and "2.34". Obviously, to use a keyword as an ID, it must be quoted.' (http://www.graphviz.org/doc/info/lang.html) As far as I can tell, the same applies to labels. If this is the case, it seems that it would be best to double-quote all labels generated by the to_dot_graph function and escape any double-quotes in the labels themselves.
Could you give me an example of how to set properties to edges? Or an example of adding new edges with weight and other attributes?
Line 120 in 8613828
Image from our calling the bfs_search_tree_from method internally through the RGL directed graph is indicating high memory for the require, is it possible to remove it and do once when this file is loaded?
Is there a method to check whether a path exists between two vertices?
E.g. graph.path? v1, v2
@monora Thanks for your effort to create this gem.
The solution I found that to use -ve weight for edges and then find shortest path and that will be equal to longest path. In docs I found that -ve weight for edges will return error for various shortest path algorithm methods.
How should I overcome this ?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.