Class: Networkr::MultiGraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/networkr/graphs/multigraph.rb

Overview

Class for undirected graphs that can store parallel edges.

A MultiGraph holds undirected edges. Self loops are allowed.

See Also

Graph DiGraph

Instance Attribute Summary

Attributes inherited from Graph

#adj, #graph, #nodes

Instance Method Summary collapse

Methods inherited from Graph

#add_node, #children_of, #clear, #deep_copy, #has_edge?, #has_node?, #initialize, #is_directed?, #length, #remove_node, #to_s

Constructor Details

This class inherits a constructor from Networkr::Graph

Instance Method Details

#add_edge(u, v, key = nil, options = {}) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/networkr/graphs/multigraph.rb', line 41

def add_edge(u, v, key=nil, options={})
  if !@adj.include?(u)
    @adj[u] = {}
    @nodes[u] = {}
  end
  if !@adj.include?(v)
    @adj[v] = {}
    @nodes[v] = {}
  end
  if !key
    key = new_edge_key(u, v)
  end
  if @adj[u].include?(v)
    keys = @adj[u][v]
    data = keys[key] || {}
    data.merge!(options)
    keys[key] = data
  else
    data = options
    keys = {}
    keys[key] = data
    @adj[u][v] = keys
    @adj[v][u] = keys
  end
  key
end

#is_multigraph? ⇒ Boolean

Returns:

  • (Boolean) 


91
92
93
 
# File 'lib/networkr/graphs/multigraph.rb', line 91

def is_multigraph?
  true
end

#new_edge_key(u, v) ⇒ Object

returns an unused key for edges between nodes ‘u’ and ‘v’.

The nodes ‘u’ and ‘v’ do not need to be already in the graph.

Notes

The new key is the number of existing edges between ‘u’ and ‘v’, increased if necessary to ensure uniqueness. The first edge will have key 0, the second edge 1, etc. If an edge is removed, new keys may not be in this order.

Parameters

u, v: nodes

Returns

key: int



28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/networkr/graphs/multigraph.rb', line 28

def new_edge_key(u, v)
  if @adj[u] && @adj[u][v]
    keys = @adj[u][v]
    key = keys.length
    while keys.include?(key)
      key += 1
    end
    return key
  else
    return 0
  end
end

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



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/networkr/graphs/multigraph.rb', line 68

def remove_edge(u, v, key=nil)
  keys = @adj[u][v]
  if keys
    if !key
      keys.shift
    else
      if keys[key]
        keys.delete(key)
      else
        raise NetworkrError, "Edge #{u}-#{v} with key #{key} not in graph"
      end
    end
    if keys.length == 0
      @adj[v].delete(v)
      if u != v
        @adj[v].delete(u)
      end
    end
  else
    raise NetworkrError, "Edge #{u}-#{v} not in graph"
  end
end