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

#+(other) ⇒ Graph

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

Parameters:

Returns:

  • (Graph)

    a new 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

#-(other) ⇒ Graph

Removes all vertices in the specified graph.

Parameters:

Returns:



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

#<<(edge) ⇒ Object

A synonym for add_edge!.



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

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

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

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

Parameters:

  • u (vertex)
  • v (vertex) (defaults to: nil)
  • l (Label) (defaults to: nil)

Returns:

  • (Graph)

    a new graph with the supplementary edge



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

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

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

Parameters:

  • *a (#each)

    an Enumerable edges set

Returns:

  • (Graph)

    a modified copy of ‘self`



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

#add_edges!(*a) ⇒ Graph 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.

Parameters:

  • *a (#each)

    an Enumerable edges set

Returns:



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

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

#add_vertex(v, l = nil) ⇒ Graph

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

Parameters:

  • v (vertex)
  • l (Label) (defaults to: nil)

Returns:

  • (Graph)

    a new graph with the supplementary vertex



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

#add_vertices(*a) ⇒ Graph

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

Parameters:

Returns:

  • (Graph)

    a modified copy of ‘self`



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

#add_vertices!(*a) ⇒ Graph

Adds all specified vertices to the vertex set.

Parameters:

  • *a (#each)

    an Enumerable vertices set

Returns:



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

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

#adjacent(x, options = {}) ⇒ Array 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.

Parameters:

  • x (vertex, Edge)

    can either be a vertex an edge

  • options (Hash) (defaults to: {})

    a customizable set of options

Options Hash (options):

  • :type (Symbol) — default: :vertices

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

  • :direction (Symbol) — default: :all

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

Returns:

  • (Array)

    an array of the adjacent portions



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

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

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.

Parameters:

  • source (vertex)
  • target (vertex)
  • direction (Symbol) (defaults to: :all)

    (:all) constraint on the direction of adjacency; may be either ‘:in`, `:out` or `:all`

Returns:

  • (Boolean)


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

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

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

Parameters:

  • w (vertex)
  • p (Edges)
  • direction (Symbol) (defaults to: :all)

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



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

#complementGraph

Computes the complement of the current graph.

Returns:



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

#connected?(options = {}) ⇒ Boolean

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.

Returns:

  • (Boolean)

    ‘true` if the graph is connected, `false` otherwise



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

#degree(v) ⇒ Integer

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

Parameters:

  • v (vertex)

Returns:

  • (Integer)

    degree



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

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

#each(&block) ⇒ Object

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

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

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

Overloads:

  • #edge?(a) ⇒ Boolean

    Parameters:

  • #edge?(u, v) ⇒ Boolean

    Parameters:

    • u (vertex)
    • v (vertex)

Returns:

  • (Boolean)


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

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

#empty?Boolean

Returns true if the graph has no vertex.

Returns:

  • (Boolean)


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

def empty?
  vertices.size.zero?
end

#eql?(g) ⇒ Boolean Also known as: ==

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

Returns:

  • (Boolean)


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

#from_array(*a) ⇒ Graph

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)

Parameters:

  • *a (Array, Hash)

Returns:



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

#in_degree(v) ⇒ Integer

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

Parameters:

  • v (vertex)

Returns:

  • (Integer)

    number of matching edges



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

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

#include?(x) ⇒ Boolean Also known as: has?

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

Parameters:

  • x (vertex, Arc)

Returns:

  • (Boolean)


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

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

#induced_subgraph(v) ⇒ Graph

Given an array of vertices, computes the induced subgraph.

Parameters:

  • v (Array(vertex))

Returns:



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

#initialize(*params) ⇒ Graph

Creates a generic graph.

Parameters:

Returns:

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

#inspectObject



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

#max_degreeInteger

Maximum degree of all vertexes of the graph.

Returns:



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

def max_degree
  [max_in_degree, max_out_degree].max
end

#max_in_degreeInteger?

Maximum in-degree of the graph.

Returns:

  • (Integer, nil)

    returns ‘nil` if the graph is empty



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

#max_out_degreeInteger?

Maximum out-degree of the graph.

Returns:

  • (Integer, nil)

    returns nil if the graph is empty



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

#merge(other) ⇒ Graph

Merges another graph into the receiver.

Parameters:

  • other (Graph)

    the graph to merge in

Returns:



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

#min_degreeInteger

Minimum degree of all vertexes of the graph.

Returns:



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

def min_degree
  [min_in_degree, min_out_degree].min
end

#min_in_degreeInteger?

Minimum in-degree of the graph.

Returns:

  • (Integer, nil)

    returns ‘nil` if the graph is empty



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

#min_out_degreeInteger?

Minimum out-degree of the graph.

Returns:

  • (Integer, nil)

    returns ‘nil` if the graph is empty



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

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

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.

Parameters:

  • x (vertex, Arc)
  • direction (Symbol) (defaults to: :all)

    (:all) can be either ‘:all`, `:in` or `:out`



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

#num_edgesInteger Also known as: number_of_edges

Number of edges.

Returns:

  • (Integer)


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

def num_edges
  edges.size
end

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

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

Parameters:

  • x (Enumerable)
  • p (Integer)

    number of steps to perform

  • direction (Symbol) (defaults to: :all)

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



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

#out_degree(v) ⇒ Integer

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

Parameters:

  • v (vertex)

Returns:

  • (Integer)

    number of matching edges



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

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

#regular?Boolean

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

Returns:

  • (Boolean)


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

def regular?
  min_degree == max_degree
end

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

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

Parameters:

  • u (vertex)
  • v (vertex) (defaults to: nil)

Returns:

  • (Graph)

    a new graph without the specified edge



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

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

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

Parameters:

  • *a (#each)

    an Enumerable edges set

Returns:

  • (Graph)

    a modified copy of ‘self`



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

#remove_edges!(*a) ⇒ Graph 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!.

Parameters:

  • *a (#each)

    an Enumerable edges set

Returns:



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

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

#remove_vertex(v) ⇒ Graph

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

Parameters:

  • v (vertex)

Returns:

  • (Graph)

    a new graph without the specified vertex



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

#remove_vertices(*a) ⇒ Graph Also known as: delete_vertices

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

Parameters:

  • *a (#each)

    a vertex Enumerable set

Returns:

  • (Graph)

    a modified copy of ‘self`



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

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

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

The process relies on remove_vertex!.

Parameters:

  • *a (#each)

    an Enumerable vertices set

Returns:



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

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

Parameters:

  • x (vertex)
  • direction (Symbol) (defaults to: :all)

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



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

#sizeInteger Also known as: num_vertices

Number of vertices.

Returns:

  • (Integer)


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

def size
  vertices.size
end

#vertex?(v) ⇒ Boolean 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.

Parameters:

  • v (vertex)

Returns:

  • (Boolean)


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

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