Class: BGL::Graph::Undirected

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

Overview

This class is a graph adaptor which transforms a directed graph into an undirected graph

Instance Method Summary collapse

Constructor Details

#initialize(g) ⇒ Undirected

Create an undirected graph which has the same edge set than g



97
98
99
 
# File 'lib/roby/graph.rb', line 97

def initialize(g)
    @__bgl_real_graph__ = g
end

Instance Method Details

#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) 


638
639
640
641
642
643
 
# File 'ext/graph/algorithm.cc', line 638

static VALUE graph_undirected_each_bfs(VALUE self, VALUE root, VALUE mode)
{
    VALUE real_graph = graph_view_of(self);
    RubyGraph& graph = graph_wrapped(real_graph);
    return graph_each_bfs(real_graph, utilmm::make_undirected_graph(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) 


483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
 
# File 'ext/graph/algorithm.cc', line 483

static VALUE graph_undirected_each_dfs(VALUE self, VALUE root, VALUE mode)
{
    VALUE real_graph = graph_view_of(self);
    RubyGraph& graph = graph_wrapped(real_graph);
    typedef utilmm::undirected_graph<RubyGraph> Undirected;
    Undirected undirected(graph);

    vertex_descriptor v; bool exists;
    tie(v, exists) = rb_to_vertex(root, real_graph);
    if (! exists)
  return self;

    ColorMap colors;
    edge_iterator ei, ei_end;
    for(tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)
  graph[*ei].color = boost::white_color;

    rb_thread_local_aset(rb_thread_current(), rb_intern("@prune"), Qfalse);
    utilmm::undirected_depth_first_visit(undirected, v, ruby_dfs_visitor(FIX2INT(mode)),
      make_assoc_property_map(colors), 
      utilmm::make_undirected_edge_map(get(&EdgeProperty::color, graph)), 
      &search_terminator<Undirected>);
    return self;
}

#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 is provided, returns only the components the vertices are part of. The graph is treated as if it were not directed. It is equivalent to graph.components.



349
350
351
 
# File 'ext/graph/algorithm.cc', line 349

static
VALUE graph_undirected_components(int argc, VALUE* argv, VALUE self)
{ return graph_components(argc, argv, graph_view_of(self)); }

#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;
}