Module: Plexus::AdjacencyGraphBuilder

Included in:
AdjacencyGraph
Defined in:
lib/plexus/adjacency_graph.rb

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.

Defined Under Namespace

Classes: ArrayWithAdd

Instance Method Summary collapse

Instance Method Details

#add_edge!(arc) ⇒ AdjacencyGraph #add_edge!(source, target, label = nil) ⇒ AdjacencyGraph

Adds an edge to the graph.

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

Overloads:



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

#remove_edge!(a) ⇒ AdjacencyGraph #remove_edge!(u, v) ⇒ AdjacencyGraph

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.

Overloads:

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

#remove_vertex!(v) ⇒ AdjacencyGraph

Removes a given vertex from the graph.

Parameters:

  • v (vertex)

Returns:



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