class Silicium::Graphs::OrientedGraph
Class represents oriented graph
Public Class Methods
# File lib/graph.rb, line 15 def initialize(initializer = []) @vertices = {}; @vertex_labels = {} @edge_labels = {}; @edge_number = 0 initializer.each do |v| add_vertex!(v[:v]) v[:i].each do |iv| add_vertex!(v[:v]) add_vertex!(iv) add_edge!(v[:v], iv) end end end
Public Instance Methods
Adds edge to graph
# File lib/graph.rb, line 37 def add_edge!(from, to) protected_add_edge!(from, to) @edge_number += 1 end
should only be used in constructor
# File lib/graph.rb, line 43 def add_edge_force!(from, to) add_vertex!(from) add_vertex!(to) add_edge!(from, to) end
Adds vertex to graph
# File lib/graph.rb, line 30 def add_vertex!(vertex_id) if @vertices.has_key?(vertex_id); return end @vertices[vertex_id] = [].to_set end
Returns array of vertices which adjacted with vertex @raise [GraphError] if graph does not contain vertex
# File lib/graph.rb, line 52 def adjacted_with(vertex) raise GraphError.new("Graph does not contain vertex #{vertex}") unless @vertices.has_key?(vertex) @vertices[vertex].clone end
Deletes edge from graph
# File lib/graph.rb, line 139 def delete_edge!(from, to) protected_delete_edge!(from, to) @edge_number -= 1 end
Deletes vertex from graph
# File lib/graph.rb, line 129 def delete_vertex!(vertex) if has_vertex?(vertex) @vertices.keys.each { |key| delete_edge!(key, vertex) } @vertices.delete(vertex) @vertex_labels.delete(vertex) @vertices.keys.each { |key| @edge_labels.delete(Pair.new(vertex, key)) } end end
Returns number of edge labels
# File lib/graph.rb, line 114 def edge_label_number @edge_labels.count end
Returns labels of edges
# File lib/graph.rb, line 166 def edge_labels @edge_labels end
Returns number of edges
# File lib/graph.rb, line 104 def edge_number @edge_number end
Finds Strongly Connected Components (SCC) in graph. SCC is a subgraph where every vertex is reachable from every other vertex. @return Array of SCC. Each component is represented as Array of vertices in decreasing order of their DFS timestamps. @author vaimon
# File lib/graph/scc.rb, line 11 def find_strongly_connected_components # Vertices we have already visited. visited = Hash.new(false) # Timestamps got during depth-first search. order = [] # Resulting array of SCC. res = [] # Step 1: Launch DFS to get order marks @vertices.keys.each do |key| visited, order = scc_dfs_first key, visited, order unless visited[key] end order.uniq! # Step 2: Transpose adjacency list transposed = transpose_adjacency_list # Step 3: Launch second DFS in reverse order of timestamps from Step 1 to build components. # HACK: In original algorithm, we use *visited* again, but here the code is a bit # optimized using *order* instead of *visited* until order.empty? component = [] order, component = scc_dfs_second order.last, component, order, transposed res << component end res end
Returns edge label @raise [GraphError] if graph does not contain edge
# File lib/graph.rb, line 80 def get_edge_label(from, to) if !@vertices.has_key?(from) || ! @vertices[from].include?(to) raise GraphError.new("Graph does not contain edge (#{from}, #{to})") end @edge_labels[Pair.new(from, to)] end
Returns vertex label @raise [GraphError] if graph does not contain vertex
# File lib/graph.rb, line 90 def get_vertex_label(vertex) unless @vertices.has_key?(vertex) raise GraphError.new("Graph does not contain vertex #{vertex}") end @vertex_labels[vertex] end
Checks if graph contains edge
# File lib/graph.rb, line 124 def has_edge?(from, to) @vertices.has_key?(from) && @vertices[from].include?(to) end
Checks if graph contains vertex
# File lib/graph.rb, line 119 def has_vertex?(vertex) @vertices.has_key?(vertex) end
Adds label to edge @raise [GraphError] if graph does not contain edge
# File lib/graph.rb, line 60 def label_edge!(from, to, label) unless @vertices.has_key?(from) && @vertices[from].include?(to) raise GraphError.new("Graph does not contain edge (#{from}, #{to})") end @edge_labels[Pair.new(from, to)] = label end
Adds label to vertex @raise [GraphError] if graph does not contain vertex
# File lib/graph.rb, line 70 def label_vertex!(vertex, label) unless @vertices.has_key?(vertex) raise GraphError.new("Graph does not contain vertex #{vertex}") end @vertex_labels[vertex] = label end
Reverses graph
# File lib/graph.rb, line 145 def reverse! l = {}; v = {} @vertices.keys.each { |from| v[from] = [].to_set } @vertices.keys.each do |from| @vertices[from].each do |to| v[to] << from if @edge_labels.include?(Pair.new(from, to)) l[Pair.new(to, from)] = @edge_labels[Pair.new(from, to)] end end end @vertices = v; @edge_labels = l end
Returns number of vertex labels
# File lib/graph.rb, line 109 def vertex_label_number @vertex_labels.count end
Returns labels of vertices
# File lib/graph.rb, line 172 def vertex_labels @vertex_labels end
Returns number of vertices
# File lib/graph.rb, line 99 def vertex_number @vertices.count end
Returns array of vertices
# File lib/graph.rb, line 161 def vertices @vertices end
Protected Instance Methods
Adds edge to graph
# File lib/graph.rb, line 179 def protected_add_edge!(from, to) @vertices[from] << to if @vertices.has_key?(from) && @vertices.has_key?(to) end
Deletes edge from graph
# File lib/graph.rb, line 184 def protected_delete_edge!(from, to) if has_edge?(from, to) @vertices[from].delete(to) @edge_labels.delete(Pair.new(from, to)) end end
Processes the first pass of depth-first search as a step of SCC search algorithm.
Parameters:
+v+: current vertex; +visited+: array of booleans representing which vertices have been processed; +order+: array of vertex exit timestamps.
@return Tuple [visited, order]
of params changed during current step of DFS.
# File lib/graph/scc.rb, line 51 def scc_dfs_first(v, visited, order) visited[v] = true @vertices[v].each do |adj| visited, order = scc_dfs_first adj, visited, order unless visited[adj] end order << v [visited, order] end
Processes the second pass of depth-first search collecting vertices to a component as a step of SCC search algorithm.
Parameters:
+v+: current vertex; +component+: component we are building; +order+: order of timestamps got after first DFS; +transposed+: transposed adjacency list.
@return Tuple [order, component]
of params changed during current step of DFS.
# File lib/graph/scc.rb, line 84 def scc_dfs_second(v, component, order, transposed) order.delete v component << v transposed[v].each do |adj| if order.include? adj order, component = scc_dfs_second adj, component, order, transposed end end [order, component] end
Transposes adjacency list as a step of SCC search algorithm.
g.vertices #=> {1 => [2,3], 2 => [3], 3 => []} g.transpose_adjacency_list #=> {2=>[1], 3=>[1, 2]}
# File lib/graph/scc.rb, line 65 def transpose_adjacency_list # HACK res = Hash.new { |h, k| h[k] = [] } @vertices.each do |vert, adj| adj.each { |x| res[x] << vert } end res end