module RGL::MutableGraph

A MutableGraph can be changed via the addition or removal of edges and vertices.

Public Instance Methods

add_edge(u, v) click to toggle source

Inserts the edge (u,v) into the graph.

Note that for undirected graphs, (u,v) is the same edge as (v,u), so after a call to the function add_edge(), this implies that edge (u,v) will appear in the out-edges of u and (u,v) (or equivalently (v,u)) will appear in the out-edges of v. Put another way, v will be adjacent to u and u will be adjacent to v.

   # File lib/rgl/mutable.rb
29 def add_edge(u, v)
30   raise NotImplementedError
31 end
add_edges(*edges) click to toggle source

Add all edges in the edges array to the edge set. Elements of the array can be both two-element arrays or instances of DirectedEdge or UnDirectedEdge.

   # File lib/rgl/mutable.rb
43 def add_edges(*edges)
44   edges.each { |edge| add_edge(edge[0], edge[1]) }
45 end
add_vertex(v) click to toggle source

Add a new vertex v to the graph. If the vertex is already in the graph (tested via eql?), the method does nothing.

   # File lib/rgl/mutable.rb
17 def add_vertex(v)
18   raise NotImplementedError
19 end
add_vertices(*a) click to toggle source

Add all objects in a to the vertex set.

   # File lib/rgl/mutable.rb
35 def add_vertices(*a)
36   a.each { |v| add_vertex v }
37 end
cycles() click to toggle source

Returns an array of all minimum cycles in a graph

This is not an efficient implementation O(n^4) and could be done using Minimum Spanning Trees. Hint. Hint.

    # File lib/rgl/mutable.rb
 99 def cycles
100   g = self.clone
101   self.inject([]) do |acc, v|
102     acc = acc.concat(g.cycles_with_vertex(v))
103     g.remove_vertex(v); acc
104   end
105 end
cycles_with_vertex(vertex) click to toggle source

Returns all minimum cycles that pass through a give vertex. The format is an Array of cycles, with each cycle being an Array of vertices in the cycle.

   # File lib/rgl/mutable.rb
78 def cycles_with_vertex(vertex)
79   cycles_with_vertex_helper(vertex, vertex, [])
80 end
from_graphxml(source) click to toggle source

Initializes an RGL graph from a subset of the GraphML format given in source (see graphml.graphdrawing.org/).

   # File lib/rgl/graphxml.rb
53 def from_graphxml(source)
54   listener = MutableGraphParser.new(self)
55   REXML::Document.parse_stream(source, listener)
56   self
57 end
remove_edge(u, v) click to toggle source

Remove the edge (u,v) from the graph. If the graph allows parallel edges, this removes all occurrences of (u,v).

Precondition: u and v are vertices in the graph. Postcondition: (u,v) is no longer in the edge set for g.

   # File lib/rgl/mutable.rb
63 def remove_edge(u, v)
64   raise NotImplementedError
65 end
remove_vertex(v) click to toggle source

Remove u from the vertex set of the graph. All edges whose target is v are also removed from the edge set of the graph.

Postcondition: num_vertices is one less, v no longer appears in the vertex set of the graph, and there no edge with source or target v.

   # File lib/rgl/mutable.rb
53 def remove_vertex(v)
54   raise NotImplementedError
55 end
remove_vertices(*a) click to toggle source

Remove all vertices specified by the array a from the graph by calling remove_vertex.

   # File lib/rgl/mutable.rb
70 def remove_vertices(*a)
71   a.each { |v| remove_vertex v }
72 end