monora / rgl Goto Github PK

Ruby 3.2 ist released:
https://www.ruby-lang.org/en/news/2022/12/25/ruby-3-2-0-released/

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

https://spdx.dev/ids/

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

https://spdx.org/licenses/

We have been asked to review the licences of gems we use. Can we get clarification of the licence for rgl? Thank you!

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 ?

Discussed in #65

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!

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.

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!

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.

#89 (comment)
#89 (comment)

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!

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

David Inman filed this bug at rubyforge
http://rubyforge.org//tracker/?func=detail&atid=511&aid=29788&group_id=110

Conditions:

• I'm a novice with RGL!
• rgl (0.4.0)
• stream (0.5)
• Scientific Linux 5.6
• ruby 1.9.3p194
• 'gem install' installed stream and rgl w/out errors

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:into_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

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 ?

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)

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?

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)

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:

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

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'

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.

Is there a method to check whether a path exists between two vertices?

E.g. graph.path? v1, v2

Examples:

• Automating Ruby Gem Releases with GitHub Actions — andrewm.codes
  Automating Ruby Gem Package Releases With Github Actions | Dennis O'Keeffe Blog

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

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.

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:

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

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.

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?

I botched both the code and the test. Pull request coming.

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.

I was too clever by half in thinking that the reverse graph doesn't need to mirror unconnected vertices. It does.

Pull request coming.

I see it mentioned in the examples, but I couldn't find it in the code...
thanks

See https://monora.github.io/rgl/

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.

Example from README.md

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"

[Ruby License](../LICENSE).

Should be:

{file:LICENSE}

same as in README

Also fix formatting.

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.

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

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?

@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 ?

• Fix Dangling links in Readme ## Links section
• Fix doc.yml trigger. Should only fire when a release (new tag) is created.