Class: LemonGraph::Graph

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

Overview

Undirected graph.

The undirected graphs fulfill the concept of directed graphs, since each edge can also be regarded as two oppositely directed arcs. Undirected graphs provide an Edge type for the undirected edges and an Arc type for the directed arcs.

In LEMON, each undirected edge has an inherent orientation. Thus it can define if an arc is forward or backward oriented in an undirected graph with respect to this default oriantation of the represented edge. With the direction() and direct() functions the direction of an arc can be obtained and set, respectively.

Only nodes and edges can be added to or removed from an undirected graph and the corresponding arcs are added or removed automatically.

Defined Under Namespace

Classes: Arc, Edge, Node

Instance Method Summary collapse

Instance Method Details

#add_edge(u, v) ⇒ Edge

Adds a new Edge to the graph with between nodes u and v.

Parameters:

Returns:

  • (Edge) —

    the newly created edge



116
117
118
119
120
121
122
123
124
125
 
# File 'ext/lemongraph/graph.cc', line 116

VALUE lemongraph_graph_add_edge(VALUE self, VALUE u, VALUE v)
{
	lemon::ListGraph &g = lemongraph_graph_rb2ref(self);
	lemongraph_graph_raise_if_not_valid_node(g, self, u);
	lemongraph_graph_raise_if_not_valid_node(g, self, v);
	lemon::ListGraph::Edge e = g.addEdge(
			lemongraph_rbunnode2unnode(u),
			lemongraph_rbunnode2unnode(v));
	return lemongraph_make_unedge(e, self);
}

#add_node ⇒ Node

Adds a new node to the graph

Returns:

  • (Node) —

    the newly created node



91
92
93
94
95
 
# File 'ext/lemongraph/graph.cc', line 91

VALUE lemongraph_graph_add_node(VALUE self)
{
	lemon::ListGraph::Node n = lemongraph_graph_rb2ref(self).addNode();
	return lemongraph_make_unnode(n, self);
}

#arcs ⇒ Array<Arc>

Returns an array containing all the arcs of the graph.

Returns:



313
314
315
316
317
318
319
320
 
# File 'ext/lemongraph/graph.cc', line 313

VALUE lemongraph_graph_arcs(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	VALUE ar = rb_ary_new_capa(lemon::countArcs(g));
	for (lemon::ListGraph::ArcIt a(g); a != lemon::INVALID; ++a)
		rb_ary_push(ar, lemongraph_make_unarc(a, self));
	return ar;
}

#clear ⇒ self

Erases all nodes and edges from the graph

Returns:

  • (self) 


189
190
191
192
193
 
# File 'ext/lemongraph/graph.cc', line 189

VALUE lemongraph_graph_clear(VALUE self)
{
	lemongraph_graph_rb2ref(self).clear();
	return self;
}

#each_arc {|arc| ... } ⇒ self #each_arc ⇒ Enumerator

Calls the block, if given, once for each Arc in the graph. The arcs are passed as parameters to the block.

Returns self, or, if no block is given, an Enumerator is returned.

Overloads:

  • #each_arc {|arc| ... } ⇒ self

    Yield Parameters:

    Returns:

    • (self)
  • #each_arc ⇒ Enumerator

    Returns:

    • (Enumerator)

Returns:

  • (self, Enumerator) 


342
343
344
345
346
347
348
349
 
# File 'ext/lemongraph/graph.cc', line 342

VALUE lemongraph_graph_each_arc(VALUE self)
{
	RETURN_SIZED_ENUMERATOR(self, 0, 0, lemongraph_graph_arcenum_nbarcs);
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	for (lemon::ListGraph::ArcIt a(g); a != lemon::INVALID; ++a)
		rb_yield(lemongraph_make_unarc(a, self));
	return self;
}

#each_edge {|edge| ... } ⇒ self #each_edge ⇒ Enumerator

Calls the block, if given, once for each Edge in the graph. The edges are passed as parameters to the block.

Returns self, or, if no block is given, an Enumerator is returned.

Overloads:

  • #each_edge {|edge| ... } ⇒ self

    Yield Parameters:

    Returns:

    • (self)
  • #each_edge ⇒ Enumerator

    Returns:

    • (Enumerator)

Returns:

  • (self, Enumerator) 


290
291
292
293
294
295
296
297
 
# File 'ext/lemongraph/graph.cc', line 290

VALUE lemongraph_graph_each_edge(VALUE self)
{
	RETURN_SIZED_ENUMERATOR(self, 0, 0, lemongraph_graph_edgeenum_nbedges);
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	for (lemon::ListGraph::EdgeIt n(g); n != lemon::INVALID; ++n)
		rb_yield(lemongraph_make_unedge(n, self));
	return self;
}

#each_node {|node| ... } ⇒ self #each_node ⇒ Enumerator

Calls the block, if given, once for each Node in the graph. The nodes are passed as parameters to the block.

Returns self, or, if no block is given, an Enumerator is returned.

Overloads:

  • #each_node {|node| ... } ⇒ self

    Yield Parameters:

    Returns:

    • (self)
  • #each_node ⇒ Enumerator

    Returns:

    • (Enumerator)

Returns:

  • (self, Enumerator) 


238
239
240
241
242
243
244
245
 
# File 'ext/lemongraph/graph.cc', line 238

VALUE lemongraph_graph_each_node(VALUE self)
{
	RETURN_SIZED_ENUMERATOR(self, 0, 0, lemongraph_graph_nodeenum_nbnodes);
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	for (lemon::ListGraph::NodeIt n(g); n != lemon::INVALID; ++n)
		rb_yield(lemongraph_make_unnode(n, self));
	return self;
}

#edges ⇒ Array<Edge>

Returns an array containing all the edges of the graph.

Returns:



261
262
263
264
265
266
267
268
 
# File 'ext/lemongraph/graph.cc', line 261

VALUE lemongraph_graph_edges(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	VALUE a = rb_ary_new_capa(lemon::countEdges(g));
	for (lemon::ListGraph::EdgeIt e(g); e != lemon::INVALID; ++e)
		rb_ary_push(a, lemongraph_make_unedge(e, self));
	return a;
}

#erase(node) ⇒ self #erase(edge) ⇒ self

Erases the node or edge from the graph.

Overloads:

  • #erase(node) ⇒ self

    Erases the given node along with its incidents edges from the graph.

    Parameters:

    • node (Node) —

      the node to erase

  • #erase(edge) ⇒ self

    Erases the given edge from the graph.

    Parameters:

    • arc (Edge) —

      the edge to erase

Returns:

  • (self) 


164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'ext/lemongraph/graph.cc', line 164

VALUE lemongraph_graph_erase_item(VALUE self, VALUE item)
{
	VALUE klass = rb_class_of(item);
	if (klass == c_UnNode) {
		if (rb_iv_get(item, "@graph") != self)
			rb_raise(rb_eRuntimeError, "this node does not belong to the graph");
		lemongraph_graph_rb2ref(self).erase(lemongraph_rbunnode2unnode(item));
	}
	else if (klass == c_UnEdge) {
		if (rb_iv_get(item, "@graph") != self)
			rb_raise(rb_eRuntimeError, "this edge does not belong to the graph");
		lemongraph_graph_rb2ref(self).erase(lemongraph_rbunedge2unedge(item));
	}
	else if (klass == c_UnArc)
		rb_raise(rb_eTypeError, "cannot erase a %" PRIsVALUE " from a %" PRIsVALUE, rb_class_name(c_UnArc), rb_class_name(c_Graph));
	else
		rb_raise(rb_eTypeError, "expecting a %" PRIsVALUE " or a %" PRIsVALUE ", not a %s",
				rb_class_name(c_UnNode), rb_class_name(c_UnEdge), rb_obj_classname(item));
	return self;
}

#initialize_copy(orig) ⇒ self

Method called by dup and clone methods.

Returns:

  • (self) 


77
78
79
80
81
82
83
84
85
 
# File 'ext/lemongraph/graph.cc', line 77

VALUE lemongraph_graph_initialize_copy(VALUE self, VALUE orig)
{

	rb_call_super(1, &orig);
	lemon::ListGraph& from = lemongraph_graph_rb2ref(orig);
	lemon::ListGraph& to =   lemongraph_graph_rb2ref(self);
	lemon::graphCopy(from, to).run();
	return self;
}

#nb_arcs ⇒ Integer

Number of arcs in the graph.

Returns:

  • (Integer) 


303
304
305
306
307
 
# File 'ext/lemongraph/graph.cc', line 303

VALUE lemongraph_graph_nb_arcs(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	return INT2NUM(lemon::countArcs(g));
}

#nb_edges ⇒ Integer

Number of edges in the graph.

Returns:

  • (Integer) 


251
252
253
254
255
 
# File 'ext/lemongraph/graph.cc', line 251

VALUE lemongraph_graph_nb_edges(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	return INT2NUM(lemon::countEdges(g));
}

#nb_nodes ⇒ Integer

Number of nodes in the graph.

Returns:

  • (Integer) 


199
200
201
202
203
 
# File 'ext/lemongraph/graph.cc', line 199

VALUE lemongraph_graph_nb_nodes(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	return INT2NUM(lemon::countNodes(g));
}

#nodes ⇒ Array<Node>

Returns an array containing all the nodes of the graph.

Returns:



209
210
211
212
213
214
215
216
 
# File 'ext/lemongraph/graph.cc', line 209

VALUE lemongraph_graph_nodes(VALUE self)
{
	lemon::ListGraph& g = lemongraph_graph_rb2ref(self);
	VALUE a = rb_ary_new_capa(lemon::countNodes(g));
	for (lemon::ListGraph::NodeIt n(g); n != lemon::INVALID; ++n)
		rb_ary_push(a, lemongraph_make_unnode(n, self));
	return a;
}

#to_dot(**h) ⇒ Graphviz

Returns a LemonGraph::Graphviz object. See LemonGraph::Graphviz#initialize for optional keyword arguments.

Returns:



234
235
236
 
# File 'lib/lemongraph/graphviz.rb', line 234

def to_dot(**h)
  Graphviz.new(self, **h)
end

#valid?(item) ⇒ Boolean

Test if the given node edge or arc is valid, i.e. it is a real node/edge/arc of the graph.

Parameters:

Returns:

  • (Boolean) 


132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
# File 'ext/lemongraph/graph.cc', line 132

VALUE lemongraph_graph_item_is_valid(VALUE self, VALUE item)
{
	bool r = false;
	VALUE klass = rb_class_of(item);
	if (klass == c_UnNode) {
		if (rb_iv_get(item, "@graph") == self)
			r = lemongraph_graph_rb2ref(self).valid(lemongraph_rbunnode2unnode(item));
	}
	else if (klass == c_UnEdge) {
		if (rb_iv_get(item, "@graph") == self)
			r = lemongraph_graph_rb2ref(self).valid(lemongraph_rbunedge2unedge(item));
	}
	else if (klass == c_UnArc) {
		if (rb_iv_get(item, "@graph") == self)
			r = lemongraph_graph_rb2ref(self).valid(lemongraph_rbunarc2unarc(item));
	}
	else
		rb_raise(rb_eTypeError, "expecting a %" PRIsVALUE ", a %" PRIsVALUE " or a %" PRIsVALUE ", not a %s",
				rb_class_name(c_UnNode), rb_class_name(c_UnEdge), rb_class_name(c_UnArc), rb_obj_classname(item));
	return r ? Qtrue : Qfalse;
}