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, #bellman_ford_shortest_paths, #bfs_iterator, #bfs_search_tree_from, #bipartite?, #bipartite_sets, #condensation_graph, #depth_first_search, #depth_first_visit, #dfs_iterator, #dijkstra_shortest_path, #dijkstra_shortest_paths, #directed?, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_edge?, #has_vertex?, #implicit_graph, #maximum_flow, #num_edges, #out_degree, #path?, #prim_minimum_spanning_tree, #print_dotted_on, #reverse, #set_edge_options, #set_vertex_options, #size, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertex_id, #vertex_label, #vertices, #vertices_filtered_by, #write_to_graphic_file

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) 


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

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 Edge::DirectedEdge or Edge::UnDirectedEdge.



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

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) 


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

def add_vertex(v)
  raise NotImplementedError
end

#add_vertices(*a) ⇒ Object

Add all objects in a to the vertex set.



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

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

#cycles ⇒ Array

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

Returns:

  • (Array) —

    of all minimum cycles in a graph



99
100
101
102
103
104
105
 
# File 'lib/rgl/mutable.rb', line 99

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) ⇒ Array[Array]

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.

Returns:

  • (Array[Array]) 


78
79
80
 
# File 'lib/rgl/mutable.rb', line 78

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 graphml.graphdrawing.org/).



53
54
55
56
57
 
# File 'lib/rgl/graphxml.rb', line 53

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) 


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

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) 


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

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.



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

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