Return the adjancy matrix of the graph
# File lib/graphviz/theory.rb, line 12 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 )).index y = @graph.get_node(e.node_two( false )).index matrix[x+1, y+1] = 1 matrix[y+1, x+1] = 1 if @graph.type == "graph" } return matrix end
Return the critical path for a PERT network
If the given graph is not a PERT network, return nul
# File lib/graphviz/theory.rb, line 165 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
Return the degree of the given node
# File lib/graphviz/theory.rb, line 49 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) == name or e.node_two(false) == name end return degree end
Return the incidence matrix of the graph
# File lib/graphviz/theory.rb, line 28 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 )).index nend = @graph.get_node(e.node_two( 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
Return the laplacian matrix of the graph
# File lib/graphviz/theory.rb, line 66 def laplacian_matrix return degree_matrix - adjancy_matrix end
moore_dijkstra(source, destination)
# File lib/graphviz/theory.rb, line 80 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.id) k = pred[k.index] end ch.unshift(dep.id) if d[arv.index].to_f.infinite? return nil else return( { :path => ch, :distance => d[arv.index] } ) end end
Return a liste of range
If the returned array include nil values, there is one or more circuits in the graph
# File lib/graphviz/theory.rb, line 151 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
Generated with the Darkfish Rdoc Generator 2.