class Bio::Pathway

Bio::Pathway is a general graph object initially constructed by the list of the ((<Bio::Relation>)) objects. The basic concept of the Bio::Pathway object is to store a graph as an adjacency list (in the instance variable @graph), and converting the list into an adjacency matrix by calling to_matrix method on demand. However, in some cases, it is convenient to have the original list of the ((<Bio::Relation>))s, Bio::Pathway object also stores the list (as the instance variable @relations) redundantly.

Note: you can clear the @relations list by calling clear_relations! method to reduce the memory usage, and the content of the @relations can be re-generated from the @graph by to_relations method.

Attributes

graph[R]

Read-only accessor for the adjacency list of the graph.

index[R]

Read-only accessor for the row/column index (@index) of the adjacency matrix. Contents of the hash @index is created by calling to_matrix method.

label[RW]

Accessor for the hash of the label assigned to the each node. You can label some of the nodes in the graph by passing a hash to the label and select subgraphs which contain labeled nodes only by subgraph method.

hash = { 1 => 'red', 2 => 'green', 5 => 'black' }
g.label = hash
g.label
g.subgraph    # => new graph consists of the node 1, 2, 5 only
relations[R]

Read-only accessor for the internal list of the Bio::Relation objects

Public Class Methods

new(relations, undirected = false) click to toggle source

Initial graph (adjacency list) generation from the list of Relation.

Generate Bio::Pathway object from the list of Bio::Relation objects. If the second argument is true, undirected graph is generated.

r1 = Bio::Relation.new('a', 'b', 1)
r2 = Bio::Relation.new('a', 'c', 5)
r3 = Bio::Relation.new('b', 'c', 3)
list = [ r1, r2, r3 ]
g = Bio::Pathway.new(list, 'undirected')
   # File lib/bio/pathway.rb
41 def initialize(relations, undirected = false)
42   @undirected = undirected
43   @relations = relations
44   @graph = {}         # adjacency list expression of the graph
45   @index = {}         # numbering each node in matrix
46   @label = {}         # additional information on each node
47   self.to_list                # generate adjacency list
48 end

Public Instance Methods

append(rel, add_rel = true) click to toggle source

Add an Bio::Relation object 'rel' to the @graph and @relations. If the second argument is false, @relations is not modified (only useful when genarating @graph from @relations internally).

    # File lib/bio/pathway.rb
144 def append(rel, add_rel = true)
145   @relations.push(rel) if add_rel
146   if @graph[rel.from].nil?
147     @graph[rel.from] = {}
148   end
149   if @graph[rel.to].nil?
150     @graph[rel.to] = {}
151   end
152   @graph[rel.from][rel.to] = rel.relation
153   @graph[rel.to][rel.from] = rel.relation if @undirected
154 end
bellman_ford(root) click to toggle source

Bellman-Ford method for solving the single-source shortest-paths problem in the graph in which edge weights can be negative.

    # File lib/bio/pathway.rb
592 def bellman_ford(root)
593   distance, predecessor = initialize_single_source(root)
594   (self.nodes - 1).times do
595     @graph.each_key do |u|
596       @graph[u].each do |v, w|
597         # relaxing procedure of root -> 'u' -> 'v'
598         if distance[v] > distance[u] + w
599           distance[v] = distance[u] + w
600           predecessor[v] = u
601         end
602       end
603     end
604   end
605   # negative cyclic loop check
606   @graph.each_key do |u|
607     @graph[u].each do |v, w|
608       if distance[v] > distance[u] + w
609         return false
610       end
611     end
612   end
613   return distance, predecessor
614 end
bfs(root)

Alias for the breadth_first_search method.

bfs_shortest_path(node1, node2) click to toggle source

Calculates the shortest path between two nodes by using breadth_first_search method and returns steps and the path as Array.

    # File lib/bio/pathway.rb
450 def bfs_shortest_path(node1, node2)
451   distance, route = breadth_first_search(node1)
452   step = distance[node2]
453   node = node2
454   path = [ node2 ]
455   while node != node1 and route[node]
456     node = route[node]
457     path.unshift(node)
458   end
459   return step, path
460 end
clear_relations!() click to toggle source

Clear @relations array to reduce the memory usage.

    # File lib/bio/pathway.rb
114 def clear_relations!
115   @relations.clear
116 end
clique() click to toggle source

Not implemented yet.

    # File lib/bio/pathway.rb
370 def clique
371   raise NotImplementedError
372 end
cliquishness(node) click to toggle source

Returns completeness of the edge density among the surrounded nodes.

Calculates the value of cliquishness around the 'node'. This value indicates completeness of the edge density among the surrounded nodes.

Note: cliquishness (clustering coefficient) for a directed graph is also calculated. Reference: en.wikipedia.org/wiki/Clustering_coefficient

Note: Cliquishness (clustering coefficient) for a node that has only one neighbor node is undefined. Currently, it returns NaN, but the behavior may be changed in the future.

    # File lib/bio/pathway.rb
388 def cliquishness(node)
389   neighbors = @graph[node].keys
390   sg = subgraph(neighbors)
391   if sg.graph.size != 0
392     edges = sg.edges
393     nodes = neighbors.size
394     complete = (nodes * (nodes - 1))
395     return edges.quo(complete)
396   else
397     return 0.0
398   end
399 end
common_subgraph(graph) click to toggle source

Not implemented yet.

    # File lib/bio/pathway.rb
364 def common_subgraph(graph)
365   raise NotImplementedError
366 end
delete(rel) click to toggle source

Remove an edge indicated by the Bio::Relation object 'rel' from the @graph and the @relations.

    # File lib/bio/pathway.rb
158 def delete(rel)
159   @relations.delete_if do |x|
160     x === rel
161   end
162   @graph[rel.from].delete(rel.to)
163   @graph[rel.to].delete(rel.from) if @undirected
164 end
dfs()

Alias for the depth_first_search method.

Alias for: depth_first_search
dfs_topological_sort() click to toggle source

Topological sort of the directed acyclic graphs (“dags”) by using depth_first_search.

    # File lib/bio/pathway.rb
558 def dfs_topological_sort
559   # sorted by finished time reversely and collect node names only
560   timestamp, = self.depth_first_search
561   timestamp.sort {|a,b| b[1][1] <=> a[1][1]}.collect {|x| x.first }
562 end
dijkstra(root) click to toggle source

Dijkstra method to solve the shortest path problem in the weighted graph.

    # File lib/bio/pathway.rb
566 def dijkstra(root)
567   distance, predecessor = initialize_single_source(root)
568   @graph[root].each do |k, v|
569     distance[k] = v
570     predecessor[k] = root
571   end
572   queue = distance.dup
573   queue.delete(root)
574 
575   while queue.size != 0
576     min = queue.min {|a, b| a[1] <=> b[1]}
577     u = min[0]                # extranct a node having minimal distance
578     @graph[u].each do |k, v|
579       # relaxing procedure of root -> 'u' -> 'k'
580       if distance[k] > distance[u] + v
581         distance[k] = distance[u] + v
582         predecessor[k] = u
583       end
584     end
585     queue.delete(u)
586   end
587   return distance, predecessor
588 end
directed() click to toggle source

Changes the internal state of the graph from 'undirected' to 'directed' and re-generate adjacency list. The undirected graph can be converted to directed graph, however, the edge between two nodes will be simply doubled to both ends.

Note: this method can not be used without the list of the Bio::Relation objects (internally stored in @relations variable). Thus if you already called clear_relations! method, call to_relations first.

   # File lib/bio/pathway.rb
92 def directed
93   if undirected?
94     @undirected = false
95     self.to_list
96   end
97 end
directed?() click to toggle source

Returns true or false respond to the internal state of the graph.

   # File lib/bio/pathway.rb
74 def directed?
75   @undirected ? false : true
76 end
dump_list() click to toggle source

Pretty printer of the adjacency list.

Useful when you want to check the internal state of the adjacency list (for debug purpose etc.) easily.

The result of this method depends on the order of Hash#each (and each_key, etc.), which may be variable with Ruby version and Ruby interpreter variations (JRuby, etc.). For a workaround to remove such dependency, you can use @index to set order of Hash keys. Note that this behavior might be changed in the future.

    # File lib/bio/pathway.rb
293 def dump_list
294   # begin workaround removing depencency to order of Hash#each
295   if @index.empty? then
296     pref = nil
297     enum = @graph
298   else
299     pref = {}.merge(@index)
300     i = pref.values.max
301     @graph.each_key do |node|
302       pref[node] ||= (i += 1)
303     end
304     graph_to_a = @graph.to_a
305     graph_to_a.sort! { |x, y| pref[x[0]] <=> pref[y[0]] }
306     enum = graph_to_a
307   end
308   # end workaround removing depencency to order of Hash#each
309 
310   list = ""
311   enum.each do |from, hash|
312     list << "#{from} => "
313     # begin workaround removing depencency to order of Hash#each
314     if pref then
315       ary = hash.to_a
316       ary.sort! { |x,y| pref[x[0]] <=> pref[y[0]] }
317       hash = ary
318     end
319     # end workaround removing depencency to order of Hash#each
320     a = []
321     hash.each do |to, relation|
322       a.push("#{to} (#{relation})")
323     end
324     list << a.join(", ") + "\n"
325   end
326   list
327 end
dump_matrix(*arg) click to toggle source

Pretty printer of the adjacency matrix.

The dump_matrix method accepts the same arguments as to_matrix. Useful when you want to check the internal state of the matrix (for debug purpose etc.) easily.

This method internally calls to_matrix method. Read documents of to_matrix for important informations.

    # File lib/bio/pathway.rb
274 def dump_matrix(*arg)
275   matrix = self.to_matrix(*arg)
276   sorted = @index.sort {|a,b| a[1] <=> b[1]}
277   "[# " + sorted.collect{|x| x[0]}.join(", ") + "\n" +
278     matrix.to_a.collect{|row| ' ' + row.inspect}.join(",\n") + "\n]"
279 end
edges() click to toggle source

Returns the number of the edges in the graph.

    # File lib/bio/pathway.rb
172 def edges
173   edges = 0
174   @graph.each_value do |v|
175     edges += v.size
176   end
177   edges
178 end
floyd()

Alias for the floyd_warshall method.

Alias for: floyd_warshall
floyd_warshall() click to toggle source

Floyd-Wardshall alogrithm for solving the all-pairs shortest-paths problem on a directed graph G = (V, E).

    # File lib/bio/pathway.rb
619 def floyd_warshall
620   inf = 1 / 0.0
621 
622   m = self.to_matrix(inf, 0)
623   d = m.dup
624   n = self.nodes
625   for k in 0 .. n - 1 do
626     for i in 0 .. n - 1 do
627       for j in 0 .. n - 1 do
628         if d[i, j] > d[i, k] + d[k, j]
629           d[i, j] = d[i, k] + d[k, j]
630         end
631       end
632     end
633   end
634   return d
635 end
Also aliased as: floyd
kruskal() click to toggle source

Kruskal method for finding minimam spaninng trees

    # File lib/bio/pathway.rb
641 def kruskal
642   # initialize
643   rel = self.to_relations.sort{|a, b| a <=> b}
644   index = []
645   for i in 0 .. (rel.size - 1) do
646     for j in (i + 1) .. (rel.size - 1) do
647       if rel[i] == rel[j]
648         index << j
649       end
650     end
651   end
652   index.sort{|x, y| y<=>x}.each do |idx|
653     rel[idx, 1] = []
654   end
655   mst = []
656   seen = Hash.new()
657   @graph.each_key do |x|
658     seen[x] = nil
659   end
660   i = 1
661   # initialize end
662 
663   rel.each do |r|
664     if seen[r.node[0]] == nil
665       seen[r.node[0]] = 0
666     end
667     if seen[r.node[1]] == nil
668       seen[r.node[1]] = 0
669     end
670     if seen[r.node[0]] == seen[r.node[1]] && seen[r.node[0]] == 0
671       mst << r
672       seen[r.node[0]] = i
673       seen[r.node[1]] = i
674     elsif seen[r.node[0]] != seen[r.node[1]]
675       mst << r
676       v1 = seen[r.node[0]].dup
677       v2 = seen[r.node[1]].dup
678       seen.each do |k, v|
679         if v == v1 || v == v2
680           seen[k] = i
681         end
682       end
683     end
684     i += 1
685   end
686   return Pathway.new(mst)
687 end
nodes() click to toggle source

Returns the number of the nodes in the graph.

    # File lib/bio/pathway.rb
167 def nodes
168   @graph.keys.length
169 end
small_world() click to toggle source

Returns frequency of the nodes having same number of edges as hash

Calculates the frequency of the nodes having the same number of edges and returns the value as Hash.

    # File lib/bio/pathway.rb
405 def small_world
406   freq = Hash.new(0)
407   @graph.each_value do |v|
408     freq[v.size] += 1
409   end
410   return freq
411 end
subgraph(list = nil) click to toggle source

Select labeled nodes and generate subgraph

This method select some nodes and returns new Bio::Pathway object consists of selected nodes only. If the list of the nodes (as Array) is assigned as the argument, use the list to select the nodes from the graph. If no argument is assigned, internal property of the graph @label is used to select the nodes.

hash = { 'a' => 'secret', 'b' => 'important', 'c' => 'important' }
g.label = hash
g.subgraph
list = [ 'a', 'b', 'c' ]
 g.subgraph(list)
    # File lib/bio/pathway.rb
343 def subgraph(list = nil)
344   if list
345     @label.clear
346     list.each do |node|
347       @label[node] = true
348     end
349   end
350   sub_graph = Pathway.new([], @undirected)
351   @graph.each do |from, hash|
352     next unless @label[from]
353     sub_graph.graph[from] ||= {}
354     hash.each do |to, relation|
355       next unless @label[to]
356       sub_graph.append(Relation.new(from, to, relation))
357     end
358   end
359   return sub_graph
360 end
to_list() click to toggle source

Graph (adjacency list) generation from the Relations

Generate the adjcancecy list @graph from @relations (called by initialize and in some other cases when @relations has been changed).

    # File lib/bio/pathway.rb
134 def to_list
135   @graph.clear
136   @relations.each do |rel|
137     append(rel, false)        # append to @graph without push to @relations
138   end
139 end
to_matrix(default_value = nil, diagonal_value = nil) click to toggle source

Convert adjacency list to adjacency matrix

Returns the adjacency matrix expression of the graph as a Matrix object. If the first argument was assigned, the matrix will be filled with the given value. The second argument indicates the value of the diagonal constituents of the matrix besides the above.

The result of this method depends on the order of Hash#each (and each_key, etc.), which may be variable with Ruby version and Ruby interpreter variations (JRuby, etc.). For a workaround to remove such dependency, you can use @index to set order of Hash keys. Note that this behavior might be changed in the future. Be careful that @index is overwritten by this method.

    # File lib/bio/pathway.rb
196 def to_matrix(default_value = nil, diagonal_value = nil)
197 
198   #--
199   # Note: following code only fills the outer Array with the reference
200   # to the same inner Array object.
201   #
202   #   matrix = Array.new(nodes, Array.new(nodes))
203   #
204   # so create a new Array object for each row as follows:
205   #++
206 
207   matrix = Array.new
208   nodes.times do
209     matrix.push(Array.new(nodes, default_value))
210   end
211 
212   if diagonal_value
213     nodes.times do |i|
214       matrix[i][i] = diagonal_value
215     end
216   end
217 
218   # assign index number
219   if @index.empty? then
220     # assign index number for each node
221     @graph.keys.each_with_index do |k, i|
222       @index[k] = i
223     end
224   else
225     # begin workaround removing depencency to order of Hash#each
226     # assign index number from the preset @index
227     indices = @index.to_a
228     indices.sort! { |i0, i1| i0[1] <=> i1[1] }
229     indices.collect! { |i0| i0[0] }
230     @index.clear
231     v = 0
232     indices.each do |k, i|
233       if @graph[k] and !@index[k] then
234         @index[k] = v; v += 1
235       end
236     end
237     @graph.each_key do |k|
238       unless @index[k] then
239         @index[k] = v; v += 1
240       end
241     end
242     # end workaround removing depencency to order of Hash#each
243   end
244 
245   if @relations.empty?                # only used after clear_relations!
246     @graph.each do |from, hash|
247       hash.each do |to, relation|
248         x = @index[from]
249         y = @index[to]
250         matrix[x][y] = relation
251       end
252     end
253   else
254     @relations.each do |rel|
255       x = @index[rel.from]
256       y = @index[rel.to]
257       matrix[x][y] = rel.relation
258       matrix[y][x] = rel.relation if @undirected
259     end
260   end
261   Matrix[*matrix]
262 end
to_relations() click to toggle source

Reconstruct @relations from the adjacency list @graph.

    # File lib/bio/pathway.rb
119 def to_relations
120   @relations.clear
121   @graph.each_key do |from|
122     @graph[from].each do |to, w|
123       @relations << Relation.new(from, to, w)
124     end
125   end
126   return @relations
127 end
undirected() click to toggle source

Changes the internal state of the graph from 'directed' to 'undirected' and re-generate adjacency list.

Note: this method can not be used without the list of the Bio::Relation objects (internally stored in @relations variable). Thus if you already called clear_relations! method, call to_relations first.

    # File lib/bio/pathway.rb
106 def undirected
107   if directed?
108     @undirected = true
109     self.to_list
110   end
111 end
undirected?() click to toggle source

Returns true or false respond to the internal state of the graph.

   # File lib/bio/pathway.rb
79 def undirected?
80   @undirected ? true : false
81 end