Class: Networkr::Graph

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

Overview

Class for undirected graphs.

A Graph stores nodes and edges with optional attributes.

Graphs hold undirected edges. Self loops are allowed but parallel edges are not.

Nodes can be arbitrary hashable Ruby objects with optional attributes.

Edges are represented as links between nodes with optional attributes.

Parameters

options: attributes to add to graph as key/value pairs, optional (default is {})

See Also

DiGraph MultiGraph

Examples

Create an empty graph with no nodes and edges.

>>> g = Networkr::Graph.new

g can be grown in several ways

Nodes:

Add one node at a time:

>>> g.add_node(1)

Edges:

Add one edge at a time:

>>> g.add_edge(1, 2)

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute hash. By default these are empty, but can be added or changed using add_node, add_node, or direct manipulation of the attribute hashes named graph, nodes, and adj.

>>> g = Graph(name: “users”) >>> g.graph { name: “users” }

Add/update node attributes using add_node or g.nodes:

>>> g.add_node(1, username: “janedoe”) >>> g.add_node(3, username: “johndoe”) >>> g.nodes { username: “janedoe” } >>> g.nodes[:score] = 10 >>> g.nodes.delete(:score) # remove attribute >>> g.nodes { 1 => { username: “janedoe” }, 3 => { username: “johndoe” } }

Add/update edge attributes using add_edge or g.adj:

>>> g.add_edge(1, 2, weight: 10) >>> g.adj[2] = 4 >>> g.adj[2] { weight: 4 }

Direct Known Subclasses

DiGraph, MultiGraph

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ Graph

Returns a new instance of Graph.



72
73
74
75
76
 
# File 'lib/networkr/graphs/graph.rb', line 72

def initialize(options = {})
  @graph = options
  @nodes = {}
  @adj = {}
end

Instance Attribute Details

#adj ⇒ Object

Returns the value of attribute adj.



70
71
72
 
# File 'lib/networkr/graphs/graph.rb', line 70

def adj
  @adj
end

#graph ⇒ Object

Returns the value of attribute graph.



70
71
72
 
# File 'lib/networkr/graphs/graph.rb', line 70

def graph
  @graph
end

#nodes ⇒ Object

Returns the value of attribute nodes.



70
71
72
 
# File 'lib/networkr/graphs/graph.rb', line 70

def nodes
  @nodes
end

Instance Method Details

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



101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/networkr/graphs/graph.rb', line 101

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

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



78
79
80
81
82
83
84
85
 
# File 'lib/networkr/graphs/graph.rb', line 78

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

#children_of(node) ⇒ Object 



127
128
129
 
# File 'lib/networkr/graphs/graph.rb', line 127

def children_of(node)
  @adj[node]
end

#clear ⇒ Object 



143
144
145
146
147
 
# File 'lib/networkr/graphs/graph.rb', line 143

def clear
  @graph.clear
  @nodes.clear
  @adj.clear
end

#deep_copy ⇒ Object 



149
150
151
 
# File 'lib/networkr/graphs/graph.rb', line 149

def deep_copy
  Marshal.load(Marshal.dump(self))
end

#has_edge?(u, v) ⇒ Boolean

Returns:

  • (Boolean) 


135
136
137
 
# File 'lib/networkr/graphs/graph.rb', line 135

def has_edge?(u, v)
  @adj[u].include?(v)
end

#has_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


131
132
133
 
# File 'lib/networkr/graphs/graph.rb', line 131

def has_node?(node)
  @nodes.include?(node)
end

#is_directed? ⇒ Boolean

Returns:

  • (Boolean) 


157
158
159
 
# File 'lib/networkr/graphs/graph.rb', line 157

def is_directed?
  false
end

#is_multigraph? ⇒ Boolean

Returns:

  • (Boolean) 


153
154
155
 
# File 'lib/networkr/graphs/graph.rb', line 153

def is_multigraph?
  false
end

#length ⇒ Object 



139
140
141
 
# File 'lib/networkr/graphs/graph.rb', line 139

def length
  @nodes.length
end

#remove_edge(u, v) ⇒ Object 



116
117
118
119
120
121
122
123
124
125
 
# File 'lib/networkr/graphs/graph.rb', line 116

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

#remove_node(node) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/networkr/graphs/graph.rb', line 87

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

  nbrs = @adj[node]
  nbrs.each_key do |nbr|
    @adj[nbr].delete(node)
  end
  @adj.delete(node)
end

#to_s ⇒ Object 



161
162
163
164
165
166
167
168
169
 
# File 'lib/networkr/graphs/graph.rb', line 161

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