Module: RGL::MutableGraph

Includes:
Graph
Included in:
DirectedAdjacencyGraph
Defined in:
lib/rgl/mutable.rb,
lib/rgl/graphxml.rb

Overview

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

Defined Under Namespace

Classes: MutableGraphParser

Instance Method Summary collapse

Methods included from Graph

#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #condensation_graph, #depth_first_search, #depth_first_visit, #dfs_iterator, #directed?, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_vertex?, #implicit_graph, #num_edges, #out_degree, #print_dotted_on, #reverse, #size, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertices, #vertices_filtered_by, #write_to_graphic_file

Methods included from Enumerable

#length

Instance Method Details

#add_edge(u, v) ⇒ Object

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.

Raises:

  • (NotImplementedError) 


28
29
30
 
# File 'lib/rgl/mutable.rb', line 28

def add_edge (u, v)
  raise NotImplementedError
end

#add_edges(*edges) ⇒ Object

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.



42
43
44
 
# File 'lib/rgl/mutable.rb', line 42

def add_edges (*edges)
  edges.each { |edge| add_edge(edge[0], edge[1]) }
end

#add_vertex(v) ⇒ Object

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

Raises:

  • (NotImplementedError) 


16
17
18
 
# File 'lib/rgl/mutable.rb', line 16

def add_vertex (v)
  raise NotImplementedError
end

#add_vertices(*a) ⇒ Object

Add all objects in a to the vertex set.



34
35
36
 
# File 'lib/rgl/mutable.rb', line 34

def add_vertices (*a)
  a.each { |v| add_vertex v }
end

#cycles ⇒ Object

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.



94
95
96
97
98
99
100
 
# 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) ⇒ Object

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.



76
77
78
 
# File 'lib/rgl/mutable.rb', line 76

def cycles_with_vertex(vertex)
  cycles_with_vertex_helper(vertex, vertex, [])
end

#from_graphxml(source) ⇒ Object

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



45
46
47
48
49
 
# 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) ⇒ Object

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.

Raises:

  • (NotImplementedError) 


62
63
64
 
# File 'lib/rgl/mutable.rb', line 62

def remove_edge (u, v)
  raise NotImplementedError
end

#remove_vertex(v) ⇒ Object

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.

Raises:

  • (NotImplementedError) 


52
53
54
 
# File 'lib/rgl/mutable.rb', line 52

def remove_vertex (v)
  raise NotImplementedError
end

#remove_vertices(*a) ⇒ Object

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



69
70
71
 
# File 'lib/rgl/mutable.rb', line 69

def remove_vertices (*a)
  a.each { |v| remove_vertex v }
end