# Class: GraphViz::Theory

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

## Instance Method Summary collapse

• Return the adjancy matrix of the graph.

• Return the critical path for a PERT network.

• Return the degree of the given node.

• Depth First Search.

• Return the incidence matrix of the graph.

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

• constructor

A new instance of Theory.

• Return the laplacian matrix of the graph.

• moore_dijkstra(source, destination).

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

• Return the PageRank in an directed graph.

• Return a liste of range.

• Return `true` if the graph if symmetric, `false` otherwise.

## Constructor Details

### #initialize(graph) ⇒ Theory

Returns a new instance of Theory.

 ``` 5 6 7``` ```# File 'lib/graphviz/theory.rb', line 5 def initialize( graph ) @graph = graph end```

## Instance Method Details

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

 ``` 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

Returns:

• (Boolean)
 ``` 63 64 65``` ```# File 'lib/graphviz/theory.rb', line 63 def symmetric? adjancy_matrix == adjancy_matrix.transpose end```