Class: BGL::Graph

Inherits:
Object show all
Defined in:
ext/graph/algorithm.cc,
lib/roby/graph.rb,
ext/graph/graph.cc,
ext/graph/algorithm.cc

Overview

A directed graph between Ruby objects. See BGL documentation.

Direct Known Subclasses

Roby::RelationGraph

Defined Under Namespace

Classes: Reverse, Undirected

Instance Method Summary collapse

Instance Method Details

#components(seeds = nil, include_singletons = true) ⇒ Object

Returns an array of vertex sets. Each set is a connected component of graph. If a list of vertices seeds is provided, returns only the components the vertices are part of. The graph is treated as if it were not directed.

If include_singletons is false and seeds is non-nil, then components will not include the singleton components { v } where v is in seeds



264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
 
# File 'ext/graph/algorithm.cc', line 264

static VALUE graph_components(int argc, VALUE* argv, VALUE self)
{ 
    VALUE seeds, include_singletons;
    rb_scan_args(argc, argv, "02", &seeds, &include_singletons);
    if (argc == 1)
  include_singletons = Qtrue;

    // Compute the connected components
    RubyGraph const& g = graph_wrapped(self);

    typedef std::map<vertex_descriptor, int> ComponentMap;
    ComponentMap component_map;
    ColorMap   color_map;
    int count = connected_components(utilmm::make_undirected_graph(g),
      make_assoc_property_map(component_map), 
      boost::color_map( make_assoc_property_map(color_map) ));

    VALUE ret = rb_ary_new2(count);
    std::vector<bool>  enabled_components;
    std::vector<VALUE> components(count);
    if (0 == argc) 
  enabled_components.resize(count, true);
    else
    {
  enabled_components.resize(count, false);
  std::set<VALUE>& seed_set = rb_to_set(seeds);
  for (std::set<VALUE>::const_iterator it = seed_set.begin(); it != seed_set.end(); ++it)
  {
      VALUE rb_vertex = *it;

      vertex_descriptor v; bool in_graph;
      tie(v, in_graph) = rb_to_vertex(rb_vertex, self);
      if (in_graph)
      {
    int v_c = component_map[v];
    enabled_components[v_c] = true;
      }
      else if (RTEST(include_singletons))
    rb_ary_push(ret, rb_ary_new3(1, rb_vertex));
  }
    }

    // Add empty array for all enabled components
    for (int i = 0; i < count; ++i)
    {
  if (! enabled_components[i]) continue;
  VALUE ary = components[i] = rb_ary_new();
  rb_ary_store(ret, i, ary);
    }

    // Add the vertices to their corresponding Ruby component
    for (ComponentMap::const_iterator it = component_map.begin(); it != component_map.end(); ++it)
    {
  int c = it->second;
  if (! enabled_components[c])
      continue;

  rb_ary_push(components[c], g[it->first]);
    }

    if (argc > 0 && !RTEST(include_singletons))
    {
  // Remove the remaining singletons
  for (int i = 0; i < count; ++i)
  {
      if (! enabled_components[i])
    continue;
      if (RARRAY(components[i])->len == 1)
    rb_ary_store(ret, i, Qnil);
  }
    }

    // Remove all unused component slots (disabled components)
    rb_funcall(ret, rb_intern("compact!"), 0);
    return ret;
}

#each_bfs(root, mode) {|source, dest, info, kind| ... } ⇒ Object

Enumerates edges of the graph following a breadth-first search order. mode is a filter on the kind of edge which shall be enumerated (TREE, NON_TREE and ALL) and root is the source of the search

Yields:

  • (source, dest, info, kind) 


611
612
613
614
615
 
# File 'ext/graph/algorithm.cc', line 611

static VALUE graph_direct_each_bfs(VALUE self, VALUE root, VALUE mode)
{
    RubyGraph& graph = graph_wrapped(self);
    return graph_each_bfs(self, graph, root, mode);
}

#each_dfs(root, mode) {|source, dest, info, kind| ... } ⇒ Object

Enumerates edges of the graph following a depth-first search order. mode is a filter on the kind of edge which shall be enumerated (TREE, FORWARD_OR_CROSS, BACK and ALL) and root is the source of the search

Yields:

  • (source, dest, info, kind) 


456
457
458
459
460
 
# File 'ext/graph/algorithm.cc', line 456

static VALUE graph_direct_each_dfs(VALUE self, VALUE root, VALUE mode)
{
    RubyGraph& graph = graph_wrapped(self);
    return graph_each_dfs(self, graph, root, mode);
}

#each_edge {|source, target, info| ... } ⇒ Object

Iterates on all edges in this graph. source and target are the edge vertices, info is the data associated with the edge. See #link.

Yields:

  • (source, target, info) 


224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'ext/graph/graph.cc', line 224

static
VALUE graph_each_edge(VALUE self)
{
    RubyGraph& graph = graph_wrapped(self);

    edge_iterator   begin, end;
    tie(begin, end) = edges(graph);

    for (edge_iterator it = begin; it != end;)
    {
  VALUE from = graph[source(*it, graph)];
  VALUE to = graph[target(*it, graph)];
  VALUE data = graph[*it].info;
  ++it;

  rb_yield_values(3, from, to, data);
    }
    return self;
}

#each_vertex {|vertex| ... } ⇒ Object

Iterates on all vertices in graph.

Yields:

  • (vertex) 


65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'ext/graph/graph.cc', line 65

static
VALUE graph_each_vertex(VALUE self)
{
    RubyGraph& graph = graph_wrapped(self);

    vertex_iterator begin, end;
    tie(begin, end) = vertices(graph);

    for (vertex_iterator it = begin; it != end;)
    {
  VALUE vertex = graph[*it];
  ++it;
  rb_yield(vertex);
    }
    return self;
}

#generated_subgraph([v1, v2, ...][, include_singletons]) ⇒ Object

Returns an array of vertex sets. Each set is the component that can be reached from one of the given seed. If no initial vertex is given, the graph roots are taken.



360
361
 
# File 'ext/graph/algorithm.cc', line 360

static VALUE graph_generated_subgraphs(int argc, VALUE* argv, VALUE self)
{ return graph_do_generated_subgraphs(argc, argv, graph_wrapped(self), self); }

#include?(vertex) ⇒ Boolean

Returns true if vertex is part of this graph.

Returns:

  • (Boolean) 


131
132
133
134
135
136
137
 
# File 'ext/graph/graph.cc', line 131

static
VALUE graph_include_p(VALUE self, VALUE vertex)
{
    bool includes;
    tie(tuples::ignore, includes) = rb_to_vertex(vertex, self);
    return includes ? Qtrue : Qfalse;
}

#initialize_copy(source) ⇒ Object

:nodoc:



103
104
105
106
107
108
 
# File 'lib/roby/graph.rb', line 103

def initialize_copy(source) # :nodoc:
    super

    source.each_vertex { |v| insert(v) }
    source.each_edge { |s, t, i| link(s, t, i) }
end

#insert(vertex) ⇒ Object

Add vertex in this graph.



88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'ext/graph/graph.cc', line 88

static
VALUE graph_insert(VALUE self, VALUE vertex)
{
    RubyGraph&  graph = graph_wrapped(self);
    graph_map&  vertex_graphs = vertex_descriptor_map(vertex);

    graph_map::iterator it;
    bool inserted;
    tie(it, inserted) = vertex_graphs.insert( make_pair(self, static_cast<void*>(0)) );
    if (inserted)
  it->second = add_vertex(vertex, graph);

    return self;
}

#link(source, target, info) ⇒ Object

Adds an edge from source to target, with info as property Raises ArgumentError if the edge already exists.



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
# File 'ext/graph/graph.cc', line 161

static
VALUE graph_link(VALUE self, VALUE source, VALUE target, VALUE info)
{
    RubyGraph& graph = graph_wrapped(self);

    vertex_descriptor 
  s = graph_ensure_inserted_vertex(self, source),
  t = graph_ensure_inserted_vertex(self, target);

    bool inserted = add_edge(s, t, EdgeProperty(info), graph).second;
    if (! inserted)
  rb_raise(rb_eArgError, "edge already exists");

    return self;
}

#linked?(source, target) ⇒ Boolean

Checks if there is an edge from source to target

Returns:

  • (Boolean) 


204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'ext/graph/graph.cc', line 204

static
VALUE graph_linked_p(VALUE self, VALUE source, VALUE target)
{
    RubyGraph& graph = graph_wrapped(self);

    vertex_descriptor s, t; bool exists;
    tie(s, exists) = rb_to_vertex(source, self);
    if (! exists) return Qfalse;
    tie(t, exists) = rb_to_vertex(target, self);
    if (! exists) return Qfalse;
    return edge(s, t, graph).second ? Qtrue : Qfalse;
}

#neighborhood(vertex, distance) ⇒ Object

Returns a list of [parent, child, info] for all edges that are at a distance no more than distance from vertex.



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/roby/graph.rb', line 124

def neighborhood(vertex, distance)
    result = []
    seen = Set.new
    depth = { vertex => 0 }
    undirected.each_bfs(vertex, ALL) do |from, to, info, kind|
  new_depth = depth[from] + 1
  if kind == TREE
      depth[to] = new_depth
  else
      next if seen.include?(to)
  end
  seen << from

  if depth[from] > distance
      break
  end

  if new_depth <= distance
      if linked?(from, to)
    result << [from, to, info]
      else
    result << [to, from, info]
      end
  end
    end
    result
end

#prune ⇒ Object

In #each_dfs, call this method to stop developing the current branch



426
427
428
429
430
431
 
# File 'ext/graph/algorithm.cc', line 426

static VALUE graph_prune(VALUE self)
{
    VALUE thread = rb_thread_current();
    rb_thread_local_aset(thread, rb_intern("@prune"), Qtrue);
    return Qtrue;
}

#reachable?(v1, v2) ⇒ Boolean

Returns true if v2 can be reached from v1

Returns:

  • (Boolean) 


539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
 
# File 'ext/graph/algorithm.cc', line 539

VALUE graph_reachable_p(VALUE self, VALUE source, VALUE target)
{
    RubyGraph& graph = graph_wrapped(self);
    vertex_descriptor s, t; bool exists;
    tie(s, exists) = rb_to_vertex(source, self);
    if (! exists)
  return Qfalse;
    tie(t, exists) = rb_to_vertex(target, self);
    if (! exists)
  return Qfalse;

    map<vertex_descriptor, default_color_type> colors;
    bool found;
    depth_first_visit(graph, s, ruby_reachable_visitor(found, t), 
      make_assoc_property_map(colors), ruby_reachable_terminator(found));

    return found;
}

#remove(vertex) ⇒ Object

Remove vertex from this graph.



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'ext/graph/graph.cc', line 109

static
VALUE graph_remove(VALUE self, VALUE vertex)
{
    RubyGraph&  graph = graph_wrapped(self);
    graph_map&  vertex_graphs = vertex_descriptor_map(vertex);

    graph_map::iterator it = vertex_graphs.find(self);
    if (it == vertex_graphs.end())
  return self;

    clear_vertex(it->second, graph);
    remove_vertex(it->second, graph);
    vertex_graphs.erase(it);
    return self;
}

#replace_vertex(from, to) ⇒ Object

Replaces from by to. This means to takes the role of from in all edges from is involved in. from is removed from the graph.



112
113
114
115
116
117
118
119
120
 
# File 'lib/roby/graph.rb', line 112

def replace_vertex(from, to)
    from.each_parent_vertex(self) do |parent|
  link(parent, to, parent[from, self])
    end
    from.each_child_vertex(self) do |child|
  link(to, child, from[child, self])
    end
    remove(from)
end

#same_graph?(other) ⇒ Boolean

Two graphs are the same if they have the same vertex set and the same edge set

Returns:

  • (Boolean) 


154
155
156
157
158
159
160
161
162
163
 
# File 'lib/roby/graph.rb', line 154

def same_graph?(other)
    unless other.respond_to?(:each_vertex) && other.respond_to?(:each_edge)
  return false
    end

    # cannot use to_value_set for edges since we are comparing arrays (and ValueSet
    # bases its comparison on VALUE)
    (other.enum_for(:each_vertex).to_value_set == enum_for(:each_vertex).to_value_set) && 
  (other.enum_for(:each_edge).to_set == enum_for(:each_edge).to_set)
end

#topological_sort ⇒ Array

Returns a topological sorting of this graph

Returns:



650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
 
# File 'ext/graph/algorithm.cc', line 650

static VALUE graph_topological_sort(int argc, VALUE* argv, VALUE self)
{
    VALUE rb_result;
    rb_scan_args(argc, argv, "01", &rb_result);
    if (NIL_P(rb_result))
  rb_result = rb_ary_new();
    else
  rb_ary_clear(rb_result);

    RubyGraph& graph = graph_wrapped(self);
    typedef std::vector<RubyGraph::vertex_descriptor> Result;
    Result result;

    map<vertex_descriptor, default_color_type> colors;
    try
    {
  topological_sort(graph, std::back_inserter(result), 
    boost::color_map(make_assoc_property_map(colors)));

  for (int i = result.size() - 1; i >= 0; --i)
      rb_ary_push(rb_result, graph[result[i]]);
  return rb_result;
    }
    catch(boost::not_a_dag) {}
    rb_raise(rb_eArgError, "the graph is not a DAG");
}

#unlink(source, target, info) ⇒ Object

Removes the edge from source to target. Does nothing if the edge does not exist.



184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'ext/graph/graph.cc', line 184

static
VALUE graph_unlink(VALUE self, VALUE source, VALUE target)
{
    RubyGraph& graph = graph_wrapped(self);

    vertex_descriptor s, t; bool exists;
    tie(s, exists) = rb_to_vertex(source, self);
    if (! exists) return self;
    tie(t, exists) = rb_to_vertex(target, self);
    if (! exists) return self;
    remove_edge(s, t, graph);
    return self;
}