Class: GraphViz::Theory

Inherits:
Object show all
Defined in:
lib/graphviz/theory.rb

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ Theory 



5
6
7
 
# File 'lib/graphviz/theory.rb', line 5

def initialize( graph )
   @graph = graph
end

Instance Method Details

#adjancy_matrix ⇒ Object

Return the adjancy matrix of the graph



10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/graphviz/theory.rb', line 10

def adjancy_matrix
   matrix = GraphViz::Math::Matrix.new( @graph.node_count, @graph.node_count )

   @graph.each_edge { |e|
      x = @graph.get_node(e.node_one(false, false)).index
      y = @graph.get_node(e.node_two(false, false)).index
      matrix[x+1, y+1] = 1
      matrix[y+1, x+1] = 1 if @graph.type == "graph"
   }

   return matrix
end

#bfs(node, &b) ⇒ Object

Breadth First Search



209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/graphviz/theory.rb', line 209

def bfs(node, &b)
   queue = []
   visited_nodes = []
   node = @graph.get_node(node) if node.kind_of? String
   queue << node
   visited_nodes << node

   while not queue.empty?
      node = queue.shift
      b.call(node)
      neighbors(node).each do |n|
         unless visited_nodes.include?(n)
            visited_nodes << n
            queue << n
         end
      end
   end
end

#critical_path ⇒ Object

Return the critical path for a PERT network

If the given graph is not a PERT network, return nul



149
150
151
152
153
154
155
156
 
# File 'lib/graphviz/theory.rb', line 149

def critical_path
   return nil if range.include?(nil) or @graph.type != "digraph"
   r = [ [0, [1]] ]

   critical_path_recursion( distance_matrix, adjancy_matrix, r, [], 0 ).inject( {:distance => 0, :path => []} ) { |_r, item|
      (_r[:distance] < item[0]) ? { :distance => item[0], :path => item[1] } : _r
   }
end

#degree(node) ⇒ Object

Return the degree of the given node



43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/graphviz/theory.rb', line 43

def degree( node )
   degree = 0
   name = node
   if node.kind_of?(GraphViz::Node)
      name = node.id
   end

   @graph.each_edge do |e|
      degree += 1 if e.node_one(false, false) == name or e.node_two(false, false) == name
   end

   return degree
end

#dfs(node, &b) ⇒ Object

Depth First Search



229
230
231
232
 
# File 'lib/graphviz/theory.rb', line 229

def dfs(node, &b)
   visited_nodes = []
   recursive_dfs(node, visited_nodes, &b)
end

#incidence_matrix ⇒ Object

Return the incidence matrix of the graph



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/graphviz/theory.rb', line 24

def incidence_matrix
   tail = (@graph.type == "digraph") ? -1 : 1
   matrix = GraphViz::Math::Matrix.new( @graph.node_count, @graph.edge_count )

   @graph.each_edge { |e|
      x = e.index

      nstart = @graph.get_node(e.node_one(false, false)).index
      nend = @graph.get_node(e.node_two(false, false)).index

      matrix[nstart+1, x+1] = 1
      matrix[nend+1, x+1] = tail
      matrix[nend+1, x+1] = 2 if nstart == nend
   }

   return matrix
end

#incidents(node) ⇒ Object

Return the list of nodes that are incident to the given node (in a directed graph neighbors == incidents)



200
201
202
203
204
205
206
 
# File 'lib/graphviz/theory.rb', line 200

def incidents(node)
   if node.class == String
      @graph.get_node(node).incidents
   else
      node.incidents
   end
end

#laplacian_matrix ⇒ Object

Return the laplacian matrix of the graph



58
59
60
 
# File 'lib/graphviz/theory.rb', line 58

def laplacian_matrix
   return degree_matrix - adjancy_matrix
end

#moore_dijkstra(dep, arv) ⇒ Object

moore_dijkstra(source, destination)



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/graphviz/theory.rb', line 68

def moore_dijkstra( dep, arv )
   dep = @graph.get_node(dep) unless dep.kind_of?(GraphViz::Node)
   arv = @graph.get_node(arv) unless arv.kind_of?(GraphViz::Node)

   m = distance_matrix
   n = @graph.node_count
   # Table des sommets à choisir
   c = [dep.index]
   # Table des distances
   d = []
   d[dep.index] = 0

   # Table des predecesseurs
   pred = []

   @graph.each_node do |name, k|
      if k != dep
         d[k.index] = m[dep.index+1,k.index+1]
         pred[k.index] = dep
      end
   end

   while c.size < n
      # trouver y tel que d[y] = min{d[k];  k sommet tel que k n'appartient pas à c}
      mini = 1.0/0.0
      y = nil
      @graph.each_node do |name, k|
         next if c.include?(k.index)
         if d[k.index] < mini
            mini = d[k.index]
            y = k
         end
      end

      # si ce minimum est ∞ alors sortir de la boucle fin si
      break unless mini.to_f.infinite?.nil?

      c << y.index
      @graph.each_node do |name, k|
         next if c.include?(k.index)
         if d[k.index] > d[y.index] + m[y.index+1,k.index+1]
            d[k.index] = d[y.index] + m[y.index+1,k.index+1]
            pred[k.index] = y
         end
      end
   end

   # Construction du chemin le plus court
   ch = []
   k = arv
   while k.index != dep.index
      ch.unshift(k)
      k = pred[k.index]
   end
   ch.unshift(dep)

   if d[arv.index].to_f.infinite?
      return nil
   else
      return( {
         :path => ch,
         :distance => d[arv.index]
      } )
   end
end

#neighbors(node) ⇒ Object

Return the list of nodes that are directly accessible from given node



191
192
193
194
195
196
197
 
# File 'lib/graphviz/theory.rb', line 191

def neighbors(node)
   if node.class == String
      @graph.get_node(node).neighbors
   else
      node.neighbors
   end
end

#pagerank(damping_factor = 0.85, max_iterations = 100, min_delta = 0.00001) ⇒ Object

Return the PageRank in an directed graph.

  • damping_factor: PageRank dumping factor.

  • max_iterations: Maximum number of iterations.

  • min_delta: Smallest variation required to have a new iteration.



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/graphviz/theory.rb', line 163

def pagerank(damping_factor = 0.85, max_iterations = 100, min_delta = 0.00001)
   return nil unless @graph.directed?

   min_value = (1.0-damping_factor)/@graph.node_count

   pagerank = {}
   @graph.each_node { |_, node|
      pagerank[node] = 1.0/@graph.node_count
   }

   max_iterations.times { |_|
      diff = 0
      @graph.each_node { |_, node|
         rank = min_value
         incidents(node).each { |referent|
            rank += damping_factor * pagerank[referent] / neighbors(referent).size
         }

         diff += (pagerank[node] - rank).abs
         pagerank[node] = rank
      }
      break if diff < min_delta
   }

   return pagerank
end

#range ⇒ Object

Return a liste of range

If the returned array include nil values, there is one or more circuits in the graph



137
138
139
140
141
142
143
144
 
# File 'lib/graphviz/theory.rb', line 137

def range
   matrix = adjancy_matrix
   unseen = (1..matrix.columns).to_a
   result = Array.new(matrix.columns)
   r = 0

   range_recursion( matrix, unseen, result, r )
end

#symmetric? ⇒ Boolean

Return true if the graph if symmetric, false otherwise



63
64
65
 
# File 'lib/graphviz/theory.rb', line 63

def symmetric?
   adjancy_matrix == adjancy_matrix.transpose
end