Module: GRATR::AdjacencyGraph

Includes:
Graph
Included in:
Digraph, UndirectedGraph
Defined in:
lib/gratr/adjacency_graph.rb

Overview

This provides the basic routines needed to implement the Digraph, UndirectedGraph, PseudoGraph, DirectedPseudoGraph, MultiGraph and DirectedPseudoGraph class.

Defined Under Namespace

Classes: ArrayWithAdd

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Graph

#+, #-, #<<, #==, #add_edge, #add_edges, #add_edges!, #add_vertex, #add_vertices, #add_vertices!, #adjacent?, #closed_pth_neighborhood, #complement, #degree, #dotty, #each, #empty?, #eql?, #in_degree, #include?, #induced_subgraph, #inspect, #max_degree, #max_in_degree, #max_out_degree, #merge, #min_degree, #min_in_degree, #min_out_degree, #neighborhood, #num_edges, #num_vertices, #open_pth_neighborhood, #out_degree, #regular?, #remove_edge, #remove_edges, #remove_edges!, #remove_vertex, #remove_vertices, #remove_vertices!, #set_neighborhood, #size, #to_dot, #to_dot_graph, #to_s, #write_to_graphic_file

Methods included from GraphAPI

#chromatic_number, #directed?, #edge_class

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

Class Method Details

.included(cl) ⇒ Object 



199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
# File 'lib/gratr/adjacency_graph.rb', line 199

def self.included(cl)
  # Shortcut for creating a Graph
  #
  #  Example: GRATR::Digraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s =>
  #    "(1-2)(2-3)(2-4)(4-5)"
  # 
  # Or as a Hash for specifying lables
  # GRATR::Digraph[ [:a,:b] => 3, [:b,:c] => 4 ]  (Note: Do not use for Multi or Pseudo graphs)
  def cl.[] (*a)
    result = new
    if a.size == 1 and a[0].kind_of? Hash
      # Convert to edge class
      a[0].each do |k,v|
        if result.edge_class.include? GRATR::ArcNumber
          result.add_edge!(result.edge_class[k[0],k[1],nil,v])
        else
         result.add_edge!(result.edge_class[k[0],k[1],v])
        end 
      end
    elsif a[0].kind_of? GRATR::Arc
      a.each{|e| result.add_edge!(e); result[e] = e.label}
    elsif a.size % 2 == 0    
      0.step(a.size-1, 2) {|i| result.add_edge!(a[i], a[i+1])}
    else
      raise ArgumentError
    end
    result
  end
end

Instance Method Details

#add_edge!(u, v = nil, l = nil, n = nil) ⇒ Object

Adds an edge to the graph Can be called in two basic ways, label is optional

* add_edge!(Arc[source,target], "Label")
* add_edge!(source,target, "Label")



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/gratr/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.kind_of? GRATR::Arc
  return self if not @allow_loops and 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



99
100
101
102
103
 
# File 'lib/gratr/adjacency_graph.rb', line 99

def add_vertex!(vertex, label=nil)
  @vertex_dict[vertex] ||= @edgelist_class.new
  self[vertex] = label if label
  self
end

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



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/gratr/adjacency_graph.rb', line 180

def adjacent(x, options={})
  options[:direction] ||= :out
  if !x.kind_of?(GRATR::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 Arc An O(1) implementation



93
94
95
96
 
# File 'lib/gratr/adjacency_graph.rb', line 93

def edge?(u, v=nil)
  u, v = u.source, u.target if u.kind_of? GRATR::Arc
  vertex?(u) and @vertex_dict[u].include?(v)
end

#edges ⇒ Object

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



164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/gratr/adjacency_graph.rb', line 164

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

#graph_adjacent ⇒ Object 



179
 
# File 'lib/gratr/adjacency_graph.rb', line 179

alias graph_adjacent adjacent

#initialize(*params) ⇒ Object

Initialization parameters can include an Array of edges to add, Graphs to copy (will merge if multiple) :parallel_edges denotes that duplicate edges are allowed :loops denotes that loops are allowed

Raises:

  • (ArgumentError) 


50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/gratr/adjacency_graph.rb', line 50

def initialize(*params)
  @vertex_dict     = Hash.new    
  raise ArgumentError if params.any? do |p| 
    !(p.kind_of? GRATR::Graph or 
      p.kind_of? Array or 
      p == :parallel_edges or
      p == :loops)
  end
  clear_all_labels

  # Basic configuration of adjacency
  @allow_loops    = params.any? {|p| p == :loops}
  @parallel_edges = params.any? {|p| p == :parallel_edges}
  @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.kind_of? GRATR::Graph}.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|
      vertex_label_set(v, vertex_label(v)) if vertex_label(v)
    end  
  end

  # Add all array edges specified
  params.select {|p| p.kind_of? Array}.each do |a|
    0.step(a.size-1, 2) {|i| add_edge!(a[i], a[i+1])}
  end

end

#remove_edge!(u, v = nil) ⇒ Object

Removes an edge from the graph, can be called with source and target or with and object of GRATR::Arc derivation

Raises:

  • (ArgumentError) 


140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/gratr/adjacency_graph.rb', line 140

def remove_edge!(u, v=nil)
  unless u.kind_of? GRATR::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) ⇒ Object

Removes a given vertex from the graph



126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/gratr/adjacency_graph.rb', line 126

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?



89
 
# File 'lib/gratr/adjacency_graph.rb', line 89

def vertex?(v) @vertex_dict.has_key?(v); end

#vertices ⇒ Object

Returns an array of vertices that the graph has



160
 
# File 'lib/gratr/adjacency_graph.rb', line 160

def vertices() @vertex_dict.keys; end