Class: Doodl::UndirectedGraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/graph.rb

Instance Attribute Summary

Attributes inherited from Graph

#nodes

Instance Method Summary collapse

Methods inherited from Graph

#add_node, #attach_edge_data, #attach_node_data, #contains_edge?, #contains_node?, #detach_edge_data, #detach_node_data, #each_node_passing, #initialize, #out_degree, #source, #target, #to_s

Methods included from GraphGenerator

#gen_binary_tree, #gen_connected_graph, #gen_linear_graph, #gen_mesh_graph, #gen_random_graph, #gen_ring_graph

Constructor Details

This class inherits a constructor from Doodl::Graph

Instance Method Details

#add_edge(source, target, update = false) ⇒ Object

Raises:

  • (ArgumentError) 


303
304
305
306
307
308
309
310
311
312
 
# File 'lib/graph.rb', line 303

def add_edge(source, target, update = false)
  raise ArgumentError unless (@nodes.include?(source) and @nodes.include?(target))
  edge = UndirectedEdge.new(source, target)
  raise ArgumentError if (source.includes_edge?(edge) or target.includes_edge?(edge))
  source.add_edge(edge)
  target.add_edge(edge)
  changed if update
  notify_observers(self)
  return edge
end

#del_edge(edge, update = false) ⇒ Object 



314
315
316
317
318
319
 
# File 'lib/graph.rb', line 314

def del_edge(edge, update = false)
  edge.source.del_edge(edge)
  edge.target.del_edge(edge)
  changed if update
  notify_observers(self)
end

#del_node(node, update = false) ⇒ Object 



291
292
293
294
295
296
297
298
299
300
301
 
# File 'lib/graph.rb', line 291

def del_node(node, update = false)
  each_edge do |edge|
    if (edge.source == node or edge.target == node)
      edge.source.del_edge(edge)
      edge.target.del_edge(edge)
    end
  end
  @nodes.delete(node)
  changed if update
  notify_observers(self)
end

#directed? ⇒ Boolean

Returns:

  • (Boolean) 


268
269
270
 
# File 'lib/graph.rb', line 268

def directed?
  false
end

#each_adjacent(node) ⇒ Object 



345
346
347
348
349
350
351
352
353
 
# File 'lib/graph.rb', line 345

def each_adjacent(node)
  each_adjacent_edge(node) do |edge|
    if target(edge) == node
      yield(source(edge), edge)
    else
      yield(target(edge), edge)
    end
  end
end

#each_adjacent_edge(node) ⇒ Object 



331
332
333
 
# File 'lib/graph.rb', line 331

def each_adjacent_edge(node)
  node.each_edge { |edge| yield(edge) }
end

#each_adjacent_node(node) ⇒ Object 



335
336
337
338
339
340
341
342
343
 
# File 'lib/graph.rb', line 335

def each_adjacent_node(node)
  each_adjacent_edge(node) do |edge|
    if target(edge) == node
      yield(source(edge))
    else
      yield(target(edge))
    end
  end
end

#each_edge ⇒ Object 



321
322
323
324
325
326
327
328
329
 
# File 'lib/graph.rb', line 321

def each_edge
  result = []
  each_node do |source|
    each_adjacent_edge(source) do |edge|
      result << edge
    end
  end
  result.uniq.each { |edge| yield(edge) }
end

#gen_edge(source, target) ⇒ Object 



287
288
289
 
# File 'lib/graph.rb', line 287

def gen_edge(source, target)
  UndirectedEdge.new(source, target)
end

#gen_node ⇒ Object 



277
278
279
 
# File 'lib/graph.rb', line 277

def gen_node
  UndirectedNode.new
end

#get_edge(source, target) ⇒ Object

Raises:

  • (ArgumentError) 


281
282
283
284
285
 
# File 'lib/graph.rb', line 281

def get_edge(source, target)
  raise ArgumentError, "Source and Target must be member of Graph" unless
    (@nodes.include?(source) and @nodes.include?(target))
  source.get_edge(target)
end

#includes_edge?(edge) ⇒ Boolean

Returns:

  • (Boolean) 


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

def includes_edge?(edge)
  edge.source.includes_edge?(edge)
end

#num_edges ⇒ Object 



355
356
357
358
359
360
361
 
# File 'lib/graph.rb', line 355

def num_edges
  num = 0
  each_node do |node|
    num += node.degree
  end
  return  num / 2
end