Class: GraphViz::Theory

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

Instance Method Summary collapse

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

#adjancy_matrix ⇒ Object

Return the adjancy matrix of the graph



12
13
14
15
16
17
18
19
20
21
22
23
 
# 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 ⇒ Object

Return the critical path for a PERT network

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



165
166
167
168
169
170
171
172
 
# 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) ⇒ Object

Return the degree of the given node



49
50
51
52
53
54
55
56
57
58
59
60
61
 
# 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 ⇒ Object

Return the incidence matrix of the graph



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# 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 ⇒ Object

Return the laplacian matrix of the graph



66
67
68
 
# File 'lib/graphviz/theory.rb', line 66

def laplacian_matrix
  return degree_matrix - adjancy_matrix
end

#moore_dijkstra(dep, arv) ⇒ Object

moore_dijkstra(source, destination)



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
133
134
135
136
137
138
139
140
141
142
143
144
 
# 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 ⇒ Object

Return a liste of range

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



151
152
153
154
155
156
157
158
 
# 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? ⇒ Boolean

Return true if the graph if symmetric, false otherwise

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/graphviz/theory.rb', line 73

def symmetric?
  adjancy_matrix == adjancy_matrix.transpose
end