Class: Networkr::DiGraph

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

Overview

Class for directed graphs.

DiGraphs hold directed edges. Self loops are allowed but parallel edges are not.

See Also

Graph MultiGraph

Instance Attribute Summary collapse

Attributes inherited from Graph

#adj, #graph, #nodes

Instance Method Summary collapse

Methods inherited from Graph

#children_of, #deep_copy, #has_edge?, #has_node?, #is_multigraph?, #length

Constructor Details

#initialize(options = {}) ⇒ DiGraph

Returns a new instance of DiGraph.



15
16
17
18
19
 
# File 'lib/networkr/graphs/digraph.rb', line 15

def initialize(options={})
  super(options)
  @pred = {}
  @succ = @adj
end

Instance Attribute Details

#pred ⇒ Object

Returns the value of attribute pred.



13
14
15
 
# File 'lib/networkr/graphs/digraph.rb', line 13

def pred
  @pred
end

#succ ⇒ Object

Returns the value of attribute succ.



13
14
15
 
# File 'lib/networkr/graphs/digraph.rb', line 13

def succ
  @succ
end

Instance Method Details

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



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/networkr/graphs/digraph.rb', line 50

def add_edge(u, v, options={})
  if !@succ[u]
    @succ[u] = {}
    @pred[u] = {}
    @nodes[u] = {}
  end
  if !@succ[v]
    @succ[v] = {}
    @pred[v] = {}
    @nodes[v] = {}
  end
  data = @adj[u][v] || {}
  data.merge!(options)
  @succ[u][v]=data
  @pred[v][u]=data
end

#add_node(node, options = {}) ⇒ Object 



21
22
23
24
25
26
27
28
29
 
# File 'lib/networkr/graphs/digraph.rb', line 21

def add_node(node, options={})
  if !@succ.include?(node)
    @succ[node] = {}
    @pred[node] = {}
    @nodes[node] = options
  else
    @nodes[node].merge!(options)
  end
end

#clear ⇒ Object 



84
85
86
87
88
89
 
# File 'lib/networkr/graphs/digraph.rb', line 84

def clear
  @succ.clear
  @pred.clear
  @nodes.clear
  @graph.clear
end

#has_predecessor?(u, v) ⇒ Boolean

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/networkr/graphs/digraph.rb', line 80

def has_predecessor?(u, v)
  @pred[u] && @pred[u][v]
end

#has_successor?(u, v) ⇒ Boolean

Returns:

  • (Boolean) 


76
77
78
 
# File 'lib/networkr/graphs/digraph.rb', line 76

def has_successor?(u, v)
  @succ[u] && @succ[u][v]
end

#is_directed? ⇒ Boolean

Returns:

  • (Boolean) 


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

def is_directed?
  true
end

#remove_edge(u, v) ⇒ Object 



67
68
69
70
71
72
73
74
 
# File 'lib/networkr/graphs/digraph.rb', line 67

def remove_edge(u, v)
  if @succ[u] && @succ[u][v]
    @succ[u].delete(v)
    @pred[v].delete(u)
  else
    raise NetworkrError, "Edge #{u}->#{v} not in graph"
  end
end

#remove_node(node) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/networkr/graphs/digraph.rb', line 31

def remove_node(node)
  if @nodes[node]
    @nodes.delete(node)
  else
    raise NetworkrError, "Node #{node} is not in graph"
  end

  nbrs = @succ[node]
  nbrs.each_key do |u|
    @pred[u].delete(node)
  end
  @succ.delete(node)

  @pred[node].each_key do |u|
    @succ[u].delete(node)
  end
  @pred.delete(node)
end

#to_s ⇒ Object 



95
96
97
98
99
100
101
102
103
 
# File 'lib/networkr/graphs/digraph.rb', line 95

def to_s
  res = ''
  @adj.each do |u, nbrs|
    nbrs.each do |v, options|
      res = "#{res}#{u}->#{v} #{options}\n"
    end
  end
  res[0...-1]
end