class Silicium::Graphs::OrientedGraph

Class represents oriented graph

Public Class Methods

new(initializer = []) click to toggle source
# 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

add_edge!(from, to) click to toggle source

Adds edge to graph

# File lib/graph.rb, line 37
def add_edge!(from, to)
  protected_add_edge!(from, to)
  @edge_number += 1
end
add_edge_force!(from, to) click to toggle source

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
add_vertex!(vertex_id) click to toggle source

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
adjacted_with(vertex) click to toggle source

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
delete_edge!(from, to) click to toggle source

Deletes edge from graph

# File lib/graph.rb, line 139
def delete_edge!(from, to)
  protected_delete_edge!(from, to)
  @edge_number -= 1
end
delete_vertex!(vertex) click to toggle source

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
edge_label_number() click to toggle source

Returns number of edge labels

# File lib/graph.rb, line 114
def edge_label_number
  @edge_labels.count
end
edge_labels() click to toggle source

Returns labels of edges

# File lib/graph.rb, line 166
def edge_labels
  @edge_labels
end
edge_number() click to toggle source

Returns number of edges

# File lib/graph.rb, line 104
def edge_number
  @edge_number
end
find_strongly_connected_components() click to toggle source

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
get_edge_label(from, to) click to toggle source

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
get_vertex_label(vertex) click to toggle source

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
has_edge?(from, to) click to toggle source

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
has_vertex?(vertex) click to toggle source

Checks if graph contains vertex

# File lib/graph.rb, line 119
def has_vertex?(vertex)
  @vertices.has_key?(vertex)
end
label_edge!(from, to, label) click to toggle source

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
label_vertex!(vertex, label) click to toggle source

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
reverse!() click to toggle source

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
vertex_label_number() click to toggle source

Returns number of vertex labels

# File lib/graph.rb, line 109
def vertex_label_number
  @vertex_labels.count
end
vertex_labels() click to toggle source

Returns labels of vertices

# File lib/graph.rb, line 172
def vertex_labels
  @vertex_labels
end
vertex_number() click to toggle source

Returns number of vertices

# File lib/graph.rb, line 99
def vertex_number
  @vertices.count
end
vertices() click to toggle source

Returns array of vertices

# File lib/graph.rb, line 161
def vertices
  @vertices
end

Protected Instance Methods

protected_add_edge!(from, to) click to toggle source

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
protected_delete_edge!(from, to) click to toggle source

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
scc_dfs_first(v, visited, order) click to toggle source

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
scc_dfs_second(v, component, order, transposed) click to toggle source

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
transpose_adjacency_list() click to toggle source

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