Module: Plexus::GraphBuilder

Includes:
Enumerable, Dot, Labels
Included in:
DirectedGraphBuilder, Graph, UndirectedGraphBuilder
Defined in:
lib/plexus/graph.rb

Overview

Using only a basic methods set, it implements all the basic functions of a graph. The process is under the control of the pattern AdjacencyGraphBuilder, unless a specific implementation is specified during initialization.

An actual, complete implementation still needs to be done using this cheap result, hence Digraph, UndirectedGraph and their roomates.

Defined Under Namespace

Modules: ClassMethods

Instance Method Summary (collapse)

Methods included from Dot

#dotty, #to_dot, #to_dot_graph, #write_to_graphic_file

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

- (Graph) +(other)

A synonym for merge, but doesn't modify the current graph.



551
552
553
554
555
556
557
558
559
560
561
# File 'lib/plexus/graph.rb', line 551

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

- (Graph) -(other)

Removes all vertices in the specified graph.



567
568
569
570
571
572
573
574
575
576
# File 'lib/plexus/graph.rb', line 567

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

- (Object) <<(edge)

A synonym for add_edge!.



579
580
581
# File 'lib/plexus/graph.rb', line 579

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

- (Graph) add_edge(u, v = nil, l = nil) Also known as: add_arc

Non destructive version AdjacencyGraphBuilder#add_edge! (works on a copy of the graph).



107
108
109
110
# File 'lib/plexus/graph.rb', line 107

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

- (Graph) add_edges(*a) Also known as: add_arcs

Same as add_edges! but works on a copy of the receiver.



192
193
194
195
196
# File 'lib/plexus/graph.rb', line 192

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

- (Graph) add_edges!(*a) Also known as: add_arcs!

Adds all edges mentionned in the specified Enumerable to the edge set.

Elements of the Enumerable can be either two-element arrays or instances of Edge or Arc.



182
183
184
185
# File 'lib/plexus/graph.rb', line 182

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

- (Graph) add_vertex(v, l = nil)

Non destructive version of AdjacencyGraphBuilder#add_vertex! (works on a copy of the graph).



96
97
98
99
# File 'lib/plexus/graph.rb', line 96

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

- (Graph) add_vertices(*a)

Same as add_vertices! but works on copy of the receiver.



169
170
171
172
173
# File 'lib/plexus/graph.rb', line 169

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

- (Graph) add_vertices!(*a)

Adds all specified vertices to the vertex set.



160
161
162
163
# File 'lib/plexus/graph.rb', line 160

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

- (Array) adjacent(x, options = {}) Also known as: graph_adjacent

Computes the adjacent portions of the Graph.

The options specify the parameters about the adjacency search. Note: it is probably more efficently done in the implementation class.

Options Hash (options):

  • :type (Symbol) — default: :vertices

    can be either `:edges` or `:vertices`

  • :direction (Symbol) — default: :all

    can be `:in`, `:out` or `:all`



143
144
145
146
147
148
149
150
151
152
# File 'lib/plexus/graph.rb', line 143

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

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

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

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

Tests two objects to see if they are adjacent.

Note that in this method, one is primarily concerned with finding all adjacent objects in a graph to a given object. The concern is primarily on seeing if two objects touch. For two vertexes, any edge between the two will usually do, but the direction can be specified if needed.



289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
# File 'lib/plexus/graph.rb', line 289

def adjacent?(source, target, direction = :all)
  if source.is_a? Plexus::Arc
    raise NoArcError unless edge? source
    if target.is_a? Plexus::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.is_a? Plexus::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

- (Object) closed_pth_neighborhood(w, p, direction = :all)

Union of all set_neighborhoods reachable among the specified edges.

Definition taken from Jorgen Bang-Jensen, Gregory Gutin, *Digraphs: Theory, Algorithms and Applications*, pg. 46



384
385
386
387
388
389
390
391
392
393
# File 'lib/plexus/graph.rb', line 384

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

- (Graph) complement

Computes the complement of the current graph.



586
587
588
589
590
591
# File 'lib/plexus/graph.rb', line 586

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

- (Boolean) connected?(options = {})

Is the graph connected?

A graph is called connected if every pair of distinct vertices in the graph can be connected through some path. The exact definition depends on whether the graph is directed or not, hence this method should overriden in specific implementations.

This methods implements a lazy routine using the internal vertices hash. If you ever want to check connectivity state using a bfs/dfs algorithm, use the `:algo => :bfs` or `:dfs` option.



323
324
325
326
327
328
329
330
331
332
# File 'lib/plexus/graph.rb', line 323

def connected?(options = {})
  options = options.reverse_merge! :algo => :bfs
  if options[:algo] == (:bfs || :dfs)
    num_nodes = 0
    send(options[:algo]) { |n| num_nodes += 1 }
    return num_nodes == @vertex_dict.size
  else
    !@vertex_dict.collect { |v| degree(v) > 0 }.any? { |check| check == false }
  end
end

- (Integer) degree(v)

Returns the sum of the number in and out edges for the specified vertex.



437
438
439
# File 'lib/plexus/graph.rb', line 437

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

- (Object) each(&block)

Executes the given block for each vertex. It allows for mixing Enumerable in.



246
247
248
# File 'lib/plexus/graph.rb', line 246

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

- (Boolean) edge?(a) - (Boolean) edge?(u, v) Also known as: arc?, has_edge?, has_arc?

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



272
273
274
# File 'lib/plexus/graph.rb', line 272

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

- (Boolean) empty?

Returns true if the graph has no vertex.



342
343
344
# File 'lib/plexus/graph.rb', line 342

def empty?
  vertices.size.zero?
end

- (Boolean) eql?(g) Also known as: ==

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



527
528
529
530
531
532
533
# File 'lib/plexus/graph.rb', line 527

def eql?(g)
  return false unless g.is_a? Plexus::Graph

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

- (Graph) from_array(*a)

Shortcut for creating a Graph.

Using an arry of implicit Arc, specifying the vertices:

Plexus::Graph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s
# => "(1-2)(2-3)(2-4)(4-5)"

Using a Hash for specifying labels along the way:

Plexus::Graph[ [:a,:b] => 3, [:b,:c] => 4 ]  (note: do not use for Multi or Pseudo graphs)


69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# File 'lib/plexus/graph.rb', line 69

def from_array(*a)
  if a.size == 1 and a[0].is_a? Hash
    # Convert to edge class
    a[0].each do |k,v|
      #FIXME, edge class shouldn't be assume here!!!
      if edge_class.include? Plexus::ArcNumber
        add_edge!(edge_class[k[0],k[1],nil,v])
      else
        add_edge!(edge_class[k[0],k[1],v])
      end
    end
    #FIXME, edge class shouldn't be assume here!!!
  elsif a[0].is_a? Plexus::Arc
    a.each{ |e| add_edge!(e); self[e] = e.label}
  elsif a.size % 2 == 0
    0.step(a.size-1, 2) {|i| add_edge!(a[i], a[i+1])}
  else
    raise ArgumentError
  end
  self
end

- (Integer) in_degree(v)

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



429
430
431
# File 'lib/plexus/graph.rb', line 429

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

- (Boolean) include?(x) Also known as: has?

Returns true if the given object is a vertex or an arc of the graph.



349
350
351
# File 'lib/plexus/graph.rb', line 349

def include?(x)
  x.is_a?(Plexus::Arc) ? edge?(x) : vertex?(x)
end

- (Graph) induced_subgraph(v)

Given an array of vertices, computes the induced subgraph.



597
598
599
600
601
# File 'lib/plexus/graph.rb', line 597

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

- (Graph) initialize(*params)

Creates a generic graph.

Raises:

  • (ArgumentError)


34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# File 'lib/plexus/graph.rb', line 34

def initialize(*params)
  raise ArgumentError if params.any? do |p|
    # FIXME: checking wether it's a GraphBuilder (module) is not sufficient
    # and the is_a? redefinition trick (instance_evaling) should be
    # completed by a clever way to check the actual class of p.
    # Maybe using ObjectSpace to get the available Graph classes?
    !(p.is_a? Plexus::GraphBuilder or p.is_a? Array or p.is_a? Hash)
  end

  args = params.last || {}

  class << self
    self
  end.module_eval do
    # These inclusions trigger some validations checks by the way.
    include(args[:implementation]       ? args[:implementation]       : Plexus::AdjacencyGraphBuilder)
    include(args[:algorithmic_category] ? args[:algorithmic_category] : Plexus::DigraphBuilder       )
  end

  implementation_initialize(*params)
end

- (Object) inspect



603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
# File 'lib/plexus/graph.rb', line 603

def inspect
  ## FIXME: broken, it's not updated. The issue's not with inspect, but it's worth mentionning here.
  ## Example:
  ##     dg = Digraph[1,2, 2,3, 2,4, 4,5, 6,4, 1,6]
  ##     dg.add_vertices! 1, 5, "yosh"
  ##     # => Plexus::Digraph[Plexus::Arc[1,2,nil], Plexus::Arc[1,6,nil], Plexus::Arc[2,3,nil], Plexus::Arc[2,4,nil], Plexus::Arc[4,5,nil], Plexus::Arc[6,4,nil]]
  ##     dg.vertex?("yosh")
  ##     # => true
  ##     dg
  ##     # =>Plexus::Digraph[Plexus::Arc[1,2,nil], Plexus::Arc[1,6,nil], Plexus::Arc[2,3,nil], Plexus::Arc[2,4,nil], Plexus::Arc[4,5,nil], Plexus::Arc[6,4,nil]]
  ## the new vertex doesn't show up.
  ## Actually this version of inspect is far too verbose IMO :)
  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 != '' ? '.'+l : '')
end

- (Integer) max_degree

Maximum degree of all vertexes of the graph.



485
486
487
# File 'lib/plexus/graph.rb', line 485

def max_degree
  [max_in_degree, max_out_degree].max
end

- (Integer?) max_in_degree

Maximum in-degree of the graph.



468
469
470
471
# File 'lib/plexus/graph.rb', line 468

def max_in_degree
  return nil if to_a.empty?
  vertices.map { |v| in_degree(v)}.max
end

- (Integer?) max_out_degree

Maximum out-degree of the graph.



476
477
478
479
# File 'lib/plexus/graph.rb', line 476

def max_out_degree
  return nil if to_a.empty?
  vertices.map { |v| out_degree(v)}.max
end

- (Graph) merge(other)

Merges another graph into the receiver.



540
541
542
543
544
545
# File 'lib/plexus/graph.rb', line 540

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

- (Integer) min_degree

Minimum degree of all vertexes of the graph.



461
462
463
# File 'lib/plexus/graph.rb', line 461

def min_degree
  [min_in_degree, min_out_degree].min
end

- (Integer?) min_in_degree

Minimum in-degree of the graph.



444
445
446
447
# File 'lib/plexus/graph.rb', line 444

def min_in_degree
  return nil if to_a.empty?
  to_a.map { |v| in_degree(v) }.min
end

- (Integer?) min_out_degree

Minimum out-degree of the graph.



452
453
454
455
# File 'lib/plexus/graph.rb', line 452

def min_out_degree
  return nil if to_a.empty?
  to_a.map {|v| out_degree(v)}.min
end

- (Object) neighborhood(x, direction = :all)

Returns the neighborhood of the given vertex or arc.

This is equivalent to adjacent, but the type is based on the type of the specified object.



361
362
363
# File 'lib/plexus/graph.rb', line 361

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

- (Integer) num_edges Also known as: number_of_edges

Number of edges.



516
517
518
# File 'lib/plexus/graph.rb', line 516

def num_edges
  edges.size
end

- (Object) open_pth_neighborhood(x, p, direction = :all)

Returns the neighboorhoods reachable in a certain amount of steps from every vertex (or edge) in the specified Enumerable.

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



404
405
406
407
408
409
410
411
412
413
# File 'lib/plexus/graph.rb', line 404

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

- (Integer) out_degree(v)

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



420
421
422
# File 'lib/plexus/graph.rb', line 420

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

- (Boolean) regular?

Is the graph regular, that is are its min degree and max degree equal?



492
493
494
# File 'lib/plexus/graph.rb', line 492

def regular?
  min_degree == max_degree
end

- (Graph) remove_edge(u, v = nil) Also known as: remove_arc

Non destructive version AdjacencyGraphBuilder#remove_edge! (works on a copy of the graph).



127
128
129
130
# File 'lib/plexus/graph.rb', line 127

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

- (Graph) remove_edges(*a) Also known as: remove_arcs, delete_edges, delete_arcs

Same as remove_edges! but works on a copy of the receiver.



237
238
239
240
# File 'lib/plexus/graph.rb', line 237

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

- (Graph) remove_edges!(*a) Also known as: remove_arcs!, delete_edges!, delete_arcs!

Removes all edges mentionned in the specified Enumerable from the graph.

The process relies on remove_edges!.



226
227
228
# File 'lib/plexus/graph.rb', line 226

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

- (Graph) remove_vertex(v)

Non destructive version of AdjacencyGraphBuilder#remove_vertex! (works on a copy of the graph).



117
118
119
120
# File 'lib/plexus/graph.rb', line 117

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

- (Graph) remove_vertices(*a) Also known as: delete_vertices

Same as remove_vertices! but works on a copy of the receiver.



214
215
216
217
# File 'lib/plexus/graph.rb', line 214

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

- (Graph) remove_vertices!(*a) Also known as: delete_vertices!

Removes all vertices mentionned in the specified Enumerable from the graph.

The process relies on remove_vertex!.



205
206
207
# File 'lib/plexus/graph.rb', line 205

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

- (Object) set_neighborhood(x, direction = :all)

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



371
372
373
# File 'lib/plexus/graph.rb', line 371

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

- (Integer) size Also known as: num_vertices

Number of vertices.



499
500
501
# File 'lib/plexus/graph.rb', line 499

def size
  vertices.size
end

- (Boolean) vertex?(v) Also known as: has_vertex?

Returns true if the specified vertex belongs to 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.



258
259
260
# File 'lib/plexus/graph.rb', line 258

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