Module: Plexus::GraphBuilder
- 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
-
#+(other) ⇒ Graph
A synonym for merge, but doesn’t modify the current graph.
-
#-(other) ⇒ Graph
Removes all vertices in the specified graph.
-
#<<(edge) ⇒ Object
A synonym for add_edge!.
-
#add_edge(u, v = nil, l = nil) ⇒ Graph
(also: #add_arc)
Non destructive version AdjacencyGraphBuilder#add_edge! (works on a copy of the graph).
-
#add_edges(*a) ⇒ Graph
(also: #add_arcs)
Same as add_edges! but works on a copy of the receiver.
-
#add_edges!(*a) ⇒ Graph
(also: #add_arcs!)
Adds all edges mentionned in the specified Enumerable to the edge set.
-
#add_vertex(v, l = nil) ⇒ Graph
Non destructive version of AdjacencyGraphBuilder#add_vertex! (works on a copy of the graph).
-
#add_vertices(*a) ⇒ Graph
Same as add_vertices! but works on copy of the receiver.
-
#add_vertices!(*a) ⇒ Graph
Adds all specified vertices to the vertex set.
-
#adjacent(x, options = {}) ⇒ Array
(also: #graph_adjacent)
Computes the adjacent portions of the Graph.
-
#adjacent?(source, target, direction = :all) ⇒ Boolean
Tests two objects to see if they are adjacent.
-
#closed_pth_neighborhood(w, p, direction = :all) ⇒ Object
Union of all set_neighborhoods reachable among the specified edges.
-
#complement ⇒ Graph
Computes the complement of the current graph.
-
#connected?(options = {}) ⇒ Boolean
Is the graph connected?.
-
#degree(v) ⇒ Integer
Returns the sum of the number in and out edges for the specified vertex.
-
#each(&block) ⇒ Object
Executes the given block for each vertex.
-
#edge?(*args) ⇒ Boolean
(also: #arc?, #has_edge?, #has_arc?)
Returns true if u or (u,v) is an edge of the graph.
-
#empty? ⇒ Boolean
Returns true if the graph has no vertex.
-
#eql?(g) ⇒ Boolean
(also: #==)
Equality is defined to be same set of edges and directed?.
-
#from_array(*a) ⇒ Graph
Shortcut for creating a Graph.
-
#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.
-
#include?(x) ⇒ Boolean
(also: #has?)
Returns true if the given object is a vertex or an arc of the graph.
-
#induced_subgraph(v) ⇒ Graph
Given an array of vertices, computes the induced subgraph.
-
#initialize(*params) ⇒ Graph
Creates a generic graph.
- #inspect ⇒ Object
-
#max_degree ⇒ Integer
Maximum degree of all vertexes of the graph.
-
#max_in_degree ⇒ Integer?
Maximum in-degree of the graph.
-
#max_out_degree ⇒ Integer?
Maximum out-degree of the graph.
-
#merge(other) ⇒ Graph
Merges another graph into the receiver.
-
#min_degree ⇒ Integer
Minimum degree of all vertexes of the graph.
-
#min_in_degree ⇒ Integer?
Minimum in-degree of the graph.
-
#min_out_degree ⇒ Integer?
Minimum out-degree of the graph.
-
#neighborhood(x, direction = :all) ⇒ Object
Returns the neighborhood of the given vertex or arc.
-
#num_edges ⇒ Integer
(also: #number_of_edges)
Number of edges.
-
#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.
-
#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.
-
#regular? ⇒ Boolean
Is the graph regular, that is are its min degree and max degree equal?.
-
#remove_edge(u, v = nil) ⇒ Graph
(also: #remove_arc)
Non destructive version AdjacencyGraphBuilder#remove_edge! (works on a copy of the graph).
-
#remove_edges(*a) ⇒ Graph
(also: #remove_arcs, #delete_edges, #delete_arcs)
Same as remove_edges! but works on a copy of the receiver.
-
#remove_edges!(*a) ⇒ Graph
(also: #remove_arcs!, #delete_edges!, #delete_arcs!)
Removes all edges mentionned in the specified Enumerable from the graph.
-
#remove_vertex(v) ⇒ Graph
Non destructive version of AdjacencyGraphBuilder#remove_vertex! (works on a copy of the graph).
-
#remove_vertices(*a) ⇒ Graph
(also: #delete_vertices)
Same as remove_vertices! but works on a copy of the receiver.
-
#remove_vertices!(*a) ⇒ Graph
(also: #delete_vertices!)
Removes all vertices mentionned in the specified Enumerable from the graph.
-
#set_neighborhood(x, direction = :all) ⇒ Object
Union of all neighborhoods of vertices (or edges) in the Enumerable x minus the contents of x.
-
#size ⇒ Integer
(also: #num_vertices)
Number of vertices.
-
#vertex?(v) ⇒ Boolean
(also: #has_vertex?)
Returns true if the specified vertex belongs to the graph.
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.
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.
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).
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.
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!
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).
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.
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.
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.
143 144 145 146 147 148 149 150 151 152 |
# File 'lib/plexus/graph.rb', line 143 def adjacent(x, = {}) d = directed? ? ([:direction] || :out) : :all # Discharge the easy ones first. return [x.source] if x.is_a? Arc and [:type] == :vertices and d == :in return [x.target] if x.is_a? Arc and [:type] == :vertices and d == :out return [x.source, x.target] if x.is_a? Arc and [:type] != :edges and d == :all ([: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.
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
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 |
#complement ⇒ Graph
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 |
#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.
323 324 325 326 327 328 329 330 331 332 |
# File 'lib/plexus/graph.rb', line 323 def connected?( = {}) = .reverse_merge! :algo => :bfs if [:algo] == (:bfs || :dfs) num_nodes = 0 send([: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.
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.
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.
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?
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)
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
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.
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.
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.
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 |
#inspect ⇒ Object
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_degree ⇒ Integer
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 |
#max_in_degree ⇒ Integer?
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 |
#max_out_degree ⇒ Integer?
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 |
#merge(other) ⇒ Graph
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 |
#min_degree ⇒ Integer
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 |
#min_in_degree ⇒ Integer?
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 |
#min_out_degree ⇒ Integer?
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 |
#neighborhood(x, direction = :all) ⇒ 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 |
#num_edges ⇒ Integer 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 |
#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
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.
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?
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).
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.
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!.
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).
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.
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!.
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
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 |
#size ⇒ Integer Also known as: num_vertices
Number of vertices.
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.
258 259 260 |
# File 'lib/plexus/graph.rb', line 258 def vertex?(v) vertices.include?(v) end |