Parent

GraphViz::Theory

Public Class Methods

new( graph ) click to toggle source
# File lib/graphviz/theory.rb, line 5
def initialize( graph )
  @graph = graph
end

Public Instance Methods

adjancy_matrix() click to toggle source

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

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

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

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

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( dep, arv ) click to toggle source

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

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

Return true if the graph if symmetric, false otherwise

# File lib/graphviz/theory.rb, line 73
def symmetric?
  adjancy_matrix == adjancy_matrix.transpose
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.