Class: Silicium::Graphs::OrientedGraph

Inherits:
Object
  • Object
show all
Includes:
Silicium::Graphs
Defined in:
lib/graph.rb,
lib/graph/scc.rb

Overview

Class represents oriented graph

Direct Known Subclasses

UnorientedGraph

Instance Method Summary collapse

Methods included from Silicium::Graphs

#add_to_queue, #add_to_stack, #breadth_first_search?, #connected?, #depth_first_search?, #dfs_traverse, #dfs_traverse_recursive, #dfu, #dijkstra_algorithm, #goal_node?, #graph_to_sets, #kruskal_mst, #number_of_connected, #sum_labels

Constructor Details

#initialize(initializer = []) ⇒ OrientedGraph

Returns a new instance of OrientedGraph.



15
16
17
18
19
20
21
22
23
24
25
26
 
# 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

Instance Method Details

#add_edge!(from, to) ⇒ Object

Adds edge to graph



37
38
39
40
 
# 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) ⇒ Object

should only be used in constructor



43
44
45
46
47
 
# 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) ⇒ Object

Adds vertex to graph



30
31
32
33
 
# 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) ⇒ Object

Returns array of vertices which adjacted with vertex

Raises:

  • (GraphError) —

    if graph does not contain vertex



52
53
54
55
 
# 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) ⇒ Object

Deletes edge from graph



139
140
141
142
 
# File 'lib/graph.rb', line 139

def delete_edge!(from, to)
  protected_delete_edge!(from, to)
  @edge_number -= 1
end

#delete_vertex!(vertex) ⇒ Object

Deletes vertex from graph



129
130
131
132
133
134
135
136
 
# 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 ⇒ Object

Returns number of edge labels



114
115
116
 
# File 'lib/graph.rb', line 114

def edge_label_number
  @edge_labels.count
end

#edge_labels ⇒ Object

Returns labels of edges



166
167
168
 
# File 'lib/graph.rb', line 166

def edge_labels
  @edge_labels
end

#edge_number ⇒ Object

Returns number of edges



104
105
106
 
# File 'lib/graph.rb', line 104

def edge_number
  @edge_number
end

#find_strongly_connected_components ⇒ Object

Finds Strongly Connected Components (SCC) in graph. SCC is a subgraph where every vertex is reachable from every other vertex.

Returns:

  • Array of SCC. Each component is represented as Array of vertices in decreasing order of their DFS timestamps.

Author:

  • vaimon



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# 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) ⇒ Object

Returns edge label

Raises:



80
81
82
83
84
85
 
# 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) ⇒ Object

Returns vertex label

Raises:

  • (GraphError) —

    if graph does not contain vertex



90
91
92
93
94
95
96
 
# 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) ⇒ Boolean

Checks if graph contains edge

Returns:

  • (Boolean) 


124
125
126
 
# File 'lib/graph.rb', line 124

def has_edge?(from, to)
  @vertices.has_key?(from) && @vertices[from].include?(to)
end

#has_vertex?(vertex) ⇒ Boolean

Checks if graph contains vertex

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/graph.rb', line 119

def has_vertex?(vertex)
  @vertices.has_key?(vertex)
end

#label_edge!(from, to, label) ⇒ Object

Adds label to edge

Raises:



60
61
62
63
64
65
 
# 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) ⇒ Object

Adds label to vertex

Raises:

  • (GraphError) —

    if graph does not contain vertex



70
71
72
73
74
75
 
# 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! ⇒ Object

Reverses graph



145
146
147
148
149
150
151
152
153
154
155
156
157
 
# 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 ⇒ Object

Returns number of vertex labels



109
110
111
 
# File 'lib/graph.rb', line 109

def vertex_label_number
  @vertex_labels.count
end

#vertex_labels ⇒ Object

Returns labels of vertices



172
173
174
 
# File 'lib/graph.rb', line 172

def vertex_labels
  @vertex_labels
end

#vertex_number ⇒ Object

Returns number of vertices



99
100
101
 
# File 'lib/graph.rb', line 99

def vertex_number
  @vertices.count
end

#vertices ⇒ Object

Returns array of vertices



161
162
163
 
# File 'lib/graph.rb', line 161

def vertices
  @vertices
end