Included in:
Defined in:

## Overview

This module provides the basic routines needed to implement the specialized builders: DigraphBuilder, UndirectedGraphBuilder, DirectedPseudoGraphBuilder, UndirectedPseudoGraphBuilder, DirectedMultiGraphBuilder and UndirectedMultiGraphBuilder modules, each of them streamlining AdjacencyGraphBuilder's behavior. Those implementations rely on the GraphBuilder.

## Instance Method Summary collapse

• Adds an edge to the graph.

• Adds a vertex to the graph with an optional label.

• FIXME, EFFED UP (but why?).

• Returns true if [u,v] or u is an Arc (an “O(1)” implementation of `edge?`).

• Returns an array of edges, most likely of class Arc or Edge depending upon the type of graph.

• This method is called by the specialized implementations upon graph creation.

• Removes an edge from the graph.

• Removes a given vertex from the graph.

• Returns true if v is a vertex of this Graph (an “O(1)” implementation of `vertex?`).

• Returns an array of vertices that the graph has.

## Instance Method Details

Adds an edge to the graph.

Can be called in two basic ways, label is optional:

Using an explicit Plexus::Arc

Parameters:

Returns:

• `self`

Using vertices to define an arc implicitly

Parameters:

• u (vertex)
• v (vertex)

(nil)

• l (Label)

(nil)

• n (Integer)

(nil) arc number of `(u, v)` (if `nil` and if `u` has an Plexus::ArcNumber, then it will be used)

Returns:

• `self`

 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 # File 'lib/plexus/adjacency_graph.rb', line 109 def add_edge!(u, v = nil, l = nil, n = nil) n = u.number if u.class.include? ArcNumber and n.nil? u, v, l = u.source, u.target, u.label if u.is_a? Plexus::Arc return self if !@allow_loops && u == v n = (@next_edge_number += 1) unless n if @parallel_edges add_vertex!(u) add_vertex!(v) @vertex_dict[u].add(v) (@edge_number[u] ||= @edgelist_class.new).add(n) if @parallel_edges unless directed? @vertex_dict[v].add(u) (@edge_number[v] ||= @edgelist_class.new).add(n) if @parallel_edges end self[n ? edge_class[u,v,n] : edge_class[u,v]] = l if l self end

### #add_vertex!(vertex, label = nil) ⇒ Object

Adds a vertex to the graph with an optional label.

Parameters:

• vertex (vertex(Object))

any kind of Object can act as a vertex

• label (#to_s) (defaults to: nil)

(nil)

 87 88 89 90 91 # File 'lib/plexus/adjacency_graph.rb', line 87 def add_vertex!(vertex, label = nil) @vertex_dict[vertex] ||= @edgelist_class.new self[vertex] = label if label self end

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

FIXME, EFFED UP (but why?)

 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 # File 'lib/plexus/adjacency_graph.rb', line 209 def adjacent(x, options = {}) options[:direction] ||= :out if !x.is_a?(Plexus::Arc) and (options[:direction] == :out || !directed?) if options[:type] == :edges i = -1 @parallel_edges ? @vertex_dict[x].map { |v| e = edge_class[x, v, @edge_number[x][i+=1]]; e.label = self[e]; e } : @vertex_dict[x].map { |v| e = edge_class[x, v]; e.label = self[e]; e } else @vertex_dict[x].to_a end else graph_adjacent(x,options) end end

### #edge?(u, v = nil) ⇒ Boolean

Returns true if [u,v] or u is an Plexus::Arc (an “O(1)” implementation of `edge?`).

Parameters:

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

(nil)

Returns:

• (Boolean)
 78 79 80 81 # File 'lib/plexus/adjacency_graph.rb', line 78 def edge?(u, v = nil) u, v = u.source, u.target if u.is_a? Plexus::Arc vertex?(u) and @vertex_dict[u].include?(v) end

### #edges ⇒ Array

Returns an array of edges, most likely of class Plexus::Arc or Edge depending upon the type of graph.

Returns:

• (Array)
 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 # File 'lib/plexus/adjacency_graph.rb', line 190 def edges @vertex_dict.keys.inject(Set.new) do |a,v| if @parallel_edges and @edge_number[v] @vertex_dict[v].zip(@edge_number[v]).each do |w| s, t, n = v, w[0], w[1] a.add(edge_class[s, t, n, edge_label(s, t, n)]) end else @vertex_dict[v].each do |w| a.add(edge_class[v, w, edge_label(v, w)]) end end a end.to_a end

### #implementation_initialize(*params) ⇒ Object

This method is called by the specialized implementations upon graph creation.

Initialization parameters can include:

• an array of edges to add

• one or several graphs to copy (will be merged if multiple)

• `:parallel_edges` denotes that duplicate edges are allowed

• `:loops denotes` that loops are allowed

Parameters:

• *params (Hash)

the initialization parameters

 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 # File 'lib/plexus/adjacency_graph.rb', line 27 def implementation_initialize(*params) @vertex_dict = Hash.new clear_all_labels # FIXME: could definitely make use of the activesupport helper # extract_options! and facets' reverse_merge! technique # to handle parameters args = (params.pop if params.last.is_a? Hash) || {} # Basic configuration of adjacency. @allow_loops = args[:loops] || false @parallel_edges = args[:parallel_edges] || false @edgelist_class = @parallel_edges ? ArrayWithAdd : Set if @parallel_edges @edge_number = Hash.new @next_edge_number = 0 end # Copy any given graph into this graph. params.select { |p| p.is_a? Plexus::GraphBuilder }.each do |g| g.edges.each do |e| add_edge!(e) edge_label_set(e, edge_label(e)) if edge_label(e) end g.vertices.each do |v| add_vertex!(v) vertex_label_set(v, vertex_label(v)) if vertex_label(v) end end # Add all array edges specified. params.select { |p| p.is_a? Array }.each do |a| 0.step(a.size-1, 2) { |i| add_edge!(a[i], a[i+1]) } end end

Removes an edge from the graph.

Can be called with both source and target as vertex, or with source and object of Plexus::Arc derivation.

Returns `self`.

Parameters:

• a

Returns:

• `self`

Raises:

• (ArgumentError)

if parallel edges are enabled

Returns `self`.

Parameters:

• u (vertex)
• v (vertex)

Returns:

• `self`

Raises:

• (ArgumentError)

if parallel edges are enabled and the Plexus::ArcNumber of `u` is zero

Raises:

• (ArgumentError)
 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 # File 'lib/plexus/adjacency_graph.rb', line 160 def remove_edge!(u, v = nil) unless u.is_a? Plexus::Arc raise ArgumentError if @parallel_edges u = edge_class[u,v] end raise ArgumentError if @parallel_edges and (u.number || 0) == 0 return self unless @vertex_dict[u.source] # It doesn't exist delete_label(u) # Get rid of label if @parallel_edges index = @edge_number[u.source].index(u.number) raise NoArcError unless index @vertex_dict[u.source].delete_at(index) @edge_number[u.source].delete_at(index) else @vertex_dict[u.source].delete(u.target) end self end

Removes a given vertex from the graph.

Parameters:

• v (vertex)

Returns:

• `self`

 134 135 136 137 138 139 140 141 142 143 144 # File 'lib/plexus/adjacency_graph.rb', line 134 def remove_vertex!(v) # FIXME This is broken for multi graphs @vertex_dict.delete(v) @vertex_dict.each_value { |adjList| adjList.delete(v) } @vertex_dict.keys.each do |u| delete_label(edge_class[u,v]) delete_label(edge_class[v,u]) end delete_label(v) self end

### #vertex?(v) ⇒ Boolean

Returns true if v is a vertex of this Graph (an “O(1)” implementation of `vertex?`).

Parameters:

• v (vertex)

Returns:

• (Boolean)
 68 69 70 # File 'lib/plexus/adjacency_graph.rb', line 68 def vertex?(v) @vertex_dict.has_key?(v) end

### #vertices ⇒ Array

Returns an array of vertices that the graph has.

Returns:

• (Array)

graph's vertices

 182 183 184 # File 'lib/plexus/adjacency_graph.rb', line 182 def vertices @vertex_dict.keys end