Included Modules

Files

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, line 28
def add_edge (u, v)
  raise NotImplementedError
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, line 42
def add_edges (*edges)
  edges.each { |edge| add_edge(edge[0], edge[1]) }
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, line 16
def add_vertex (v)
  raise NotImplementedError
end
add_vertices(*a) click to toggle source

Add all objects in a to the vertex set.

# File lib/rgl/mutable.rb, line 34
def add_vertices (*a)
  a.each { |v| add_vertex v }
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, line 94
def cycles
  g = self.clone
  self.inject([]) do |acc, v| 
    acc = acc.concat(g.cycles_with_vertex(v))
    g.remove_vertex(v); acc
  end
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, line 76
def cycles_with_vertex(vertex)
  cycles_with_vertex_helper(vertex, vertex, [])
end
from_graphxml(source) click to toggle source

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

# File lib/rgl/graphxml.rb, line 45
def from_graphxml(source)
  listener = MutableGraphParser.new(self)
  REXML::Document.parse_stream(source, listener)
  self
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, line 62
def remove_edge (u, v)
  raise NotImplementedError
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, line 52
def remove_vertex (v)
  raise NotImplementedError
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, line 69
def remove_vertices (*a)
  a.each { |v| remove_vertex v }
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.