Module: RGL::MutableGraph
 Includes:
 Graph
 Included in:
 ControlFlowGraph, DirectedAdjacencyGraph
 Defined in:
 lib/laser/third_party/rgl/mutable.rb,
lib/laser/third_party/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)

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

 (Object) add_edges(*edges)
Add all edges in the edges array to the edge set.

 (Object) add_graph(graph)
Add the graph to the current graph.

 (Object) add_graphs(*graphs)
Adds all the given graphs to the current graph.

 (Object) add_vertex(v)
Add a new vertex v to the graph.

 (Object) add_vertices(*a)
Add all objects in a to the vertex set.

 (Object) cycles
Returns an array of all minimum cycles in a graph.

 (Object) cycles_with_vertex(vertex)
Returns all minimum cycles that pass through a give vertex.

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

 (Object) remove_edge(u, v)
Remove the edge (u,v) from the graph.

 (Object) remove_vertex(v)
Remove u from the vertex set of the graph.

 (Object) remove_vertices(*a)
Remove all vertices specified by the array a from the graph by calling remove_vertex.
Methods included from Graph
#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #build_dfst, #condensation_graph, #depth_first_search, #depth_first_spanning_tree, #depth_first_visit, #dfs_iterator, #directed?, #dominance_frontier, #dominator_tree, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_vertex?, #implicit_graph, #iterated_dominance_frontier, #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
#all?, #any?, #chunk, #collect, #collect_concat, #count, #cycle, #detect, #drop, #drop_while, #each_cons, #each_entry, #each_slice, #each_with_index, #each_with_object, #entries, #find_index, #first, #flat_map, #grep, #group_by, #include?, #inject, #map, #max, #max_by, #min, #min_by, #minmax, #minmax_by, #none?, #one?, #partition, #reject, #reverse_each, #select, #slice_before, #sort, #sort_by, #take, #take_while, #to_a, #to_set, #zip
Instance Method Details
 (Object) add_edge(u, v)
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 outedges of u and (u,v) (or equivalently (v,u)) will appear in the outedges of v. Put another way, v will be adjacent to u and u will be adjacent to v.
28 29 30 
# File 'lib/laser/third_party/rgl/mutable.rb', line 28 def add_edge (u, v) raise NotImplementedError end 
 (Object) add_edges(*edges)
Add all edges in the edges array to the edge set. Elements of the array can be both twoelement arrays or instances of DirectedEdge or UnDirectedEdge.
42 43 44 
# File 'lib/laser/third_party/rgl/mutable.rb', line 42 def add_edges (*edges) edges.each { edge add_edge(edge[0], edge[1]) } end 
 (Object) add_graph(graph)
Add the graph to the current graph. All vertices in the other graph are added, as are all edges.
49 50 51 52 
# File 'lib/laser/third_party/rgl/mutable.rb', line 49 def add_graph(graph) add_vertices(*graph.vertices) add_edges(*graph.edges) end 
 (Object) add_graphs(*graphs)
Adds all the given graphs to the current graph. See #add_graph.
56 57 58 
# File 'lib/laser/third_party/rgl/mutable.rb', line 56 def add_graphs(*graphs) graphs.each { graph add_graph graph } end 
 (Object) add_vertex(v)
Add a new vertex v to the graph. If the vertex is already in the graph (tested via eql?), the method does nothing.
16 17 18 
# File 'lib/laser/third_party/rgl/mutable.rb', line 16 def add_vertex (v) raise NotImplementedError end 
 (Object) add_vertices(*a)
Add all objects in a to the vertex set.
34 35 36 
# File 'lib/laser/third_party/rgl/mutable.rb', line 34 def add_vertices (*a) a.each { v add_vertex v } end 
 (Object) cycles
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.
108 109 110 111 112 113 114 
# File 'lib/laser/third_party/rgl/mutable.rb', line 108 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 
 (Object) cycles_with_vertex(vertex)
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.
90 91 92 
# File 'lib/laser/third_party/rgl/mutable.rb', line 90 def cycles_with_vertex(vertex) cycles_with_vertex_helper(vertex, vertex, []) end 
 (Object) from_graphxml(source)
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/laser/third_party/rgl/graphxml.rb', line 45 def from_graphxml(source) listener = MutableGraphParser.new(self) REXML::Document.parse_stream(source, listener) self end 
 (Object) remove_edge(u, v)
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.
76 77 78 
# File 'lib/laser/third_party/rgl/mutable.rb', line 76 def remove_edge (u, v) raise NotImplementedError end 
 (Object) remove_vertex(v)
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.
66 67 68 
# File 'lib/laser/third_party/rgl/mutable.rb', line 66 def remove_vertex (v) raise NotImplementedError end 
 (Object) remove_vertices(*a)
Remove all vertices specified by the array a from the graph by calling remove_vertex.
83 84 85 
# File 'lib/laser/third_party/rgl/mutable.rb', line 83 def remove_vertices (*a) a.each { v remove_vertex v } end 