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

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

#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.



28
29
30
# File 'lib/laser/third_party/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/laser/third_party/rgl/mutable.rb', line 42

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

#add_graph(graph) ⇒ Object

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

#add_graphs(*graphs) ⇒ Object

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

#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.



16
17
18
# File 'lib/laser/third_party/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/laser/third_party/rgl/mutable.rb', line 34

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

#cyclesObject

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

#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.



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

#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/laser/third_party/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.



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

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.



66
67
68
# File 'lib/laser/third_party/rgl/mutable.rb', line 66

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.



83
84
85
# File 'lib/laser/third_party/rgl/mutable.rb', line 83

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