Module: GRATR::Graph

Includes:
Enumerable, GraphAPI, Labels
Included in:
AdjacencyGraph
Defined in:
lib/gratr/graph.rb,
lib/gratr/dot.rb,
lib/gratr/search.rb,
lib/gratr/biconnected.rb,
lib/gratr/comparability.rb,
lib/gratr/chinese_postman.rb,
lib/gratr/digraph_distance.rb,
lib/gratr/strong_components.rb

Overview

Using the functions required by the GraphAPI, it implements all the basic functions of a Graph class by using only functions in GraphAPI. An actual implementation still needs to be done, as in Digraph or UndirectedGraph.

Defined Under Namespace

Modules: Biconnected, ChinesePostman, Comparability, Distance, Search, StrongComponents

Instance Method Summary collapse

Methods included from GraphAPI

#add_edge!, #add_vertex!, #chromatic_number, #directed?, #edge_class, #edges, #remove_edge!, #remove_vertex!, #vertices

Methods included from Labels

#[], #[]=, #clear_all_labels, #delete_label, #edge_label, #edge_label_delete, #edge_label_set, #vertex_label, #vertex_label_delete, #vertex_label_set

Instance Method Details

#+(other) ⇒ Object

A synonym for merge, that doesn’t modify the current graph



267
268
269
270
271
272
273
274
275
276
 
# File 'lib/gratr/graph.rb', line 267

def +(other)
  result = self.class.new(self)
  case other
    when GRATR::Graph
      result.merge(other)
    when GRATR::Arc
      result.add_edge!(other)
    else              result.add_vertex!(other)
  end
end

#-(other) ⇒ Object

Remove all vertices in the specified right hand side graph



279
280
281
282
283
284
285
286
287
288
 
# File 'lib/gratr/graph.rb', line 279

def -(other)
  case  other
    when GRATR::Graph
      induced_subgraph(vertices - other.vertices)
    when GRATR::Arc
      self.class.new(self).remove_edge!(other)
    else
      self.class.new(self).remove_vertex!(other)
  end
end

#<<(edge) ⇒ Object

A synonym for add_edge!



291
 
# File 'lib/gratr/graph.rb', line 291

def <<(edge) add_edge!(edge); end

#==(rhs) ⇒ Object

Synonym for eql?



256
 
# File 'lib/gratr/graph.rb', line 256

def ==(rhs) eql?(rhs); end

#add_edge(u, v = nil, l = nil) ⇒ Object Also known as: add_arc

Non destructive version add_edge!, returns modified copy of Graph



53
 
# File 'lib/gratr/graph.rb', line 53

def add_edge(u, v=nil, l=nil) x=self.class.new(self); x.add_edge!(u,v,l); end

#add_edges(*a) ⇒ Object Also known as: add_arcs

See add_edge!



95
 
# File 'lib/gratr/graph.rb', line 95

def add_edges(*a) x=self.class.new(self); x.add_edges!(*a); self; end

#add_edges!(*args) ⇒ Object Also known as: add_arc!

Add all edges in the edges Enumerable to the edge set. Elements of the Enumerable can be both two-element arrays or instances of DirectedArc or UnDirectedArc.



91
 
# File 'lib/gratr/graph.rb', line 91

def add_edges!(*args) args.each { |edge| add_edge!(edge) }; self; end

#add_vertex(v, l = nil) ⇒ Object

Non destructive version of add_vertex!, returns modified copy of Graph



50
 
# File 'lib/gratr/graph.rb', line 50

def add_vertex(v, l=nil) x=self.class.new(self); x.add_vertex!(v,l); end

#add_vertices(*a) ⇒ Object

See add_vertices!



86
 
# File 'lib/gratr/graph.rb', line 86

def add_vertices(*a) x=self.class.new(self); x.add_vertices(*a); self; end

#add_vertices!(*a) ⇒ Object

Add all objects in a to the vertex set.



82
 
# File 'lib/gratr/graph.rb', line 82

def add_vertices!(*a) a.each {|v| add_vertex! v}; self; end

#adjacent(x, options = {}) ⇒ Object

Return Array of adjacent portions of the Graph

x can either be a vertex an edge.
options specifies parameters about the adjacency search
 :type can be either :edges or :vertices (default).
 :direction can be :in, :out(default) or :all.

Note: It is probably more efficently done in implementation.



70
71
72
73
74
75
76
77
78
79
 
# File 'lib/gratr/graph.rb', line 70

def adjacent(x, options={})
  d = directed? ? (options[:direction] || :out) : :all

  # Discharge the easy ones first
  return [x.source] if x.kind_of? Arc and options[:type] == :vertices and d == :in
  return [x.target] if x.kind_of? Arc and options[:type] == :vertices and d == :out
  return [x.source, x.target] if x.kind_of? Arc and options[:type] != :edges and d == :all

  (options[:type] == :edges ? edges : to_a).select {|u| adjacent?(x,u,d)}
end

#adjacent?(source, target, direction = :all) ⇒ Boolean

Tests two objects to see if they are adjacent. direction parameter specifies direction of adjacency, :in, :out, or :all(default) All denotes that if there is any adjacency, then it will return true. Note that the default is different than adjacent where one is primarily concerned with finding all adjacent objects in a graph to a given object. Here the concern is primarily on seeing if two objects touch. For vertexes, any edge between the two will usually do, but the direction can be specified if need be.

Returns:

  • (Boolean) 


134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/gratr/graph.rb', line 134

def adjacent?(source, target, direction=:all)
  if source.kind_of? GRATR::Arc
    raise NoArcError unless edge? source
    if target.kind_of? GRATR::Arc
      raise NoArcError unless edge? target
      (direction != :out and source.source == target.target) or (direction != :in and source.target == target.source)
    else
      raise NoVertexError unless vertex? target
      (direction != :out and source.source == target)  or (direction != :in and source.target == target)
    end
  else
    raise NoVertexError unless vertex? source
    if target.kind_of? GRATR::Arc
      raise NoArcError unless edge? target
      (direction != :out and source == target.target) or (direction != :in and source == target.source)
    else
      raise NoVertexError unless vertex? target
      (direction != :out and edge?(target,source)) or (direction != :in and edge?(source,target))
    end
  end
end

#closed_pth_neighborhood(w, p, direction = :all) ⇒ Object

Union of all set_neighborhoods reachable in p edges Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46



178
179
180
181
182
183
184
185
186
187
 
# File 'lib/gratr/graph.rb', line 178

def closed_pth_neighborhood(w,p,direction=:all)
  if p <= 0
    w 
  elsif p == 1
    (w + set_neighborhood(w,direction)).uniq
  else
    n = set_neighborhood(w, direction)
    (w + n + closed_pth_neighborhood(n,p-1,direction)).uniq
  end
end

#complement ⇒ Object

Return the complement of the current graph



294
295
296
297
298
299
 
# File 'lib/gratr/graph.rb', line 294

def complement
  vertices.inject(self.class.new) do |a,v|
    a.add_vertex!(v)
    vertices.each {|v2| a.add_edge!(v,v2) unless edge?(v,v2) }; a
  end
end

#degree(v) ⇒ Object

Returns the sum of the number in and out edges for a vertex



211
 
# File 'lib/gratr/graph.rb', line 211

def degree(v) in_degree(v) + out_degree(v); end

#dotty(params = {}, dotfile = 'graph.dot') ⇒ Object

Call dotty for the graph which is written to the file ‘graph.dot’ in the # current directory.



72
73
74
75
 
# File 'lib/gratr/dot.rb', line 72

def dotty (params = {}, dotfile = 'graph.dot')
  File.open(dotfile, 'w') {|f| f << to_dot(params) }
  system('dotty', dotfile)
end

#each(&block) ⇒ Object

Execute given block for each vertex, provides for methods in Enumerable



115
 
# File 'lib/gratr/graph.rb', line 115

def each(&block) vertices.each(&block); end

#edge?(*arg) ⇒ Boolean Also known as: arc?

Returns true if u or (u,v) is an Arc of the graph.

Returns:

  • (Boolean) 


124
 
# File 'lib/gratr/graph.rb', line 124

def edge?(*arg) edges.include?(edge_convert(*args)); end

#empty? ⇒ Boolean

Returns true if the graph has no vertex, i.e. num_vertices == 0.

Returns:

  • (Boolean) 


157
 
# File 'lib/gratr/graph.rb', line 157

def empty?() vertices.size.zero?; end

#eql?(g) ⇒ Boolean

Equality is defined to be same set of edges and directed?

Returns:

  • (Boolean) 


247
248
249
250
251
252
253
 
# File 'lib/gratr/graph.rb', line 247

def eql?(g) 
  return false unless g.kind_of? GRATR::Graph

  (g.directed?   == self.directed?)  and 
  (vertices.sort == g.vertices.sort) and
  (g.edges.sort  == edges.sort)
end

#in_degree(v) ⇒ Object

Returns the number of in-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.



208
 
# File 'lib/gratr/graph.rb', line 208

def in_degree(v)  adjacent(v, :direction => :in ).size; end

#include?(x) ⇒ Boolean

Returns true if the given object is a vertex or Arc in the Graph.

Returns:

  • (Boolean) 


161
 
# File 'lib/gratr/graph.rb', line 161

def include?(x) x.kind_of?(GRATR::Arc) ? edge?(x) : vertex?(x); end

#induced_subgraph(v) ⇒ Object

Given an array of vertices return the induced subgraph



302
303
304
305
306
 
# File 'lib/gratr/graph.rb', line 302

def induced_subgraph(v)
  edges.inject(self.class.new) do |a,e| 
    ( v.include?(e.source) and v.include?(e.target) ) ?  (a << e) : a
  end;
end

#inspect ⇒ Object 



308
309
310
311
 
# File 'lib/gratr/graph.rb', line 308

def inspect
  l = vertices.select {|v| self[v]}.map {|u| "vertex_label_set(#{u.inspect},#{self[u].inspect})"}.join('.')
  self.class.to_s + '[' + edges.map {|e| e.inspect}.join(', ') + ']' + (l ? '.'+l : '')
end

#max_degree ⇒ Object

Minimum degree of all vertexes



229
 
# File 'lib/gratr/graph.rb', line 229

def max_degree() [max_in_degree, max_out_degree].max; end

#max_in_degree ⇒ Object

Maximum in-degree



223
 
# File 'lib/gratr/graph.rb', line 223

def max_in_degree() vertices.map {|v| in_degree(v)}.max; end

#max_out_degree ⇒ Object

Maximum out-degree



226
 
# File 'lib/gratr/graph.rb', line 226

def max_out_degree() vertices.map {|v| out_degree(v)}.max; end

#merge(other) ⇒ Object

Merge another graph into this one



259
260
261
262
263
264
 
# File 'lib/gratr/graph.rb', line 259

def merge(other)
  other.vertices.each {|v| add_vertex!(v)      }
  other.edges.each    {|e| add_edge!(e)         }
  other.edges.each    {|e| add_edge!(e.reverse) } if directed? and !other.directed? 
  self 
end

#min_degree ⇒ Object

Minimum degree of all vertexes



220
 
# File 'lib/gratr/graph.rb', line 220

def min_degree() [min_in_degree, min_out_degree].min; end

#min_in_degree ⇒ Object

Minimum in-degree



214
 
# File 'lib/gratr/graph.rb', line 214

def min_in_degree() to_a.map {|v| in_degree(v)}.min; end

#min_out_degree ⇒ Object

Minimum out-degree



217
 
# File 'lib/gratr/graph.rb', line 217

def min_out_degree() to_a.map {|v| out_degree(v)}.min; end

#neighborhood(x, direction = :all) ⇒ Object

Returns the neighboorhood of the given vertex (or Arc) This is equivalent to adjacent, but bases type on the type of object. direction can be :all, :in, or :out



166
167
168
 
# File 'lib/gratr/graph.rb', line 166

def neighborhood(x, direction = :all)
  adjacent(x, :direction => direction, :type => ((x.kind_of? GRATR::Arc) ? :edges : :vertices )) 
end

#num_edges ⇒ Object

Returns the number of edges.



241
 
# File 'lib/gratr/graph.rb', line 241

def num_edges()    edges.size; end

#num_vertices ⇒ Object

Synonym for size.



238
 
# File 'lib/gratr/graph.rb', line 238

def num_vertices() vertices.size; end

#open_pth_neighborhood(x, p, direction = :all) ⇒ Object

Returns the neighboorhoods reachable in p steps from every vertex (or edge) in the Enumerable x

Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46



192
193
194
195
196
197
198
199
200
 
# File 'lib/gratr/graph.rb', line 192

def open_pth_neighborhood(x, p, direction=:all)
  if    p <= 0
    x
  elsif p == 1
    set_neighborhood(x,direction)
  else  
    set_neighborhood(open_pth_neighborhood(x, p-1, direction),direction) - closed_pth_neighborhood(x,p-1,direction)
  end    
end

#out_degree(v) ⇒ Object

Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.



204
 
# File 'lib/gratr/graph.rb', line 204

def out_degree(v) adjacent(v, :direction => :out).size; end

#regular? ⇒ Boolean

Regular

Returns:

  • (Boolean) 


232
 
# File 'lib/gratr/graph.rb', line 232

def regular?() min_degree == max_degree; end

#remove_edge(u, v = nil) ⇒ Object Also known as: remove_arc

Non destructive version of remove_edge!, returns modified copy of Graph



60
 
# File 'lib/gratr/graph.rb', line 60

def remove_edge(u,v=nil) x=self.class.new(self); x.remove_edge!(u,v); end

#remove_edges(*a) ⇒ Object Also known as: remove_arcs

See remove_edges



111
 
# File 'lib/gratr/graph.rb', line 111

def remove_edges(*a) x=self.class.new(self); x.remove_edges(*a); end

#remove_edges!(*a) ⇒ Object Also known as: remove_arc!

Remove all vertices edges by the Enumerable a from the graph by calling remove_edge!



107
 
# File 'lib/gratr/graph.rb', line 107

def remove_edges!(*a) a.each { |e| remove_edges! e }; end

#remove_vertex(v) ⇒ Object

Non destructive version of remove_vertex!, returns modified copy of Graph



57
 
# File 'lib/gratr/graph.rb', line 57

def remove_vertex(v) x=self.class.new(self); x.remove_vertex!(v); end

#remove_vertices(*a) ⇒ Object

See remove_vertices!



103
 
# File 'lib/gratr/graph.rb', line 103

def remove_vertices(*a) x=self.class.new(self); x.remove_vertices(*a); end

#remove_vertices!(*a) ⇒ Object

Remove all vertices specified by the Enumerable a from the graph by calling remove_vertex!.



100
 
# File 'lib/gratr/graph.rb', line 100

def remove_vertices!(*a) a.each { |v| remove_vertex! v }; end

#set_neighborhood(x, direction = :all) ⇒ Object

Union of all neighborhoods of vertices (or edges) in the Enumerable x minus the contents of x Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 4



172
173
174
 
# File 'lib/gratr/graph.rb', line 172

def set_neighborhood(x, direction = :all)
  x.inject(Set.new) {|a,v| a.merge(neighborhood(v,direction))}.reject {|v2| x.include?(v2)}
end

#size ⇒ Object

Returns the number of vertices.



235
 
# File 'lib/gratr/graph.rb', line 235

def size()         vertices.size; end

#to_dot(params = {}) ⇒ Object

Output the dot format as a string



68
 
# File 'lib/gratr/dot.rb', line 68

def to_dot (params={}) to_dot_graph(params).to_s; end

#to_dot_graph(params = {}) ⇒ Object

Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an undirected Graph. params can contain any graph property specified in rdot.rb. If an edge or vertex label is a kind of Hash then the keys which match dot properties will be used as well.



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/gratr/dot.rb', line 42

def to_dot_graph (params = {})
  params['name'] ||= self.class.name.gsub(/:/,'_')
  fontsize   = params['fontsize'] ? params['fontsize'] : '8'
  graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
  edge_klass = directed? ? DOT::DOTDirectedArc : DOT::DOTArc
  vertices.each do |v|
    name = v.to_s
    params = {'name'     => '"'+name+'"',
              'fontsize' => fontsize,
              'label'    => name}
    v_label = vertex_label(v)
    params.merge!(v_label) if v_label and v_label.kind_of? Hash
    graph << DOT::DOTNode.new(params)
  end
  edges.each do |e|
    params = {'from'     => '"'+ e.source.to_s + '"',
              'to'       => '"'+ e.target.to_s + '"',
              'fontsize' => fontsize }
    e_label = edge_label(e)
    params.merge!(e_label) if e_label and e_label.kind_of? Hash
    graph << edge_klass.new(params)
  end
  graph
end

#to_s ⇒ Object

Utility method to show a string representation of the edges of the graph.



244
 
# File 'lib/gratr/graph.rb', line 244

def to_s() edges.to_s; end

#vertex?(v) ⇒ Boolean

Returns true if v is a vertex of the graph. This is a default implementation that is of O(n) average complexity. If a subclass uses a hash to store vertices, then this can be made into an O(1) average complexity operation.

Returns:

  • (Boolean) 


121
 
# File 'lib/gratr/graph.rb', line 121

def vertex?(v) vertices.include?(v); end

#write_to_graphic_file(fmt = 'png', dotfile = 'graph') ⇒ Object

Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.



79
80
81
82
83
84
85
86
87
 
# File 'lib/gratr/dot.rb', line 79

def write_to_graphic_file (fmt='png', dotfile='graph')
  src = dotfile + '.dot'
  dot = dotfile + '.' + fmt
  
  File.open(src, 'w') {|f| f << self.to_dot << "\n"}
  
  system( "dot -T#{fmt} #{src} -o #{dot}" )
  dot
end