Module: NetworkX

Defined in:
lib/networkx/flow/preflowpush.rb,
lib/networkx/graph.rb,
lib/networkx/digraph.rb,
lib/networkx/version.rb,
lib/networkx/to_matrix.rb,
lib/networkx/flow/utils.rb,
lib/networkx/multigraph.rb,
lib/networkx/multidigraph.rb,
lib/networkx/operators/all.rb,
lib/networkx/traversals/bfs.rb,
lib/networkx/traversals/dfs.rb,
lib/networkx/operators/unary.rb,
lib/networkx/flow/edmondskarp.rb,
lib/networkx/operators/binary.rb,
lib/networkx/converters/to_csv.rb,
lib/networkx/operators/product.rb,
lib/networkx/converters/to_json.rb,
lib/networkx/link_analysis/hits.rb,
lib/networkx/shortest_path/astar.rb,
lib/networkx/shortest_path/dense.rb,
lib/networkx/traversals/edge_dfs.rb,
lib/networkx/flow/capacityscaling.rb,
lib/networkx/link_analysis/pagerank.rb,
lib/networkx/shortest_path/weighted.rb,
lib/networkx/auxillary_functions/dag.rb,
lib/networkx/auxillary_functions/mis.rb,
lib/networkx/auxillary_functions/mst.rb,
lib/networkx/shortest_path/unweighted.rb,
lib/networkx/auxillary_functions/cycles.rb,
lib/networkx/auxillary_functions/wiener.rb,
lib/networkx/auxillary_functions/cliques.rb,
lib/networkx/flow/shortestaugmentingpath.rb,
lib/networkx/auxillary_functions/vitality.rb,
lib/networkx/auxillary_functions/union_find.rb,
lib/networkx/auxillary_functions/eccentricity.rb

Overview

TODO: Reduce module length

Defined Under Namespace

Classes: CurrentEdge, DiGraph, GlobalRelabelThreshold, Graph, Level, MultiDiGraph, MultiGraph, UnionFind

Constant Summary collapse

VERSION =
'0.1.1'.freeze

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

._build_flow_dict(graph, residual) ⇒ Object

Returns the flowdict of the graph



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# File 'lib/networkx/flow/capacityscaling.rb', line 93

def self._build_flow_dict(graph, residual)
  flow_dict = {}
  inf = Float::INFINITY

  if graph.multigraph?
    graph.nodes.each_key do |u|
      flow_dict[u] = {}
      graph.adj[u].each do |v, uv_edges|
        flow_dict[u][v] = Hash[uv_edges.map do |k, e|
          [k, u != v || (e[:capacity] || inf) <= 0 || (e[:weight] || 0) >= 0 ? 0 : e[:capacity]]
        end]
      end
      residual.adj[u].each do |v, uv_edges|
        flow_dict[u][v].merge!(Hash[uv_edges.map { |_, val| [val[:temp_key][0], val[:flow]] if val[:flow] > 0 }])
      end
    end
  else
    graph.nodes.each_key do |u|
      flow_dict[u] = Hash[graph.adj[u].map do |v, e|
        [v, u != v || (e[:capacity] || inf) <= 0 || (e[:weight] || 0) >= 0 ? 0 : e[:capacity]]
      end]
      merge_dict = {}
      residual.adj[u].each do |v, uv_edges|
        uv_edges.each_value { |attrs| merge_dict[v] = attrs[:flow] if attrs[:flow] > 0 }
      end
      flow_dict[u].merge!(merge_dict)
    end
  end
  flow_dict
end

._build_residual_network(graph) ⇒ Object

Returns the residual graph of the given graph

Raises:

  • (ArgumentError)


48
49
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
86
87
88
# File 'lib/networkx/flow/capacityscaling.rb', line 48

def self._build_residual_network(graph)
  raise ArgumentError, 'Sum of demands should be 0!' unless\
                       graph.nodes.values.map { |attr| attr[:demand] || 0 }.inject(0, :+).zero?
  residual = NetworkX::MultiDiGraph.new(inf: 0)
  residual.add_nodes(graph.nodes.map { |u, attr| [u, excess: (attr[:demand] || 0) * -1, potential: 0] })
  inf = Float::INFINITY
  edge_list = []

  # TODO: Selfloop edges check

  if graph.multigraph?
    graph.adj.each do |u, u_edges|
      u_edges.each do |v, uv_edges|
        uv_edges.each do |k, attrs|
          edge_list << [u, v, k, e] if u != v && (attrs[:capacity] || inf) > 0
        end
      end
    end
  else
    graph.adj.each do |u, u_edges|
      u_edges.each do |v, attrs|
        edge_list << [u, v, 0, attrs] if u != v && (attrs[:capacity] || inf) > 0
      end
    end
  end

  temp_inf = [residual.nodes.map { |_u, attrs| attrs[:excess].abs }.inject(0, :+), edge_list.map do |_, _, _, e|
    (e.key?(:capacity) && e[:capacity] != inf ? e[:capacity] : 0)
  end.inject(0, :+) * 2].max
  inf = temp_inf.zero? ? 1 : temp_inf

  edge_list.each do |u, v, k, e|
    r = [e[:capacity] || inf, inf].min
    w = e[:weight] || 0
    residual.add_edge(u, v, temp_key: [k, true], capacity: r, weight: w, flow: 0)
    residual.add_edge(v, u, temp_key: [k, false], capacity: 0, weight: -w, flow: 0)
  end
  residual.graph[:inf] = inf
  _detect_unboundedness(residual)
  residual
end

._detect_unboundedness(residual) ⇒ Object

Detects the unboundedness in the residual graph

Raises:

  • (ArgumentError)


30
31
32
33
34
35
36
37
38
39
40
41
42
43
# File 'lib/networkx/flow/capacityscaling.rb', line 30

def self._detect_unboundedness(residual)
  g = NetworkX::DiGraph.new
  g.add_nodes(residual.nodes.keys.zip(residual.nodes.values))
  inf = residual.graph[:inf]

  residual.nodes.each do |u, _attr|
    residual.adj[u].each do |v, uv_attrs|
      w = inf
      uv_attrs.each { |_key, edge_attrs| w = [w, edge_attrs[:weight]].min if edge_attrs[:capacity] == inf }
      g.add_edge(u, v, weight: w) unless w == inf
    end
  end
  raise ArgumentError, 'Negative cost cycle of infinite capacity found!' if negative_edge_cycle(g)
end

.activate(node, source, target, levels, residual_nodes) ⇒ Object

Helper function to move a node from inactive set to active set



116
117
118
119
120
121
122
# File 'lib/networkx/flow/preflowpush.rb', line 116

def self.activate(node, source, target, levels, residual_nodes)
  return if node == source || node == target
  return unless level.inactive.include?(node)
  level = levels[residual_nodes[node][:height]]
  level.inactive.delete(node)
  level.active.add(node)
end

.all_pairs_dijkstra(graph, cutoff = nil) ⇒ Array<Object, Array<Hash{ Object => Numeric }, Hash{ Object => Array<Object> }>>

Finds shortest weighted paths and lengths between all nodes

Parameters:

  • graph (Graph, DiGrhelp_dijkaph, MultiGraph, MultiDiGraph)

    a graph

  • cutoff (Numeric, nil) (defaults to: nil)

    cutoff for the dijkstra algorithm

Returns:

  • (Array<Object, Array<Hash{ Object => Numeric }, Hash{ Object => Array<Object> }>>)

    paths and path lengths between all nodes



184
185
186
187
188
# File 'lib/networkx/shortest_path/weighted.rb', line 184

def self.all_pairs_dijkstra(graph, cutoff=nil)
  path = []
  graph.nodes.each_key { |n| path << [n, singlesource_dijkstra(graph, n, nil, cutoff)] }
  path
end

.all_pairs_dijkstra_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>

Finds shortest weighted paths between all nodes

Parameters:

Returns:

  • (Array<Object, Hash{ Object => Array<Object> }>)

    path lengths between all nodes



208
209
210
211
212
# File 'lib/networkx/shortest_path/weighted.rb', line 208

def self.all_pairs_dijkstra_path(graph, cutoff=nil)
  paths = []
  graph.nodes.each_key { |n| paths << singlesource_dijkstra_path(graph, n, cutoff) }
  paths
end

.all_pairs_dijkstra_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>

Finds shortest weighted path length between all nodes

Parameters:

Returns:

  • (Array<Object, Hash{ Object => Numeric }>)

    path lengths between all nodes



196
197
198
199
200
# File 'lib/networkx/shortest_path/weighted.rb', line 196

def self.all_pairs_dijkstra_path_length(graph, cutoff=nil)
  path_lengths = []
  graph.nodes.each_key { |n| path_lengths << [n, singlesource_dijkstra_path_length(graph, n, cutoff)] }
  path_lengths
end

.all_pairs_shortest_path(graph, cutoff = nil) ⇒ Array<Object, Hash {Object => Array<Object> }>

Computes shortest paths to all nodes from all nodes

Parameters:

Returns:

  • (Array<Object, Hash {Object => Array<Object> }>)

    paths for all nodes from all nodes



96
97
98
99
100
# File 'lib/networkx/shortest_path/unweighted.rb', line 96

def self.all_pairs_shortest_path(graph, cutoff=nil)
  shortest_paths = []
  graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path(graph, n, cutoff)] }
  shortest_paths
end

.all_pairs_shortest_path_length(graph, cutoff = nil) ⇒ Array<Object, Array<Object, Numeric>>

Computes shortest path values to all nodes from all nodes

Parameters:

Returns:

  • (Array<Object, Array<Object, Numeric>>)

    path lengths for all nodes from all nodes



47
48
49
50
51
# File 'lib/networkx/shortest_path/unweighted.rb', line 47

def self.all_pairs_shortest_path_length(graph, cutoff=nil)
  shortest_paths = []
  graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path_length(graph, n, cutoff)] }
  shortest_paths
end

.allpairs_bellmanford_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>

Shortest paths between all nodes using Bellman Ford algorithm

Parameters:

Returns:

  • (Array<Object, Hash{ Object => Array<Object> }>)

    path lengths from source to all nodes



361
362
363
364
365
# File 'lib/networkx/shortest_path/weighted.rb', line 361

def self.allpairs_bellmanford_path(graph, cutoff=nil)
  paths = []
  graph.nodes.each_key { |n| paths << [n, singlesource_bellmanford_path(graph, n, cutoff)] }
  paths
end

.allpairs_bellmanford_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>

Shortest path lengths between all nodes using Bellman Ford algorithm

Parameters:

Returns:

  • (Array<Object, Hash{ Object => Numeric }>)

    path lengths from source to all nodes



349
350
351
352
353
# File 'lib/networkx/shortest_path/weighted.rb', line 349

def self.allpairs_bellmanford_path_length(graph, cutoff=nil)
  path_lengths = []
  graph.nodes.each_key { |n| path_lengths << [n, singlesource_bellmanford_path_length(graph, n, cutoff)] }
  path_lengths
end

.ancestors(graph, source) ⇒ Array<Object>

Returns the ancestors of a given node

Parameters:

Returns:

  • (Array<Object>)

    Array of the ancestors

Raises:

  • (ArgumentError)


20
21
22
23
24
# File 'lib/networkx/auxillary_functions/dag.rb', line 20

def self.ancestors(graph, source)
  raise ArgumentError, 'Source is not present in the graph!' unless graph.node?(source)
  anc = single_source_shortest_path_length(graph.reverse, source).map { |u, _| u }.uniq
  anc - [source]
end

.arbitrary_element(iterable) ⇒ Object

Helper function to return an arbitrary element from an iterable object



5
6
7
# File 'lib/networkx/flow/preflowpush.rb', line 5

def self.arbitrary_element(iterable)
  iterable.each { |u| return u }
end

.astar_path(graph, source, target, heuristic = nil) ⇒ Array<Object>

Returns path using astar algorithm between source and target

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    a node to start astar from

  • target (Object)

    a node to end astar

  • heuristic (defaults to: nil)

    [] a lambda to compute heuristic b/w two nodes

Returns:

  • (Array<Object>)

    an array of nodes forming a path between source and target

Raises:

  • (ArgumentError)


13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# File 'lib/networkx/shortest_path/astar.rb', line 13

def self.astar_path(graph, source, target, heuristic=nil)
  warn 'A* is not implemented for MultiGraph and MultiDiGraph'
  raise ArgumentError, 'Either source or target is not in graph' unless graph.node?(source) && graph.node?(target)
  count = ->(i) { i + 1 }
  i = -1
  heuristic ||= (->(_u, _v) { 0 })
  heap = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) }
  heap << [0, count.call(i), source, 0, nil]
  enqueued, explored = {}, {}

  until heap.empty?
    _, _, curnode, dist, parent = heap.pop
    if curnode == target
      path = [curnode]
      node = parent
      until node.nil?
        path << node
        node = explored[node]
      end
      path.reverse
      return path
    end

    next if explored.key?(curnode)

    explored[curnode] = parent

    graph.adj[curnode].each do |u, attrs|
      next if explored.key?(u)
      ncost = dist + (attrs[:weight] || 1)
      if enqueued.key?(u)
        qcost, = enqueued[u]
        next if qcost <= ncost
      else
        h = heuristic.call(u, target)
        enqueued[u] = ncost, h
        heap << [ncost + h, count.call(i), u, ncost, curnode]
      end
    end
  end
  raise ArgumentError, 'Target not reachable!'
end

.astar_path_length(graph, source, target, heuristic = nil) ⇒ Numeric

Returns astar path length b/w source and target

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    a node to start astar from

  • target (Object)

    a node to end astar

  • heuristic (defaults to: nil)

    [] a lambda to compute heuristic b/w two nodes

Returns:

  • (Numeric)

    the length of the path

Raises:

  • (ArgumentError)


64
65
66
67
68
69
70
# File 'lib/networkx/shortest_path/astar.rb', line 64

def self.astar_path_length(graph, source, target, heuristic=nil)
  raise ArgumentError, 'Either source or target is not in graph' unless graph.node?(source) && graph.node?(target)
  path = astar_path(graph, source, target, heuristic)
  path_length = 0
  (1..(path.length - 1)).each { |i| path_length += (graph.adj[path[i - 1]][path[i]][:weight] || 1) }
  path_length
end

.augment(residual, inf, path) ⇒ Object

Helper function to augment the flow in a residual graph

Raises:

  • (ArgumentError)


5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# File 'lib/networkx/flow/edmondskarp.rb', line 5

def self.augment(residual, inf, path)
  flow = inf
  path_first_elem = path.shift
  u = path_first_elem
  path.each do |v|
    flow = [flow, residual.adj[u][v][:capacity] - residual.adj[u][v][:flow]].min
    u = v
  end
  raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf
  u = path_first_elem
  path.each do |v|
    residual.adj[u][v][:flow] += flow
    residual.adj[v][u][:flow] -= flow
    u = v
  end
  flow
end

.authority_matrix(graph) ⇒ NMatrix

Computes authority matrix for the graph

Parameters:

Returns:

  • (NMatrix)

    authority matrix for the graph



45
46
47
48
# File 'lib/networkx/link_analysis/hits.rb', line 45

def self.authority_matrix(graph)
  matrix, = to_matrix(graph, 0)
  matrix.transpose.dot matrix
end

.bellmanford_path(graph, source, target) ⇒ Array<Object>

Shortest path from source to target using Bellman Ford algorithm

Parameters:

Returns:

  • (Array<Object>)

    path from source to target



314
315
316
317
# File 'lib/networkx/shortest_path/weighted.rb', line 314

def self.bellmanford_path(graph, source, target)
  _, path = singlesource_bellmanford(graph, source, target)
  path
end

.bellmanford_path_length(graph, source, target) ⇒ Numeric

Length of shortest path from source to target using Bellman Ford algorithm

Parameters:

Returns:

  • (Numeric)

    distance between source and target

Raises:

  • (ArgumentError)


299
300
301
302
303
304
305
# File 'lib/networkx/shortest_path/weighted.rb', line 299

def self.bellmanford_path_length(graph, source, target)
  return 0 if source == target
  weight = get_weight(graph)
  length = help_bellman_ford(graph, [source], weight, nil, nil, nil, nil, target=target)
  raise ArgumentError, 'Node not reachable!' unless length.key?(target)
  length[target]
end

.bellmanford_predecesor_distance(graph, source, target = nil, cutoff = nil) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>

Finds shortest weighted path lengths and predecessors on shortest paths

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    source

  • target (Object, nil) (defaults to: nil)

    target

  • cutoff (Numeric, nil) (defaults to: nil)

    cutoff for the dijkstra algorithm

Returns:

  • (Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>)

    predecessors and distances

Raises:

  • (ArgumentError)


271
272
273
274
275
276
277
278
279
280
# File 'lib/networkx/shortest_path/weighted.rb', line 271

def self.bellmanford_predecesor_distance(graph, source, target=nil, cutoff=nil)
  raise ArgumentError, 'Node not found!' unless graph.node?(source)
  weight = get_weight(graph)
  # TODO: Detection of selfloop edges
  dist = {source => 0}
  pred = {source => []}
  return [pred, dist] if graph.nodes.length == 1
  dist = help_bellman_ford(graph, [source], weight, pred, nil, dist, cutoff, target)
  [pred, dist]
end

.bfs_edges(graph, source) ⇒ Object

Returns edges of the graph travelled in breadth first fashion

Examples:

NetworkX.bfs_edges(graph, source)

Parameters:

Raises:

  • (KeyError)


11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# File 'lib/networkx/traversals/bfs.rb', line 11

def self.bfs_edges(graph, source)
  raise KeyError, "There exists no node names #{source} in the given graph." unless graph.node?(source)
  bfs_edges = []
  visited = [source]
  queue = Queue.new.push([source, graph.neighbours(source)])
  until queue.empty?
    parent, children = queue.pop
    children.each_key do |child|
      next if visited.include?(child)
      bfs_edges << [parent, child]
      visited << child
      queue.push([child, graph.neighbours(child)])
    end
  end
  bfs_edges
end

.bfs_predecessors(graph, source) ⇒ Object

Returns predecessor child pair of the graph travelled in breadth first fashion

Examples:

NetworkX.bfs_predecessors(graph, source)

Parameters:



52
53
54
55
56
57
# File 'lib/networkx/traversals/bfs.rb', line 52

def self.bfs_predecessors(graph, source)
  bfs_edges = bfs_edges(graph, source)
  predecessors = {}
  bfs_edges.each { |u, v| predecessors[v] = u }
  predecessors
end

.bfs_successors(graph, source) ⇒ Object

Returns parent successor pair of the graph travelled in breadth first fashion

Examples:

NetworkX.bfs_successors(graph, source)

Parameters:



35
36
37
38
39
40
41
42
43
# File 'lib/networkx/traversals/bfs.rb', line 35

def self.bfs_successors(graph, source)
  bfs_edges = bfs_edges(graph, source)
  successors = {}
  bfs_edges.each do |u, v|
    successors[u] = [] if successors[u].nil?
    successors[u] << v
  end
  successors
end

.bidirectional_bfs(residual, source, target) ⇒ Object

Helper function for the bidirectional bfs



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# File 'lib/networkx/flow/edmondskarp.rb', line 26

def self.bidirectional_bfs(residual, source, target)
  pred, succ = {source => nil}, {target => nil}
  q_s, q_t = [source], [target]
  loop do
    q = []
    if q_s.length <= q_t.length
      q_s.each do |u|
        residual.adj[u].each do |v, uv_attrs|
          next unless !pred.include?(v) && (uv_attrs[:flow] < uv_attrs[:capacity])
          pred[v] = u
          return [v, pred, succ] if succ.key?(v)
          q << v
        end
      end
      return [nil, nil, nil] if q.empty?
    else
      q_t.each do |u|
        residual.pred[u].each do |v, uv_attrs|
          next unless !succ.key?(v) && uv_attrs[:flow] < uv_attrs[:capacity]
          succ[v] = u
          return [v, pred, succ] if pred.key?(v)
          q << v
        end
      end
      return [nil, nil, nil] if q.empty?
      q_t = q
    end
  end
end

.build_flow_dict(graph, residual) ⇒ Hash{ Object => Hash{ Object => Numeric }] flowdict containing all the flow values in the edges

Build flow dictionary of a graph from its residual graph

Parameters:

Returns:

  • (Hash{ Object => Hash{ Object => Numeric }] flowdict containing all the flow values in the edges)

    Hash{ Object => Hash{ Object => Numeric }] flowdict containing all the flow values in the edges



151
152
153
154
155
156
157
158
159
# File 'lib/networkx/flow/utils.rb', line 151

def self.build_flow_dict(graph, residual)
  flow_dict = {}
  graph.edges.each do |u, u_edges|
    flow_dict[u] = {}
    u_edges.each_key { |v| flow_dict[u][v] = 0 }
    u_edges.each_key { |v| flow_dict[u][v] = residual[u][v][:flow] if residual[u][v][:flow] > 0 }
  end
  flow_dict
end

.build_residual_network(graph) ⇒ DiGraph

Builds a residual graph from a constituent graph

Parameters:

Returns:

Raises:

  • (NotImplementedError)


63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# File 'lib/networkx/flow/utils.rb', line 63

def self.build_residual_network(graph)
  raise NotImplementedError, 'MultiGraph and MultiDiGraph not supported!' if graph.multigraph?

  r_network = NetworkX::DiGraph.new(inf: 0, flow_value: 0)
  r_network.add_nodes(graph.nodes.keys)
  inf = Float::INFINITY
  edge_list = []

  graph.adj.each do |u, u_edges|
    require 'spec_helper'
    RSpec.describe NetworkX::DiGraph do
      subject { graph }

      let(:graph) { described_class.new }

      before do
        graph.add_edge(1, 2)
        graph.add_edge(2, 4)
      end

      context 'when capacity_scaling is called' do
        subject { NetworkX.capacity_scaling(graph) }

        it { is_expected.to eq([0, {1=>{2=>0}, 2=>{4=>0}, 4=>{}}]) }
      end
    end

    u_edges.each do |v, uv_attrs|
      edge_list << [u, v, uv_attrs] if (uv_attrs[:capacity] || inf) > 0 && u != v
    end
  end

  inf_chk = 3 * edge_list.inject(0) do |result, arr|
    arr[2].key?(:capacity) && arr[2][:capacity] != inf ? (result + arr[2][:capacity]) : result
  end
  inf = inf_chk.zero? ? 1 : inf_chk

  if graph.directed?
    edge_list.each do |u, v, attrs|
      r = [attrs[:capacity] || inf, inf].min
      if r_network.adj[u][v].nil?
        r_network.add_edge(u, v, capacity: r)
        r_network.add_edge(v, u, capacity: 0)
      else
        r_network[u][v][:capacity] = r
      end
    end
  else
    edge_list.each do |u, v, attrs|
      r = [attrs[:capacity] || inf, inf].min
      r_network.add_edge(u, v, capacity: r)
      r_network.add_edge(v, u, capacity: r)
    end
  end
  r_network.graph[:inf] = inf
  r_network
end

.capacity_scaling(graph) ⇒ Array<Numeric, Hash{ Object => Hash{ Object => Numeric } }>

Computes max flow using capacity scaling algorithm

Parameters:

Returns:

  • (Array<Numeric, Hash{ Object => Hash{ Object => Numeric } }>)

    flow cost and flowdict containing all the flow values in the edges



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
# File 'lib/networkx/flow/capacityscaling.rb', line 139

def self.capacity_scaling(graph)
  residual = _build_residual_network(graph)
  inf = Float::INFINITY
  flow_cost = 0

  # TODO: Account cost of self-loof edges

  wmax = ([-inf] + residual.adj.each_with_object([]) do |u, arr|
                     u[1].each { |_, key_attrs| key_attrs.each { |_, attrs| arr << attrs[:capacity] } }
                   end).max

  return flow_cost, _build_flow_dict(graph, residual) if wmax == -inf
  r_nodes = residual.nodes
  r_adj = residual.adj

  delta = 2 ** Math.log2(wmax).floor
  while delta >= 1
    r_nodes.each do |u, u_attrs|
      p_u = u_attrs[:potential]
      r_adj[u].each do |v, uv_edges|
        uv_edges.each do |_k, e|
          flow = e[:capacity]
          next unless e[:weight] - p_u + r_nodes[v][:potential] < 0
          flow = e[:capacity] - e[:flow]
          next unless flow >= delta
          e[:flow] += flow
          r_adj[v][u].each_key do |val|
            val[:flow] += val[:temp_key][0] == e[:temp_key][0] && val[:temp_key][1] != e[:temp_key][1] ? -flow : 0
          end
          r_nodes[u][:excess] -= flow
          r_nodes[v][:excess] += flow
        end
      end
    end

    s_set = Set.new
    t_set = Set.new

    residual.nodes.each do |u, _attrs|
      excess = r_nodes[u][:excess]
      if excess >= delta
        s_set.add(u)
      elsif excess <= -delta
        t_set.add(u)
      end
    end

    while !s_set.empty? && !t_set.empty?
      s = arbitrary_element
      t = nil
      d = {}
      pred = {s => nil}
      h = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) }
      h_dict = {s => 0}
      h << [0, count, s]
      until h.empty?
        d_u, _, u = h.pop
        h_dict.delete(u)
        d[u] = d_u
        if t_set.include?(u)
          t = u
          break
        end
        p_u = r_nodes[u][:potential]
        r_adj[u].each do |v, uv_edges|
          next if d.key?(v)
          wmin = inf
          uv_edges.each_value do |e|
            next unless e[:capacity] - e[:flow] >= delta
            w = e[:weight]
            next unless w < wmin
            wmin = w
          end
          next if wmin == inf
          d_v = d_u + wmin - p_u + r_nodes[v][:potential]
          next unless h_dict[v] > d_v
          h << [d_v, count, v]
          h_dict[v] = d_v
          pred[v] = [u, kmin, emin]
        end
      end

      if !t.nil?
        while u != s
          v = u
          u, k, e = pred[v]
          e[:flow] += delta
          r_adj[v][u].each_key do |val|
            val[:flow] += val[:temp_key][0] == k[0] && val[:temp_key][1] != k[1] ? -delta : 0
          end
        end
        r_nodes[s][:excess] -= delta
        r_nodes[t][:excess] += delta
        s_set.delete(s) if r_nodes[s][:excess] < delta
        t_set.delete(t) if r_nodes[t][:excess] > -delta
        d_t = d[t]
        d.each { |node, d_u_node| r_nodes[node][:potential] -= (d_u_node - d_t) }
      else
        s_set.delete(s)
      end
    end
    delta = (delta / 2).floor
  end

  r_nodes.each_value { |attrs| raise ArgumentError, 'No flow satisfying all demands!' if attrs[:excess] != 0 }

  residual.nodes.each_key do |node|
    residual.adj[node].each_value do |uv_edges|
      uv_edges.each_value do |k_attrs|
        flow = k_attrs[:flow]
        flow_cost += (flow * k_attrs[:weight])
      end
    end
  end
  [flow_cost, _build_flow_dict(graph, residual)]
end

.cartesian_product(g_1, g_2) ⇒ Graph, ...

Returns the cartesian product of two graphs

Parameters:

Returns:



133
134
135
136
137
138
139
# File 'lib/networkx/operators/product.rb', line 133

def self.cartesian_product(g_1, g_2)
  g = init_product_graph(g_1, g_2)
  g.add_nodes(node_product(g_1, g_2))
  g.add_edges(edges_cross_nodes(g_1, g_2))
  g.add_edges(nodes_cross_edges(g_1, g_2))
  g
end

.closeness_vitality(graph, node) ⇒ Numeric

Returns the closeness vitality of a node

Parameters:

  • graph (Graph, DiGraph)

    a graph

  • node (Object)

    node to compute closeness vitality of

Returns:

  • (Numeric)

    closeness vitality of the given node



8
9
10
11
12
# File 'lib/networkx/auxillary_functions/vitality.rb', line 8

def self.closeness_vitality(graph, node)
  before = wiener_index(graph)
  after = wiener_index(graph.subgraph(graph.nodes.keys - [node]))
  before - after
end

.complement(graph) ⇒ Graph, ...

Performs the complement operation on the graph

Parameters:

Returns:



7
8
9
10
11
12
13
14
15
16
# File 'lib/networkx/operators/unary.rb', line 7

def self.complement(graph)
  result = Marshal.load(Marshal.dump(graph))
  result.clear

  result.add_nodes(graph.nodes.map { |u, attrs| [u, attrs] })
  graph.adj.each do |u, u_edges|
    graph.nodes.each { |v, attrs| result.add_edge(u, v, attrs) if !u_edges.key?(v) && u != v }
  end
  result
end

.compose(g_1, g_2) ⇒ Graph, ...

Performs the composition of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError)


173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
# File 'lib/networkx/operators/binary.rb', line 173

def self.compose(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

  raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?

  result.add_nodes(g_1.nodes.map { |u, attrs| [u, attrs] })
  result.add_nodes(g_2.nodes.map { |u, attrs| [u, attrs] })

  if g_1.multigraph?
    g_1.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, attrs) } } }
    g_2.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, attrs) } } }
  else
    g_1.adj.each { |u, u_edges| u_edges.each { |v, attrs| result.add_edge(u, v, attrs) } }
    g_2.adj.each { |u, u_edges| u_edges.each { |v, attrs| result.add_edge(u, v, attrs) } }
  end
  result
end

.compose_all(graphs) ⇒ Graph, ...

Performs the composition of many graphs

Parameters:

Returns:

Raises:

  • (ArgumentError)


52
53
54
55
56
57
58
59
60
# File 'lib/networkx/operators/all.rb', line 52

def self.compose_all(graphs)
  raise ArgumentError, 'Argument array is empty' if graphs.empty?
  result = graphs.shift

  graphs.each do |graph|
    result = NetworkX.compose(result, graph)
  end
  result
end

.convert_to_distinct_labels(graph, starting_int = -1)) ⇒ Object

Transforms the labels of the nodes of the graphs so that they are disjoint.



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# File 'lib/networkx/operators/binary.rb', line 19

def self.convert_to_distinct_labels(graph, starting_int=-1)
  new_graph = Marshal.load(Marshal.dump(graph))
  new_graph.clear

  idx_dict = Hash[graph.nodes.keys.map do |v|
    starting_int += 1
    [v, starting_int]
  end]

  graph.nodes.each do |u, attrs|
    new_graph.add_node(u.to_s + idx_dict[u].to_s, attrs)
  end

  graph.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if graph.multigraph?
        uv_attrs.each do |_k, attrs|
          new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, attrs)
        end
      else
        new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, uv_attrs)
      end
    end
  end
  new_graph
end

.countObject



126
127
128
129
# File 'lib/networkx/flow/capacityscaling.rb', line 126

def self.count
  @itr += 1
  @itr
end

.cycle_basis(graph, root = nil) ⇒ Array<Array<Object>>

Returns all basis cycles in graph

Parameters:

  • graph (Graph)

    a graph

  • root (Object, Nil) (defaults to: nil)

    root for the graph cycles

Returns:

  • (Array<Array<Object>>)

    Arrays of nodes in the cycles



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# File 'lib/networkx/auxillary_functions/cycles.rb', line 10

def self.cycle_basis(graph, root=nil)
  gnodes = graph.nodes.keys
  cycles = []
  until gnodes.empty?
    root = gnodes.shift if root.nil?
    stack = [root]
    pred = {root => root}
    used = {root => []}
    until stack.empty?
      z = stack.shift
      zused = used[z]
      graph.adj[z].each_key do |u|
        if !used.key?(u)
          pred[u] = z
          stack << u
          used[u] = [z]
        elsif u == z
          cycles << [z]
        elsif !zused.include?(u)
          pn = used[u]
          cycle = [u, z]
          p = pred[z]
          until pn.include?(p)
            cycle << p
            p = pred[p]
          end
          cycle << p
          cycles << cycle
          used[u] << z
          used[u] = used[u].uniq
        end
      end
    end
    gnodes -= pred.keys
    root = nil
  end
  cycles
end

.descendants(graph, source) ⇒ Array<Object>

Returns the descendants of a given node

Parameters:

Returns:

  • (Array<Object>)

    Array of the descendants

Raises:

  • (ArgumentError)


8
9
10
11
12
# File 'lib/networkx/auxillary_functions/dag.rb', line 8

def self.descendants(graph, source)
  raise ArgumentError, 'Source is not present in the graph!' unless graph.node?(source)
  des = single_source_shortest_path_length(graph, source).map { |u, _| u }.uniq
  des - [source]
end

.detect_unboundedness(r_network, source, target) ⇒ Object

Detects unboundedness in a graph, raises exception when infinite capacity flow is found

Parameters:

  • r_network (DiGraph)

    a residual graph

  • source (Object)

    source node

  • target (Object)

    target node



129
130
131
132
133
134
135
136
137
138
139
140
141
142
# File 'lib/networkx/flow/utils.rb', line 129

def self.detect_unboundedness(r_network, source, target)
  q = [source]
  seen = Set.new([source])
  inf = r_network.graph[:inf]
  until q.empty?
    u = q.shift
    r_network.adj[u].each do |v, uv_attrs|
      next unless uv_attrs[:capacity] == inf && !seen.include?(v)
      raise ArgumentError, 'Infinite capacity flow!' if v == target
      seen << v
      q << v
    end
  end
end

.dfs_edges(graph, source, depth_limit = nil) ⇒ Object

Returns edges of the graph travelled in depth first fashion

Examples:

NetworkX.dfs_edges(graph, source)

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    node to start dfs from

  • depth_limit (Integer, nil) (defaults to: nil)

    the depth limit of dfs

Raises:

  • (KeyError)


12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# File 'lib/networkx/traversals/dfs.rb', line 12

def self.dfs_edges(graph, source, depth_limit=nil)
  raise KeyError, "There exists no node names #{source} in the given graph." unless graph.node?(source)
  depth_limit = graph.nodes.length if depth_limit.nil?
  dfs_edges = []
  visited = [source]
  stack = [[-1, source, depth_limit, graph.neighbours(source)]]
  until stack.empty?
    earlier_node, parent, depth_now, children = stack.pop
    dfs_edges << [earlier_node, parent]
    children.each_key do |child|
      unless visited.include?(child)
        visited << child
        stack.push([parent, child, depth_now - 1, graph.neighbours(child)]) if depth_now > 1
      end
    end
  end
  dfs_edges.shift
  dfs_edges
end

.dfs_predecessors(graph, source, depth_limit = nil) ⇒ Object

Returns predecessor child pair of the graph travelled in depth first fashion

Examples:

NetworkX.dfs_predecessors(graph, source)

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    node to start dfs from

  • depth_limit (Integer, nil) (defaults to: nil)

    the depth limit of dfs



73
74
75
76
77
78
# File 'lib/networkx/traversals/dfs.rb', line 73

def self.dfs_predecessors(graph, source, depth_limit=nil)
  dfs_edges = dfs_edges(graph, source, depth_limit)
  predecessors = {}
  dfs_edges.each { |u, v| predecessors[v] = u }
  predecessors
end

.dfs_successors(graph, source, depth_limit = nil) ⇒ Object

Returns parent successor pair of the graph travelled in depth first fashion

Examples:

NetworkX.dfs_successors(graph, source)

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    node to start dfs from

  • depth_limit (Integer, nil) (defaults to: nil)

    the depth limit of dfs



55
56
57
58
59
60
61
62
63
# File 'lib/networkx/traversals/dfs.rb', line 55

def self.dfs_successors(graph, source, depth_limit=nil)
  dfs_edges = dfs_edges(graph, source, depth_limit)
  successors = {}
  dfs_edges.each do |u, v|
    successors[u] = [] if successors[u].nil?
    successors[u] << v
  end
  successors
end

.dfs_tree(graph, source, depth_limit = nil) ⇒ Object

Returns dfs tree of the graph

Examples:

NetworkX.dfs_tree(graph, source)

Parameters:

  • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

    a graph

  • source (Object)

    node to start dfs from

  • depth_limit (Integer, nil) (defaults to: nil)

    the depth limit of dfs



40
41
42
43
44
45
# File 'lib/networkx/traversals/dfs.rb', line 40

def self.dfs_tree(graph, source, depth_limit=nil)
  t = NetworkX::DiGraph.new
  t.add_node(source)
  t.add_edges_from(dfs_edges(graph, source, depth_limit))
  t
end

.diameter(graph) ⇒ Numeric

Returns the diameter of a graph

Parameters:

Returns:

  • (Numeric)

    diameter of the graph



24
25
26
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 24

def self.diameter(graph)
  eccentricity(graph).values.max
end

.difference(g_1, g_2) ⇒ Graph, ...

Performs the difference of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError)


99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
# File 'lib/networkx/operators/binary.rb', line 99

def self.difference(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

  raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?
  raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty?

  g_1.nodes.each { |u, attrs| result.add_node(u, attrs) }

  g_1.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if g_1.multigraph?
        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, attrs) unless g_2.edge?(u, v, k)
        end
      else
        result.add_edge(u, v, uv_attrs) unless g_2.edge?(u, v)
      end
    end
  end
  result
end

.dijkstra_path(graph, source, target) ⇒ Numeric

Computes shortest path to target from the given node

Parameters:

Returns:

  • (Numeric)

    path for target node from given node



158
159
160
161
# File 'lib/networkx/shortest_path/weighted.rb', line 158

def self.dijkstra_path(graph, source, target)
  _, path = singlesource_dijkstra(graph, source, target)
  path
end

.dijkstra_path_length(graph, source, target) ⇒ Numeric

Computes shortest path length to target from the given node

Parameters:

Returns:

  • (Numeric)

    path length for target node from given node

Raises:

  • (KeyError)


143
144
145
146
147
148
149
# File 'lib/networkx/shortest_path/weighted.rb', line 143

def self.dijkstra_path_length(graph, source, target)
  return 0 if source == target
  weight = get_weight(graph)
  length = help_dijkstra(graph, source, weight, nil, nil, nil, target)
  raise KeyError, 'Node not reachable!' unless length.key?(target)
  length[target]
end

.dijkstra_predecessor_distance(graph, source, cutoff = nil) ⇒ <Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>] predcessor hash and distance hash

Computes weighted shortest path length and predecessors

Parameters:

Returns:

  • (<Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>] predcessor hash and distance hash)

    Array }, Hash{ Object => Numeric }>] predcessor hash and distance hash

    
    
    171
    172
    173
    174
    175
    # File 'lib/networkx/shortest_path/weighted.rb', line 171
    
    def self.dijkstra_predecessor_distance(graph, source, cutoff=nil)
      weight = get_weight(graph)
      pred = {source => []}
      [pred, help_dijkstra(graph, source, weight, pred, nil, cutoff)]
    end

    .directed_edges_cross_edges(g_1, g_2) ⇒ Object

    Returns the product of directed edges with edges

    
    
    44
    45
    46
    47
    48
    49
    50
    51
    52
    # File 'lib/networkx/operators/product.rb', line 44
    
    def self.directed_edges_cross_edges(g_1, g_2)
      result = []
      edges_in_array(g_1).each do |u, v, c|
        edges_in_array(g_2) do |x, y, d|
          result << [[u, x], [v, y], hash_product(c, d)]
        end
      end
      result
    end

    .discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target) ⇒ Object

    Helper function for discharging a node

    
    
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    # File 'lib/networkx/flow/preflowpush.rb', line 133
    
    def self.discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target)
      height_val = residual_nodes[u_node][:height]
      curr_edge = residual_nodes[u_node][:curr_edge]
      next_height = height_val
      levels[height_val].active.delete(u_node)
    
      loop do
        v, attr = curr_edge.get
        if height_val == residual_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity]
          flow = [residual_nodes[u_node][:excess], attr[:capacity] - attr[:flow]].min
          push(u_node, v, flow, residual_nodes, residual_adj)
          activate(v, source, target, levels, residual_nodes)
          if residual_nodes[u_node][:excess].zero?
            levels[height_val].inactive.add(u_node)
            break
          end
        end
        begin
          curr_edge.move_to_next
        rescue StopIteration
          height_val = relabel(u_node, grt, residual_adj, residual_nodes, source, target, levels)
          if is_phase_1 && height_val >= n - 1
            levels[height].active.add(u_node)
            break
          end
          next_height = height_val
        end
      end
      residual_nodes[u_node][:height] = height_val
      next_height
    end

    .disjoint_union(g_1, g_2) ⇒ Graph, ...

    Performs the disjoint union of two graphs

    Parameters:

    Returns:

    
    
    236
    237
    238
    239
    240
    241
    242
    243
    # File 'lib/networkx/operators/binary.rb', line 236
    
    def self.disjoint_union(g_1, g_2)
      new_g_1 = convert_to_distinct_labels(g_1)
      new_g_2 = convert_to_distinct_labels(g_2)
      result = union(new_g_1, new_g_2)
      result.graph.merge!(g_1.graph)
      result.graph.merge!(g_2.graph)
      result
    end

    .disjoint_union_all(graphs) ⇒ Graph, ...

    Performs the disjoint union of many graphs

    Parameters:

    Returns:

    Raises:

    • (ArgumentError)
    
    
    22
    23
    24
    25
    26
    27
    28
    29
    30
    # File 'lib/networkx/operators/all.rb', line 22
    
    def self.disjoint_union_all(graphs)
      raise ArgumentError, 'Argument array is empty' if graphs.empty?
      result = graphs.shift
    
      graphs.each do |graph|
        result = NetworkX.disjoint_union(result, graph)
      end
      result
    end

    .dist_path_lambda(_graph, _new_weight) ⇒ Object

    Helper function to get distances

    
    
    373
    374
    375
    376
    377
    378
    379
    # File 'lib/networkx/shortest_path/weighted.rb', line 373
    
    def self.dist_path_lambda(_graph, _new_weight)
      lambda do |graph, v, new_weight|
        paths = {v => [v]}
        _ = help_dijkstra(graph, v, new_weight, nil, paths)
        paths
      end
    end

    .eccentricity(graph, node = nil) ⇒ Array<Numeric>, Numeric

    Returns the eccentricity of a particular node or all nodes

    Parameters:

    Returns:

    • (Array<Numeric>, Numeric)

      eccentricity/eccentricites of all nodes

    
    
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # File 'lib/networkx/auxillary_functions/eccentricity.rb', line 8
    
    def self.eccentricity(graph, node=nil)
      e = {}
      graph.nodes.each do |u, _|
        length = single_source_shortest_path_length(graph, u)
        l = length.length
        raise ArgumentError, 'Found infinite path length!' unless l == graph.nodes.length
        e[u] = length.max_by { |a| a[1] }[1]
      end
      node.nil? ? e : e[node]
    end

    .edge_dfs(graph, start, orientation = nil) ⇒ Object

    Performs edge dfs on the graph Orientation :ignore, directed edges can be travelled in both fashions Orientation reverse, directed edges can be travelled in reverse fashion Orientation :nil, the graph is not meddled with

    Examples:

    NetworkX.edge_dfs(graph, source, 'ignore')

    Parameters:

    • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

      a graph

    • source (Object)

      node to start dfs from

    • orientation (:ignore, :reverse', nil) (defaults to: nil)

      the orientation of edges of graph

    
    
    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
    86
    87
    88
    89
    # File 'lib/networkx/traversals/edge_dfs.rb', line 54
    
    def self.edge_dfs(graph, start, orientation=nil)
      case orientation
      when :reverse
        graph = graph.reverse if graph.class.name == 'NetworkX::DiGraph' || graph.class.name == 'NetworkX::MultiDiGraph'
      when :ignore
        graph = graph.to_undirected if graph.class.name == 'NetworkX::DiGraph'
        graph = graph.to_multigraph if graph.class.name == 'NetworkX::MultiDiGraph'
      end
    
      visited_edges = []
      visited_nodes = []
      stack = [start]
      current_edges = {}
    
      e = Enumerator.new do |yield_var|
        until stack.empty?
          current = stack.last
          unless visited_nodes.include?(current)
            current_edges[current] = out_edges(graph, current)
            visited_nodes << current
          end
    
          edge = current_edges[current].shift
          if edge.nil?
            stack.pop
          else
            unless visited_edges.include?(edge_id(graph, edge))
              visited_edges << edge_id(graph, edge)
              stack << edge[1]
              yield_var.yield edge
            end
          end
        end
      end
      e.take(graph.number_of_edges)
    end

    .edge_id(graph, edge) ⇒ Object

    Helper function of edge_dfs

    
    
    33
    34
    35
    36
    37
    # File 'lib/networkx/traversals/edge_dfs.rb', line 33
    
    def self.edge_id(graph, edge)
      return edge if graph.directed?
      return Set.new([edge, (edge[0..1].reverse + edge[2])]) if graph.multigraph?
      Set.new([edge, edge.reverse])
    end

    .edges_cross_nodes(g_1, g_2) ⇒ Object

    Returns the product of edges with edges

    
    
    66
    67
    68
    69
    70
    71
    72
    73
    74
    # File 'lib/networkx/operators/product.rb', line 66
    
    def self.edges_cross_nodes(g_1, g_2)
      result = []
      edges_in_array(g_1).each do |u, v, d|
        g_2.nodes.keys.each do |x|
          result << [[u, x], [v, x], d]
        end
      end
      result
    end

    .edges_cross_nodes_and_nodes(g_1, g_2) ⇒ Object

    Returns the product of edges with pairs of nodes

    
    
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    # File 'lib/networkx/operators/product.rb', line 88
    
    def self.edges_cross_nodes_and_nodes(g_1, g_2)
      result = []
      edges_in_array(g_1).each do |u, v, d|
        g_2.nodes.keys.each do |x|
          g_2.nodes.keys.each do |y|
            result << [[u, x], [v, y], d]
          end
        end
      end
      result
    end

    .edges_in_array(graph) ⇒ Object

    Returns the edges of the graph in an array

    
    
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # File 'lib/networkx/operators/product.rb', line 7
    
    def self.edges_in_array(graph)
      edge_array = []
      if graph.multigraph?
        graph.adj.each do |u, u_edges|
          u_edges.each do |v, uv_edges|
            uv_edges.each do |_k, attrs|
              edge_array << [u, v, attrs]
            end
          end
        end
      else
        graph.adj.each do |u, u_edges|
          u_edges.each do |v, attrs|
            edge_array << [u, v, attrs]
          end
        end
      end
      edge_array
    end

    .edmondskarp(graph, source, target, residual = nil, cutoff = nil) ⇒ DiGraph

    Computes max flow using edmonds karp algorithm

    Parameters:

    • graph (Graph, DiGraph)

      a graph

    • source (Object)

      source node

    • target (Object)

      target node

    • residual (DiGraph, nil) (defaults to: nil)

      residual graph

    • cutoff (Numeric) (defaults to: nil)

      cutoff for the algorithm

    Returns:

    • (DiGraph)

      a residual graph containing the flow values

    
    
    110
    111
    112
    # File 'lib/networkx/flow/edmondskarp.rb', line 110
    
    def self.edmondskarp(graph, source, target, residual=nil, cutoff=nil)
      edmondskarp_impl(graph, source, target, residual, cutoff)
    end

    .edmondskarp_core(residual, source, target, cutoff) ⇒ Object

    Core helper function for the EdmondsKarp algorithm

    
    
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    # File 'lib/networkx/flow/edmondskarp.rb', line 59
    
    def self.edmondskarp_core(residual, source, target, cutoff)
      inf = residual.graph[:inf]
      flow_val = 0
      while flow_val < cutoff
        v, pred, succ = bidirectional_bfs(residual, source, target)
        break if pred.nil?
        path = [v]
        u = v
        while u != source
          u = pred[u]
          path << u
        end
        path.reverse!
        u = v
        while u != target
          u = succ[u]
          path << u
        end
        flow_val += augment(residual, inf, path)
      end
      flow_val
    end

    .edmondskarp_impl(graph, source, target, residual, cutoff) ⇒ Object

    Helper function for the edmondskarp function

    Raises:

    • (ArgumentError)
    
    
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    # File 'lib/networkx/flow/edmondskarp.rb', line 85
    
    def self.edmondskarp_impl(graph, source, target, residual, cutoff)
      raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source)
      raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target)
      raise ArgumentError, 'Source and target are same node!' if source == target
      res_graph = residual.nil? ? build_residual_network(graph) : residual.clone
      res_graph.adj.each do |u, u_edges|
        u_edges.each do |v, _attrs|
          res_graph.adj[u][v][:flow] = 0
          res_graph.pred[v][u][:flow] = 0
        end
      end
      cutoff = Float::INFINITY if cutoff.nil?
      res_graph.graph[:flow_val] = edmondskarp_core(res_graph, source, target, cutoff)
      res_graph
    end

    .find_cliques(graph) ⇒ Array<Array<Object>>

    Returns all cliques in the graph

    Parameters:

    Returns:

    • (Array<Array<Object>>)

      Arrays of nodes in the cliques

    
    
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    # File 'lib/networkx/auxillary_functions/cliques.rb', line 9
    
    def self.find_cliques(graph)
      return nil if graph.nodes.empty?
      q = [nil]
      adj = {}
      graph.nodes.each_key { |u| adj[u] = [] }
      graph.adj.each { |u, u_edges| u_edges.each_key { |v| adj[u] << v if u != v } }
    
      subg = graph.nodes.keys
      cand = graph.nodes.keys
      u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length }
      ext_u = cand - adj[u]
      stack = []
      cliques = []
      begin
        loop do
          if !ext_u.empty?
            q_elem = ext_u.pop
            cand.delete(q_elem)
            q[-1] = q_elem
            adj_q = adj[q_elem]
            subg_q = subg & adj_q
            if subg_q.empty?
              cliques << q[0..(q.length - 1)]
            else
              cand_q = cand & adj_q
              unless cand_q.empty?
                stack << [subg, cand, ext_u]
                q << nil
                subg = subg_q
                cand = cand_q
                u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length }
                ext_u = cand - adj[u]
              end
            end
          else
            q.pop
            subg, cand, ext_u = stack.pop
          end
        end
      rescue NoMethodError
        return cliques
      end
    end

    .find_cycle(graph, node) ⇒ Array<Array<Object>>

    Returns the cycle containing the given node

    Parameters:

    • graph (Graph, DiGraph)

      a graph

    • node (Object)

      node to be included in the cycle

    Returns:

    • (Array<Array<Object>>)

      Arrays of nodes in the cycle

    Raises:

    • (ArgumentError)
    
    
    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
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    # File 'lib/networkx/auxillary_functions/cycles.rb', line 57
    
    def self.find_cycle(graph, node)
      explored = Set.new
      cycle = []
      final_node = nil
      unless explored.include?(node)
        edges = []
        seen = [node]
        active_nodes = [node]
        previous_head = nil
    
        edge_dfs(graph, node).each do |edge|
          tail, head = edge
          next if explored.include?(head)
          if !previous_head.nil? && tail != previous_head
            loop do
              popped_edge = edges.pop
              if popped_edge.nil?
                edges = []
                active_nodes = [tail]
                break
              else
                popped_head = popped_edge[1]
                active_nodes.delete!(popped_head)
              end
    
              unless edges.empty?
                last_head = edges[-1][1]
                break if tail == last_head
              end
            end
          end
          edges << edge
    
          if active_nodes.include?(head)
            cycle += edges
            final_node = head
            break
          else
            seen << head
            active_nodes << head
            previous_head = head
          end
        end
        cycle.each_with_index { |edge, i| return cycle[i..(cycle.length - 1)] if final_node == edge[0] }
      end
      raise ArgumentError, 'No cycle found!' if cycle.empty?
    end

    .floyd_warshall(graph) ⇒ Hash{ Object => { Object => { Numeric }}}

    Returns the all pair distance between all the nodes

    Parameters:

    Returns:

    • (Hash{ Object => { Object => { Numeric }}})

      a hash containing distances b/w all pairs of nodes

    
    
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    # File 'lib/networkx/shortest_path/dense.rb', line 10
    
    def self.floyd_warshall(graph)
      a, index = to_matrix(graph, Float::INFINITY, 'min')
      nodelen = graph.nodes.length
      (0..(nodelen - 1)).each { |i| a[i, i] = 0 }
      (0..(nodelen - 1)).each do |k|
        (0..(nodelen - 1)).each do |i|
          (0..(nodelen - 1)).each do |j|
            a[i, j] = [a[i, j], a[i, k] + a[k, j]].min
          end
        end
      end
    
      as_hash = {}
      (0..(nodelen - 1)).each do |i|
        (0..(nodelen - 1)).each do |j|
          as_hash[index[i]] = {} unless as_hash.key?(index[i])
          as_hash[index[i]][index[j]] = a[i, j]
        end
      end
      as_hash
    end

    .gap_heuristic(height, levels, residual_nodes) ⇒ Object

    Helper function for applying gap heuristic

    
    
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    # File 'lib/networkx/flow/preflowpush.rb', line 168
    
    def self.gap_heuristic(height, levels, residual_nodes)
      ((height + 1)..(max_height)).each do |idx|
        level = levels[idx]
        level.active.each { |u| residual_nodes[u][:height] = n + 1 }
        level.inactive.each { |u| residual_nodes[u][:height] = n + 1 }
        levels[n + 1].active.merge!(level.active)
        level.active.clear
        levels[n + 1].inactive.merge!(level.inactive)
        level.inactive.clear
      end
    end

    .generate_unique_nodeObject

    Returns a label for unique node

    
    
    5
    6
    7
    # File 'lib/networkx/flow/capacityscaling.rb', line 5
    
    def self.generate_unique_node
      SecureRandom.uuid
    end

    .get_edges(graph) ⇒ Object

    Returns the edges of the graph in an array

    
    
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # File 'lib/networkx/operators/binary.rb', line 5
    
    def self.get_edges(graph)
      edges = []
      graph.adj.each do |u, u_attrs|
        u_attrs.each do |v, uv_attrs|
          edges << [u, v, uv_attrs]
        end
      end
      edges
    end

    .get_edges_weights(graph) ⇒ Object

    Helper function for the minimum spanning tree

    
    
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # File 'lib/networkx/auxillary_functions/mst.rb', line 4
    
    def self.get_edges_weights(graph)
      edges = []
      graph.adj.each do |u, u_edges|
        u_edges.each do |v, uv_attrs|
          edges << [[u, v], uv_attrs[:weight] || Float::INFINITY]
        end
      end
      edges
    end

    .get_sources(graph) ⇒ Object

    Helper function to get sources

    
    
    368
    369
    370
    # File 'lib/networkx/shortest_path/weighted.rb', line 368
    
    def self.get_sources(graph)
      graph.nodes.collect { |k, _v| k }
    end

    .get_weight(graph) ⇒ Object

    Helper function to extract weight from a adjecency hash

    
    
    5
    6
    7
    8
    9
    10
    11
    # File 'lib/networkx/shortest_path/weighted.rb', line 5
    
    def self.get_weight(graph)
      weight_get = lambda do |_, _, attrs|
        return attrs[:weight] || 1 unless graph.multigraph?
        attrs.group_by { |_k, vals| vals[:weight] || 1 }.keys.max
      end
      weight_get
    end

    .global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred) ⇒ Object

    Helper function for global relabel heuristic

    
    
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    # File 'lib/networkx/flow/preflowpush.rb', line 183
    
    def self.global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred)
      src = from_sink ? target : source
      heights = reverse_bfs(src, residual_pred)
      heights.delete(target) unless from_sink
      max_height = heights.values.max
      if from_sink
        residual_nodes.each { |u, attr| heights[u] = num + 1 if !heights.key?(u) && attr[:height] < num }
      else
        heights.each_key { |u| heights[u] += num }
        max_height += num
      end
      heights.delete(src)
      heights.each do |u, new_height|
        old_height = residual_nodes[u][:height]
        next unless new_height != old_height
        if levels[old_height].active.include?(u)
          levels[old_height].active.delete(u)
          levels[new_height].active.add(u)
        else
          levels[old_height].inactive.delete(u)
          levels[new_height].inactive.add(u)
        end
        residual_nodes[u][:height] = new_height
      end
      max_height
    end

    .graph_to_csv(graph, filename = 'graph.csv') ⇒ Object

    Saves the graph in a csv file

    Parameters:

    
    
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    # File 'lib/networkx/converters/to_csv.rb', line 8
    
    def self.graph_to_csv(graph, filename='graph.csv')
      CSV.open(filename, 'wb') do |csv|
        csv << [graph.class.name]
        csv << ['graph_values']
        csv << graph.graph.keys
        csv << graph.graph.values
        csv << ['graph_nodes']
        graph.nodes.each do |u, attrs|
          node_attrs = [u]
          attrs.each do |k, v|
            node_attrs << k
            node_attrs << v
          end
          csv << node_attrs
        end
        csv << ['graph_edges']
        graph.adj.each do |u, u_edges|
          u_edges.each do |v, uv_attrs|
            if graph.multigraph?
              uv_attrs.each do |key, attrs|
                node_attrs = [u, v, key]
                attrs.each do |k, k_attrs|
                  node_attrs << k
                  node_attrs << k_attrs
                end
                csv << node_attrs
              end
            else
              node_attrs = [u, v]
              uv_attrs.each do |k, vals|
                node_attrs << k
                node_attrs << vals
              end
              csv << node_attrs
            end
          end
        end
      end
    end

    .graph_to_json(graph) ⇒ JSON

    Returns a JSON object of the given graph

    Parameters:

    Returns:

    • (JSON)

      json encoded graph

    
    
    7
    8
    9
    10
    11
    12
    13
    14
    # File 'lib/networkx/converters/to_json.rb', line 7
    
    def self.graph_to_json(graph)
      json_hash = {}
      json_hash[:class] = graph.class.name
      json_hash[:graph] = graph.graph
      json_hash[:nodes] = graph.nodes
      json_hash[:adj] = graph.adj
      json_hash.to_json
    end

    .hash_product(hash_1, hash_2) ⇒ Object

    Returns the hash product of two hashes

    
    
    28
    29
    30
    # File 'lib/networkx/operators/product.rb', line 28
    
    def self.hash_product(hash_1, hash_2)
      Hash[(hash_1.keys | hash_2.keys).map { |n| [n, [hash_1[n], hash_2[n]]] }]
    end

    .help_bellman_ford(graph, sources, weight, pred = nil, paths = nil, dist = nil, cutoff = nil, target = nil) ⇒ Object

    Helper function for bellman ford

    
    
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    # File 'lib/networkx/shortest_path/weighted.rb', line 217
    
    def self.help_bellman_ford(graph, sources, weight, pred=nil, paths=nil, dist=nil, cutoff=nil, target=nil)
      pred = sources.product([[]]).to_h if pred.nil?
      dist = sources.product([0]).to_h if dist.nil?
    
      inf, n, count, q, in_q = Float::INFINITY, graph.nodes.length, {}, sources.clone, Set.new(sources)
      until q.empty?
        u = q.shift
        in_q.delete(u)
        skip = false
        pred[u].each { |k| skip = true if in_q.include?(k) }
        next if skip
        dist_u = dist[u]
        graph.adj[u].each do |v, e|
          dist_v = dist_u + weight.call(u, v, e)
          next if !cutoff.nil? && dist_v > cutoff
          next if !target.nil? && dist_v > (dist[target] || inf)
          if dist_v < (dist[v] || inf)
            unless in_q.include?(v)
              q << v
              in_q.add(v)
              count_v = (count[v] || 0) + 1
              raise ArgumentError, 'Negative edge cycle detected!' if count_v == n
              count[v] = count_v
            end
            dist[v] = dist_v
            pred[v] = [u]
          elsif dist.key?(v) && dist_v == dist[v]
            pred[v] << u
          end
        end
      end
      unless paths.nil?
        dsts = target.nil? ? pred : [target]
        dsts.each_key do |dst|
          path, cur = [dst], dst
          until pred[cur][0].nil?
            cur = pred[cur][0]
            path << cur
          end
          path.reverse
          paths[dst] = path
        end
      end
      dist
    end

    .help_dijkstra(graph, source, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object

    Helper function for single source dijkstra

    
    
    53
    54
    55
    # File 'lib/networkx/shortest_path/weighted.rb', line 53
    
    def self.help_dijkstra(graph, source, weight, pred=nil, paths=nil, cutoff=nil, target=nil)
      help_multisource_dijkstra(graph, [source], weight, pred, paths, cutoff, target)
    end

    .help_multisource_dijkstra(graph, sources, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object

    Helper function for multisource dijkstra

    
    
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    # File 'lib/networkx/shortest_path/weighted.rb', line 16
    
    def self.help_multisource_dijkstra(graph, sources, weight, pred=nil, paths=nil, cutoff=nil, target=nil)
      count = ->(i) { i + 1 }
      i = -1
      dist = {}
      seen = {}
      fringe = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) }
      sources.each do |s|
        seen[s] = 0
        fringe << [0, count.call(i), s]
      end
    
      until fringe.empty?
        d, _, v = fringe.pop
        next if dist.key?(v)
        dist[v] = d
        break if v == target
        graph.adj[v].each do |u, attrs|
          cost = weight.call(v, u, attrs)
          next if cost.nil?
          vu_dist = dist[v] + cost
          next if !cutoff.nil? && vu_dist > cutoff
          if dist.key?(u)
            raise ValueError, 'Contradictory weights found!' if vu_dist < dist[u]
          elsif !seen.key?(u) || vu_dist < seen[u]
            seen[u] = vu_dist
            fringe << [vu_dist, count.call(i), u]
            paths[u] = paths[v] + [u] unless paths.nil?
            pred[u] = [v] unless pred.nil?
          elsif vu_dist == seen[u]
            pred[u] << v unless pred.nil?
          end
        end
      end
      dist
    end

    .help_single_shortest_path(adj, firstlevel, paths, cutoff) ⇒ Object

    Helper function for finding single source shortest path

    
    
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    # File 'lib/networkx/shortest_path/unweighted.rb', line 56
    
    def self.help_single_shortest_path(adj, firstlevel, paths, cutoff)
      level = 0
      nextlevel = firstlevel
      while !nextlevel.empty? && cutoff > level
        thislevel = nextlevel
        nextlevel = {}
        thislevel.each_key do |u|
          adj[u].each_key do |v|
            unless paths.key?(v)
              paths[v] = paths[u] + [v]
              nextlevel[v] = 1
            end
          end
        end
        level += 1
      end
      paths
    end

    .help_single_shortest_path_length(adj, firstlevel, cutoff) ⇒ Object

    Helper function for single source shortest path length

    
    
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # File 'lib/networkx/shortest_path/unweighted.rb', line 5
    
    def self.help_single_shortest_path_length(adj, firstlevel, cutoff)
      iterator = Enumerator.new do |e|
        seen = {}
        level = 0
        nextlevel = firstlevel
    
        while !nextlevel.empty? && cutoff >= level
          thislevel = nextlevel
          nextlevel = {}
          thislevel.each do |u, _attrs|
            next if seen.key?(u)
            seen[u] = level
            nextlevel.merge!(adj[u])
            e.yield [u, level]
          end
          level += 1
        end
        seen.clear
      end
      iterator
    end

    .hits(graph, max_iter = 100, tol = 1e-8, nstart) ⇒ Array<Numeric, Numeric>

    Computes hits and authority scores for all the graphs

    Parameters:

    • graph (Graph, DiGraph)

      a graph

    • max_iter (Integer) (defaults to: 100)

      max iterations to run the hits algorithm

    • tol (Numeric) (defaults to: 1e-8)

      tolerences to cut off the loop

    • nstart (Array<Numeric>)

      starting hub values for the nodes

    Returns:

    • (Array<Numeric, Numeric>)

      hits and authority scores

    
    
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    # File 'lib/networkx/link_analysis/hits.rb', line 12
    
    def self.hits(graph, max_iter=100, tol=1e-8, nstart)
      return [{}, {}] if graph.nodes.empty?
      h = nstart
      sum = h.values.inject(:+)
      h.each_key { |k| h[k] /= (sum * 1.0) }
      i = 0
      a = {}
    
      loop do
        hlast = Marshal.load(Marshal.dump(h))
        h, a = {}, {}
        hlast.each do |k, _v|
          h[k] = 0
          a[k] = 0
        end
        h.each_key { |k| graph.adj[k].each { |nbr, attrs| a[k] += hlast[nbr] * (attrs[:weight] || 1) } }
        h.each_key { |k| graph.adj[k].each { |nbr, attrs| h[k] += a[nbr] * (attrs[:weight] || 1) } }
        smax = h.values.max
        h.each_key { |k| h[k] /= smax }
        smax = a.values.max
        a.each_key { |k| a[k] /= smax }
        break if h.keys.map { |k| (h[k] - hlast[k]).abs }.inject(:+) < tol
        raise ArgumentError, 'Power Iteration failed to converge!' if i > max_iter
        i += 1
      end
      [h, a]
    end

    .hub_matrix(graph) ⇒ NMatrix

    Computes hub matrix for the graph

    Parameters:

    Returns:

    • (NMatrix)

      hub matrix for the graph

    
    
    55
    56
    57
    58
    # File 'lib/networkx/link_analysis/hits.rb', line 55
    
    def self.hub_matrix(graph)
      matrix, = to_matrix(graph, 0)
      matrix.dot matrix.transpose
    end

    .init_product_graph(g_1, g_2) ⇒ Object

    Initializes the product graph

    Raises:

    • (ArgumentError)
    
    
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    # File 'lib/networkx/operators/product.rb', line 101
    
    def self.init_product_graph(g_1, g_2)
      raise ArgumentError, 'Arguments must be both directed or undirected!' unless g_1.directed? == g_2.directed?
    
      g = if g_1.multigraph? || g_2.multigraph?
            NetworkX::MultiGraph.new
          else
            NetworkX::Graph.new
          end
      g = g.to_directed if g.directed?
      g
    end

    .intersection(g_1, g_2) ⇒ Graph, ...

    Performs the intersection of two graphs

    Parameters:

    Returns:

    Raises:

    • (ArgumentError)
    
    
    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
    86
    87
    88
    89
    # File 'lib/networkx/operators/binary.rb', line 54
    
    def self.intersection(g_1, g_2)
      result = Marshal.load(Marshal.dump(g_1))
      result.clear
    
      raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?
      raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty?
    
      g_1.nodes.each { |u, attrs| result.add_node(u, attrs) }
    
      if g_1.number_of_edges <= g_2.number_of_edges
        g_1.adj.each do |u, u_edges|
          u_edges.each do |v, uv_attrs|
            if g_1.multigraph?
              uv_attrs.each do |k, attrs|
                result.add_edge(u, v, attrs) if g_2.edge?(u, v, k)
              end
            elsif g_2.edge?(u, v)
              result.add_edge(u, v, uv_attrs)
            end
          end
        end
      else
        g_2.adj.each do |u, u_edges|
          u_edges.each do |v, uv_attrs|
            if g_2.multigraph?
              uv_attrs.each do |k, attrs|
                result.add_edge(u, v, attrs) if g_1.edge?(u, v, k)
              end
            elsif g_1.edge?(u, v)
              result.add_edge(u, v, uv_attrs)
            end
          end
        end
      end
      result
    end

    .intersection_all(graphs) ⇒ Graph, ...

    Performs the intersection of many graphs

    Parameters:

    Returns:

    Raises:

    • (ArgumentError)
    
    
    37
    38
    39
    40
    41
    42
    43
    44
    45
    # File 'lib/networkx/operators/all.rb', line 37
    
    def self.intersection_all(graphs)
      raise ArgumentError, 'Argument array is empty' if graphs.empty?
      result = graphs.shift
    
      graphs.each do |graph|
        result = NetworkX.intersection(result, graph)
      end
      result
    end

    .johnson(graph) ⇒ Array<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes

    Returns shortest path between all pairs of nodes

    Parameters:

    Returns:

    • (Array<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes)

      Array Array }] shortest paths between all pairs of nodes

      
      
      395
      396
      397
      398
      399
      400
      401
      402
      403
      404
      405
      406
      407
      # File 'lib/networkx/shortest_path/weighted.rb', line 395
      
      def self.johnson(graph)
        dist, pred = {}, {}
        sources = get_sources(graph)
        graph.nodes.each_key do |n|
          dist[n], pred[n] = 0, []
        end
        weight = get_weight(graph)
        dist_bellman = help_bellman_ford(graph, sources, weight, pred, nil, dist=dist)
        new_weight = ->(u, v, d) { weight.call(u, v, d) + dist_bellman[u] - dist_bellman[v] }
        dist_path = dist_path_lambda(graph, new_weight)
        path_lengths = set_path_lengths_johnson(graph, dist_path, new_weight)
        path_lengths
      end

      .json_to_graph(json_str) ⇒ Graph, ...

      Returns a graph from the json encoded graph

      Parameters:

      • json_str (JSON)

        json encoded string

      Returns:

      
      
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      # File 'lib/networkx/converters/to_json.rb', line 23
      
      def self.json_to_graph(json_str)
        graph_hash = JSON.parse(json_str)
        case json_str['class']
        when 'NetworkX::Graph'
          graph = NetworkX::Graph.new(graph_hash.graph)
        when 'NetworkX::MultiGraph'
          graph = NetworkX::MultiGraph.new(graph_hash.graph)
        when 'NetworkX::DiGraph'
          graph = NetworkX::DiGraph.new(graph_hash.graph)
        when 'NetworkX::MultiDiGraph'
          graph = NetworkX::MultiDiGraph.new(graph_hash.graph)
        end
        graph.adj = graph_hash['adj']
        graph.nodes = graph_hash['nodes']
        graph
      end

      .lexicographic_product(g_1, g_2) ⇒ Graph, ...

      Returns the lexicographic product of two graphs

      Parameters:

      Returns:

      
      
      147
      148
      149
      150
      151
      152
      153
      # File 'lib/networkx/operators/product.rb', line 147
      
      def self.lexicographic_product(g_1, g_2)
        g = init_product_graph(g_1, g_2)
        g.add_nodes(node_product(g_1, g_2))
        g.add_edges(edges_cross_nodes_and_nodes(g_1, g_2))
        g.add_edges(nodes_cross_edges(g_1, g_2))
        g
      end

      .maximal_independent_set(graph, nodes) ⇒ Numeric

      Returns the maximal independent set of a graph

      Parameters:

      Returns:

      • (Numeric)

        radius of the graph

      
      
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      # File 'lib/networkx/auxillary_functions/mis.rb', line 10
      
      def self.maximal_independent_set(graph, nodes)
        raise 'The array containing the nodes should be a subset of the graph!' if (graph.nodes.keys - nodes).empty?
        neighbours = []
        nodes.each { |u| graph.adj[u].each { |v, _| neighbours |= [v] } }
        raise 'Nodes is not an independent set of graph!' if (neighbours - nodes).empty?
        available_nodes = graph.nodes.keys - (neighbours | nodes)
        until available_nodes.empty?
          node = available_nodes.sample
          nodes << node
          available_nodes -= (graph.adj[node].keys + [node])
        end
        nodes
      end

      .minimum_spanning_tree(graph) ⇒ DiGraph, Graph

      Returns the minimum spanning tree of a graph

      Parameters:

      Returns:

      
      
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      # File 'lib/networkx/auxillary_functions/mst.rb', line 21
      
      def self.minimum_spanning_tree(graph)
        mst = Marshal.load(Marshal.dump(graph))
        mst.clear
        edges = get_edges_weights(graph).sort_by { |a| a[1] }
        union_find = UnionFind.new(graph.nodes.keys)
        while edges.any? && mst.nodes.length <= graph.nodes.length
          edge = edges.shift
          unless union_find.connected?(edge[0][0], edge[0][1])
            union_find.union(edge[0][0], edge[0][1])
            mst.add_edge(edge[0][0], edge[0][1], graph.adj[edge[0][0]][edge[0][1]])
          end
        end
        mst
      end

      .multisource_dijkstra(graph, sources, target = nil, cutoff = nil) ⇒ Numeric, Array<Object>

      Computes shortest paths and path lengths to a target from one of the nodes

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • sources (Array<Object>)

        Array of sources

      • target (Object, nil) (defaults to: nil)

        target node for the dijkstra algorithm

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the dijkstra algorithm

      Returns:

      • (Numeric, Array<Object>)

        path lengths for all nodes

      Raises:

      • (ValueError)
      
      
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      # File 'lib/networkx/shortest_path/weighted.rb', line 65
      
      def self.multisource_dijkstra(graph, sources, target=nil, cutoff=nil)
        raise ValueError, 'Sources cannot be empty' if sources.empty?
        return [0, [target]] if sources.include?(target)
        paths = {}
        weight = get_weight(graph)
        sources.each { |source| paths[source] = [source] }
        dist = help_multisource_dijkstra(graph, sources, weight, nil, paths, cutoff, target)
        return [dist, paths] if target.nil?
        raise KeyError, "No path to #{target}!" unless dist.key?(target)
        [dist[target], paths[target]]
      end

      .multisource_dijkstra_path(graph, sources, cutoff = nil) ⇒ Hash{ Object => Array<Object> }

      Computes shortest paths to any from the given nodes

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • sources (Array<Object>)

        Array of sources

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the dijkstra algorithm

      Returns:

      • (Hash{ Object => Array<Object> })

        paths for any nodes from given nodes

      
      
      97
      98
      99
      100
      # File 'lib/networkx/shortest_path/weighted.rb', line 97
      
      def self.multisource_dijkstra_path(graph, sources, cutoff=nil)
        _, path = multisource_dijkstra(graph, sources, nil, cutoff)
        path
      end

      .multisource_dijkstra_path_length(graph, sources, cutoff = nil) ⇒ Hash{ Object => Numeric }

      Computes shortest path lengths to any from the given nodes

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • sources (Array<Object>)

        Array of sources

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the dijkstra algorithm

      Returns:

      • (Hash{ Object => Numeric })

        path lengths for any nodes from given nodes

      Raises:

      • (ValueError)
      
      
      84
      85
      86
      87
      88
      # File 'lib/networkx/shortest_path/weighted.rb', line 84
      
      def self.multisource_dijkstra_path_length(graph, sources, cutoff=nil)
        raise ValueError, 'Sources cannot be empty' if sources.empty?
        weight = get_weight(graph)
        help_multisource_dijkstra(graph, sources, weight, nil, nil, cutoff)
      end

      .negative_edge_cycle(graph) ⇒ Boolean

      Finds if there is a negative edge cycle in the graph

      Parameters:

      Returns:

      • (Boolean)

        whether there exists a negative cycle in graph

      
      
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      # File 'lib/networkx/flow/capacityscaling.rb', line 14
      
      def self.negative_edge_cycle(graph)
        newnode = generate_unique_node
        graph.add_edges(graph.nodes.keys.map { |n| [newnode, n] })
        begin
          bellmanford_predecesor_distance(graph, newnode)
        rescue ArgumentError
          return true
        ensure
          graph.remove_node(newnode)
        end
        false
      end

      .node_product(g_1, g_2) ⇒ Object

      Returns the node product of nodes of two graphs

      
      
      33
      34
      35
      36
      37
      38
      39
      40
      41
      # File 'lib/networkx/operators/product.rb', line 33
      
      def self.node_product(g_1, g_2)
        n_product = []
        g_1.nodes.each do |k_1, attrs_1|
          g_2.nodes.each do |k_2, attrs_2|
            n_product << [[k_1, k_2], hash_product(attrs_1, attrs_2)]
          end
        end
        n_product
      end

      .nodes_cross_edges(g_1, g_2) ⇒ Object

      Returns the product of directed nodes with edges

      
      
      77
      78
      79
      80
      81
      82
      83
      84
      85
      # File 'lib/networkx/operators/product.rb', line 77
      
      def self.nodes_cross_edges(g_1, g_2)
        result = []
        g_1.nodes.keys.each do |x|
          edges_in_array(g_2).each do |u, v, d|
            result << [[x, u], [x, v], d]
          end
        end
        result
      end

      .number_of_cliques(graph, node) ⇒ Numeric

      Returns the number of cliques in a graph containing a node

      Parameters:

      Returns:

      • (Numeric)

        Number of cliques containing the given node

      
      
      59
      60
      61
      62
      63
      64
      # File 'lib/networkx/auxillary_functions/cliques.rb', line 59
      
      def self.number_of_cliques(graph, node)
        cliques = find_cliques(graph)
        num_cliq_arr = []
        cliques.each { |c| num_cliq_arr << 1 if c.include?(node) }
        num_cliq_arr.length
      end

      .out_edges(graph, node) ⇒ Object

      Helper function for edge_dfs

      Parameters:

      
      
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      # File 'lib/networkx/traversals/edge_dfs.rb', line 8
      
      def self.out_edges(graph, node)
        edges = []
        visited = {}
        case graph.class.name
        when 'NetworkX::Graph', 'NetworkX::DiGraph'
          graph.adj[node].each do |v, _|
            if graph.class.name == 'NetworkX::DiGraph' || visited[[v, node]].nil?
              visited[[node, v]] = true
              edges << [node, v]
            end
          end
        else
          graph.adj[node].each do |v, uv_keys|
            uv_keys.each_key do |k|
              if graph.class.name == 'NetworkX::MultiDiGraph' || visited[[v, node, k]].nil?
                visited[[node, v, k]] = true
                edges << [node, v, k]
              end
            end
          end
        end
        edges
      end

      .pagerank(graph, init, alpha = 0.85, eps = 1e-4, max_iter = 100) ⇒ Array<Numeric>

      Computes pagerank values for the graph

      Parameters:

      • graph (Graph)

        a graph

      • init (Array<Numeric>)

        initial pagerank values for the nodes

      • alpha (Numeric) (defaults to: 0.85)

        the alpha value to compute the pagerank

      • eps (Numeric) (defaults to: 1e-4)

        tolerence to check for convergence

      • max_iter (Integer) (defaults to: 100)

        max iterations for the pagerank algorithm to run

      Returns:

      • (Array<Numeric>)

        pagerank values of the graph

      Raises:

      • (ArgumentError)
      
      
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      # File 'lib/networkx/link_analysis/pagerank.rb', line 13
      
      def self.pagerank(graph, init, alpha=0.85, eps=1e-4, max_iter=100)
        dim = graph.nodes.length
        raise ArgumentError, 'Init array needs to have same length as number of graph nodes!'\
                              unless dim == init.length
        matrix = []
        elem_ind = {}
        p = []
        curr = init.values
        init.keys.each_with_index { |n, i| elem_ind[n] = i }
        graph.adj.each do |_u, u_edges|
          adj_arr = Array.new(dim, 0)
          u_edges.each do |v, _|
            adj_arr[elem_ind[v]] = 1
          end
          matrix << adj_arr
        end
        (0..(dim - 1)).each do |i|
          p[i] = []
          (0..(dim - 1)).each { |j| p[i][j] = matrix[i][j] / (matrix[i].inject(:+) * 1.0) }
        end
      
        max_iter.times do |_|
          prev = curr.clone
          dim.times do |i|
            ip = 0
            dim.times { |j| ip += p.transpose[i][j] * prev[j] }
            curr[i] = (alpha * ip) + (1 - alpha) / (dim * 1.0)
          end
          err = 0
          dim.times { |i| err += (prev[i] - curr[i]).abs }
          return curr if err < eps
        end
        raise ArgumentError, 'PageRank failed to converge!'
      end

      .power(graph, pow) ⇒ Graph, ...

      Returns the specified power of the graph

      Parameters:

      Returns:

      Raises:

      • (ArgumentError)
      
      
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      # File 'lib/networkx/operators/product.rb', line 179
      
      def self.power(graph, pow)
        raise ArgumentError, 'Power must be a positive quantity!' if pow <= 0
        result = NetworkX::Graph.new
        result.add_nodes(graph.nodes.map { |n, attrs| [n, attrs] })
        graph.nodes.each do |n, _attrs|
          seen = {}
          level = 1
          next_level = graph.adj[n]
          until next_level.empty?
            this_level = next_level
            next_level = {}
            this_level.each do |v, _attrs|
              next if v == n
              unless seen.key?(v)
                seen[v] = level
                next_level.merge!(graph.adj[v])
              end
            end
            break if pow <= level
            level += 1
          end
          result.add_edges(seen.map { |v, _| [n, v] })
        end
        result
      end

      .predecessor(graph, source, cutoff = nil, return_seen = false) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>, Hash{ Object => Array<Object> }

      Computes shortest paths to all nodes from all nodes

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • source (Object)

        source for which predecessors are needed

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for finding predecessor

      • return_seen (Boolean) (defaults to: false)

        if true, returns seen dict

      Returns:

      • (Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>, Hash{ Object => Array<Object> })

        predecessors of a given node and/or seen dict

      Raises:

      • (ArgumentError)
      
      
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      # File 'lib/networkx/shortest_path/unweighted.rb', line 114
      
      def self.predecessor(graph, source, cutoff=nil, return_seen=false)
        raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source)
        level = 0
        nextlevel = [source]
        seen = {source => level}
        pred = {source => []}
        until nextlevel.empty?
          level += 1
          thislevel = nextlevel
          nextlevel = []
          thislevel.each do |u|
            graph.adj[u].each_key do |v|
              if !seen.key?(v)
                pred[v] = [u]
                seen[v] = level
                nextlevel << v
              elsif seen[v] == level
                pred[v] << u
              end
            end
          end
          break if cutoff.nil? && cutoff <= level
        end
        return_seen ? [pred, seen] : pred
      end

      .preflowpush(graph, source, target, residual = nil, globalrelabel_freq = 1, value_only = false) ⇒ DiGraph

      Computes max flow using preflow push algorithm

      Parameters:

      • graph (DiGraph)

        a graph

      • source (Object)

        source node

      • target (Object)

        target node

      • residual (DiGraph, nil) (defaults to: nil)

        residual graph

      • globalrelabel_freq (Numeric) (defaults to: 1)

        global relabel freq

      • value_only (Boolean) (defaults to: false)

        if false, compute maximum flow else maximum preflow

      Returns:

      • (DiGraph)

        a residual graph containing the flow values

      
      
      249
      250
      251
      # File 'lib/networkx/flow/preflowpush.rb', line 249
      
      def self.preflowpush(graph, source, target, residual=nil, globalrelabel_freq=1, value_only=false)
        preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only)
      end

      .preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only) ⇒ Object

      Helper function to apply the preflow push algorithm

      Raises:

      • (ArgumentError)
      
      
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      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
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      # File 'lib/networkx/flow/preflowpush.rb', line 12
      
      def self.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only)
        raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source)
        raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target)
        raise ArgumentError, 'Source and Target are same!' if source == target
      
        globalrelabel_freq = 0 if globalrelabel_freq.nil?
        raise ArgumentError, 'Global Relabel Freq must be nonnegative!' if globalrelabel_freq < 0
        r_network = residual.nil? ? build_residual_network(graph) : residual
        detect_unboundedness(r_network, source, target)
      
        residual_nodes = r_network.nodes
        residual_adj = r_network.adj
        residual_pred = r_network.pred
      
        residual_nodes.each do |u, u_attrs|
          u_attrs[:excess] = 0
          residual_adj[u].each { |_v, attrs| attrs[:flow] = 0 }
        end
      
        heights = reverse_bfs(target, residual_pred)
      
        unless heights.key?(source)
          r_network.graph[:flow_value] = 0
          return r_network
        end
      
        n = r_network.nodes.length
        max_height = heights.map { |u, h| u == source ? -1 : h }.max
        heights[source] = n
      
        grt = GlobalRelabelThreshold.new(n, r_network.size, globalrelabel_freq)
      
        residual_nodes.each do |u, u_attrs|
          u_attrs[:height] = heights.key?(u) ? heights[u] : (n + 1)
          u_attrs[:curr_edge] = CurrentEdge.new(residual_adj[u])
        end
      
        residual_adj[source].each do |u, attr|
          flow = attr[:capacity]
          push(source, u, flow, residual_nodes, residual_adj) if flow > 0
        end
      
        levels = (0..(2 * n - 1)).map { |_| Level.new }
        residual_nodes.each do |u, attr|
          if u != source && u != target
            level = levels[attr[:height]]
            residual_nodes[u][:excess] > 0 ? level.active.add(u) : level.inactive.add(u)
          end
        end
      
        height = max_height
        while height > 0
          loop do
            level = levels[height]
            if level.active.empty?
              height -= 1
              break
            end
            old_height = height
            old_level = level
            u = arbitrary_element(level.active)
            height = discharge(u, true, residual_nodes, residual_adj, height, levels, grt, source, target)
            if grt.reached?
              height = global_relabel(true, source, target, residual_nodes, n, levels, residual_pred)
              max_height = height
              grt.clear_work
            elsif old_level.active.empty? && old_level.inactive.empty?
              gap_heuristic(old_height, levels, residual_nodes)
              height = old_height - 1
              max_height = height
            else
              max_height = [max_height, height].max
            end
          end
        end
      
        if value_only
          r_network.graph[:flow_value] = residual_nodes[target][:excess]
          return r_network
        end
      
        height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred)
        grt.clear_work
      
        while height > n
          loop do
            level = levels[height]
            if level.active.empty?
              height -= 1
              break
            end
            u = arbitrary_element(level.active)
            height = discharge(u, false, residual_nodes, residual_adj, height, levels, grt, source, target)
            if grt.reached?
              height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred)
              grt.clear_work
            end
          end
        end
        r_network.graph[:flow_value] = residual_nodes[target][:excess]
        r_network
      end

      .push(node_1, node_2, flow, residual_nodes, residual_adj) ⇒ Object

      Helper function for augmenting flow

      
      
      211
      212
      213
      214
      215
      216
      # File 'lib/networkx/flow/preflowpush.rb', line 211
      
      def self.push(node_1, node_2, flow, residual_nodes, residual_adj)
        residual_adj[node_1][node_2][:flow] += flow
        residual_adj[node_2][node_1][:flow] -= flow
        residual_nodes[node_1][:excess] -= flow
        residual_nodes[node_2][:excess] += flow
      end

      .radius(graph) ⇒ Numeric

      Returns the radius of a graph

      Parameters:

      Returns:

      • (Numeric)

        radius of the graph

      
      
      33
      34
      35
      # File 'lib/networkx/auxillary_functions/eccentricity.rb', line 33
      
      def self.radius(graph)
        eccentricity(graph).values.min
      end

      .relabel(node, num, r_adj, r_nodes) ⇒ Object

      Helper function to relable a node to create a permissible edge

      
      
      125
      126
      127
      128
      # File 'lib/networkx/flow/preflowpush.rb', line 125
      
      def self.relabel(u_node, grt, r_adj, _r_nodes, _source, _target, _levels)
        grt.add_work(r_adj[u_node].length)
        r_adj[u_node].map { |v, attr| attr[:flow] < (attr[:capacity] + 1) ? _nodes[v][:height] : Float::INFINITY }.min
      end

      .reverse_bfs(src, residual_pred) ⇒ Object

      Helper function for reverse bfs

      
      
      221
      222
      223
      224
      225
      226
      227
      228
      229
      230
      231
      232
      233
      234
      235
      236
      # File 'lib/networkx/flow/preflowpush.rb', line 221
      
      def self.reverse_bfs(src, residual_pred)
        heights = {src => 0}
        q = [[src, 0]]
      
        until q.empty?
          u, height = q.shift
          height += 1
          residual_pred[u].each do |v, attr|
            if !heights.key?(v) && attr[:flow] < attr[:capacity]
              heights[v] = height
              q << [v, height]
            end
          end
        end
        heights
      end

      .set_path_lengths_johnson(graph, dist_path, new_weight) ⇒ Object

      Helper function to set path lengths for Johnson algorithm

      
      
      382
      383
      384
      385
      386
      # File 'lib/networkx/shortest_path/weighted.rb', line 382
      
      def self.set_path_lengths_johnson(graph, dist_path, new_weight)
        path_lengths = []
        graph.nodes.each_key { |n| path_lengths << [n, dist_path.call(graph, n, new_weight)] }
        path_lengths
      end

      .shortest_augmenting_path(graph, source, target, residual = nil, _value_only = false, two_phase = false, cutoff = nil) ⇒ DiGraph

      Computes max flow using shortest augmenting path algorithm

      Parameters:

      • graph (DiGraph)

        a graph

      • source (Object)

        source node

      • target (Object)

        target node

      • residual (DiGraph, nil) (defaults to: nil)

        residual graph

      • value_only (Boolean)

        if true, compute only the maximum flow value

      • two_phase (Boolean) (defaults to: false)

        if true, two phase variant is used

      • cutoff (Numeric) (defaults to: nil)

        cutoff value for the algorithm

      Returns:

      • (DiGraph)

        a residual graph containing the flow values

      
      
      154
      155
      156
      # File 'lib/networkx/flow/shortestaugmentingpath.rb', line 154
      
      def self.shortest_augmenting_path(graph, source, target, residual=nil, _value_only=false, two_phase=false, cutoff=nil)
        shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff)
      end

      .shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff) ⇒ Object

      Helper function for running the shortest augmenting path algorithm

      Raises:

      • (ArgumentError)
      
      
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      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
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      # File 'lib/networkx/flow/shortestaugmentingpath.rb', line 7
      
      def self.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff)
        raise ArgumentError, 'Source is not in the graph!' unless graph.nodes.key?(source)
        raise ArgumentError, 'Target is not in the graph!' unless graph.nodes.key?(target)
        raise ArgumentError, 'Source and Target are the same!' if source == target
      
        residual = residual.nil? ? build_residual_network(graph) : residual
        r_nodes = residual.nodes
        r_pred = residual.pred
        r_adj = residual.adj
      
        r_adj.each_value do |u_edges|
          u_edges.each_value do |attrs|
            attrs[:flow] = 0
          end
        end
      
        heights = {target => 0}
        q = [[target, 0]]
      
        until q.empty?
          u, height = q.shift
          height += 1
          r_pred[u].each do |v, attrs|
            if !heights.key?(v) && attrs[:flow] < attrs[:capacity]
              heights[v] = height
              q << [v, height]
            end
          end
        end
      
        unless heights.key?(source)
          residual.graph[:flow_value] = 0
          return residual
        end
      
        n = graph.nodes.length
        m = residual.size / 2
      
        r_nodes.each do |node, attrs|
          attrs[:height] = heights.key?(node) ? heights[node] : n
          attrs[:curr_edge] = CurrentEdge.new(r_adj[node])
        end
      
        counts = Array.new(2 * n - 1, 0)
        counts.fill(0)
        r_nodes.each_value { |attrs| counts[attrs[:height]] += 1 }
        inf = graph.graph[:inf]
      
        cutoff = Float::INFINITY if cutoff.nil?
        flow_value = 0
        path = [source]
        u = source
        d = two_phase ? n : [m ** 0.5, 2 * n ** (2. / 3)].min.floor
        done = r_nodes[source][:height] >= d
      
        until done
          height = r_nodes[u][:height]
          curr_edge = r_nodes[u][:curr_edge]
      
          loop do
            v, attr = curr_edge.get
            if height == r_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity]
              path << v
              u = v
              break
            end
            begin
              curr_edge.move_to_next
            rescue StopIteration
              if counts[height].zero?
                residual.graph[:flow_value] = flow_value
                return residual
              end
              height = relabel(u, n, r_adj, r_nodes)
              if u == source && height >= d
                if !two_phase
                  residual.graph[:flow_value] = flow_value
                  return residual
                else
                  done = true
                  break
                end
              end
              counts[height] += 1
              r_nodes[u][:height] = height
              unless u == source
                path.pop
                u = path[-1]
                break
              end
            end
          end
          next unless u == target
          flow_value += augment(path, inf, r_adj)
          if flow_value >= cutoff
            residual.graph[:flow_value] = flow_value
            return residual
          end
        end
        flow_value += edmondskarp_core(residual, source, target, cutoff - flow_value)
        residual.graph[:flow_value] = flow_value
        residual
      end

      .single_source_shortest_path(graph, source, cutoff = nil) ⇒ Array<Object, Array<Object, Array<Object>>>

      Computes single source shortest path from a node to every other node

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • source (Object)

        source from which shortest paths are needed

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the shortest path algorithm

      Returns:

      • (Array<Object, Array<Object, Array<Object>>>)

        path lengths for all nodes from all nodes

      Raises:

      • (ArgumentError)
      
      
      82
      83
      84
      85
      86
      87
      88
      # File 'lib/networkx/shortest_path/unweighted.rb', line 82
      
      def self.single_source_shortest_path(graph, source, cutoff=nil)
        raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source)
        cutoff = Float::INFINITY if cutoff.nil?
        nextlevel = {source => 1}
        paths = {source => [source]}
        help_single_shortest_path(graph.adj, nextlevel, paths, cutoff)
      end

      .single_source_shortest_path_length(graph, source, cutoff = nil) ⇒ Array<Object, Numeric>

      Computes shortest path values to all nodes from a given node

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • source (Object)

        source to compute path length from

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the shortest path algorithm

      Returns:

      • (Array<Object, Numeric>)

        path lengths for all nodes

      Raises:

      • (ArgumentError)
      
      
      34
      35
      36
      37
      38
      39
      # File 'lib/networkx/shortest_path/unweighted.rb', line 34
      
      def self.single_source_shortest_path_length(graph, source, cutoff=nil)
        raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source)
        cutoff = Float::INFINITY if cutoff.nil?
        nextlevel = {source => 1}
        help_single_shortest_path_length(graph.adj, nextlevel, cutoff).take(graph.nodes.length)
      end

      .singlesource_bellmanford(graph, source, target = nil, cutoff = nil) ⇒ Object

      Raises:

      • (ArgumentError)
      
      
      282
      283
      284
      285
      286
      287
      288
      289
      290
      # File 'lib/networkx/shortest_path/weighted.rb', line 282
      
      def self.singlesource_bellmanford(graph, source, target=nil, cutoff=nil)
        return [0, [source]] if source == target
        weight = get_weight(graph)
        paths = {source => [source]}
        dist = help_bellman_ford(graph, [source], weight, nil, paths, nil, cutoff, target)
        return [dist, paths] if target.nil?
        raise ArgumentError, 'Node not reachable!' unless dist.key?(target)
        [dist[target], paths[target]]
      end

      .singlesource_bellmanford_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }

      Shortest path from source to all nodes using Bellman Ford algorithm

      Parameters:

      Returns:

      • (Hash{ Object => Array<Object> })

        path from source to all nodes

      
      
      326
      327
      328
      329
      # File 'lib/networkx/shortest_path/weighted.rb', line 326
      
      def self.singlesource_bellmanford_path(graph, source, cutoff=nil)
        _, path = singlesource_bellmanford(graph, source, cutoff)
        path
      end

      .singlesource_bellmanford_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }

      Shortest path length from source to all nodes using Bellman Ford algorithm

      Parameters:

      Returns:

      • (Hash{ Object => Numeric })

        path lengths from source to all nodes

      
      
      338
      339
      340
      341
      # File 'lib/networkx/shortest_path/weighted.rb', line 338
      
      def self.singlesource_bellmanford_path_length(graph, source, cutoff=nil)
        weight = get_weight(graph)
        help_bellman_ford(graph, [source], weight, nil, nil, nil, cutoff)
      end

      .singlesource_dijkstra(graph, source, target = nil, cutoff = nil) ⇒ Hash{ Object => Array<Object> }, Array<Object>

      Computes shortest paths and path distances to all nodes/target from the given node

      Parameters:

      • graph (Graph, DiGraph, MultiGraph, MultiDiGraph)

        a graph

      • source (Object)

        source

      • target (Object) (defaults to: nil)

        target

      • cutoff (Numeric, nil) (defaults to: nil)

        cutoff for the dijkstra algorithm

      Returns:

      • (Hash{ Object => Array<Object> }, Array<Object>)

        paths for all nodes/target node from given node

      
      
      110
      111
      112
      # File 'lib/networkx/shortest_path/weighted.rb', line 110
      
      def self.singlesource_dijkstra(graph, source, target=nil, cutoff=nil)
        multisource_dijkstra(graph, [source], target, cutoff)
      end

      .singlesource_dijkstra_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }

      Computes shortest paths to all nodes from the given node

      Parameters:

      Returns:

      • (Hash{ Object => Array<Object> })

        paths for all nodes from given node

      
      
      132
      133
      134
      # File 'lib/networkx/shortest_path/weighted.rb', line 132
      
      def self.singlesource_dijkstra_path(graph, source, cutoff=nil)
        multisource_dijkstra_path(graph, [source], cutoff)
      end

      .singlesource_dijkstra_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }

      Computes shortest path lengths to all nodes from the given node

      Parameters:

      Returns:

      • (Hash{ Object => Numeric })

        path lengths for all nodes from given node

      
      
      121
      122
      123
      # File 'lib/networkx/shortest_path/weighted.rb', line 121
      
      def self.singlesource_dijkstra_path_length(graph, source, cutoff=nil)
        multisource_dijkstra_path_length(graph, [source], cutoff)
      end

      .strong_product(g_1, g_2) ⇒ Graph, ...

      Returns the strong product of two graphs

      Parameters:

      Returns:

      
      
      161
      162
      163
      164
      165
      166
      167
      168
      169
      # File 'lib/networkx/operators/product.rb', line 161
      
      def self.strong_product(g_1, g_2)
        g = init_product_graph(g_1, g_2)
        g.add_nodes(node_product(g_1, g_2))
        g.add_edges(nodes_cross_edges(g_1, g_2))
        g.add_edges(edges_cross_nodes(g_1, g_2))
        g.add_edges(directed_edges_cross_edges(g_1, g_2))
        g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed?
        g
      end

      .symmetric_difference(g_1, g_2) ⇒ Graph, ...

      Performs the symmetric difference of two graphs

      Parameters:

      Returns:

      Raises:

      • (ArgumentError)
      
      
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      # File 'lib/networkx/operators/binary.rb', line 130
      
      def self.symmetric_difference(g_1, g_2)
        result = Marshal.load(Marshal.dump(g_1))
        result.clear
      
        raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?
        raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty?
      
        g_1.nodes.each { |u, attrs| result.add_node(u, attrs) }
      
        g_1.adj.each do |u, u_edges|
          u_edges.each do |v, uv_attrs|
            if g_1.multigraph?
              uv_attrs.each do |k, attrs|
                result.add_edge(u, v, attrs) unless g_2.edge?(u, v, k)
              end
            else
              result.add_edge(u, v, uv_attrs) unless g_2.edge?(u, v)
            end
          end
        end
      
        g_2.adj.each do |u, u_edges|
          u_edges.each do |v, uv_attrs|
            if g_2.multigraph?
              uv_attrs.each do |k, attrs|
                result.add_edge(u, v, attrs) unless g_1.edge?(u, v, k)
              end
            else
              result.add_edge(u, v, uv_attrs) unless g_1.edge?(u, v)
            end
          end
        end
        result
      end

      .tensor_product(g_1, g_2) ⇒ Graph, ...

      Returns the tensor product of two graphs

      Parameters:

      Returns:

      
      
      119
      120
      121
      122
      123
      124
      125
      # File 'lib/networkx/operators/product.rb', line 119
      
      def self.tensor_product(g_1, g_2)
        g = init_product_graph(g_1, g_2)
        g.add_nodes(node_product(g_1, g_2))
        g.add_edges(directed_edges_cross_edges(g_1, g_2))
        g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed?
        g
      end

      .to_matrix(graph, val, multigraph_weight = 'sum') ⇒ Object

      TODO: Reduce condition branches and method length

      
      
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      # File 'lib/networkx/to_matrix.rb', line 3
      
      def self.to_matrix(graph, val, multigraph_weight='sum')
        is_undirected = !graph.directed?
        is_multigraph = graph.multigraph?
        nodelen = graph.nodes.length
      
        m = NMatrix.new(nodelen, val)
        index = {}
        inv_index = {}
        ind = 0
      
        graph.nodes.each do |u, _|
          index[u] = ind
          inv_index[ind] = u
          ind += 1
        end
      
        if is_multigraph
          graph.adj.each do |u, edge_hash|
            edge_hash.each do |v, keys|
              all_weights = []
              keys.each do |_key, attrs|
                all_weights << attrs[:weight]
              end
      
              edge_attr = 0
      
              case multigraph_weight
              when 'sum'
                edge_attr = all_weights.inject(0, :+)
              when 'max'
                edge_attr = all_weights.max
              when 'min'
                edge_attr = all_weights.min
              end
      
              m[index[u], index[v]] = edge_attr
              m[index[v], index[u]] = edge_attr || 1 if is_undirected
            end
          end
        else
          graph.adj.each do |u, edge_hash|
            edge_hash.each do |v, attrs|
              m[index[u], index[v]] = (attrs[:weight] || 1)
              m[index[v], index[u]] = (attrs[:weight] || 1) if is_undirected
            end
          end
        end
        [m, inv_index]
      end

      .topological_sort(graph) ⇒ Array<Object>

      Returns the nodes arranged in the topologically sorted fashion

      Parameters:

      Returns:

      • (Array<Object>)

        Array of the nodes

      Raises:

      • (ArgumentError)
      
      
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      # File 'lib/networkx/auxillary_functions/dag.rb', line 33
      
      def self.topological_sort(graph)
        raise ArgumentError, 'Topological Sort not defined on undirected graphs!' unless graph.directed?
        nodes = []
        indegree_map = Hash[graph.nodes.each_key.map { |u| [u, graph.in_degree(u)] if graph.in_degree(u) > 0 }.compact]
        zero_indegree = graph.nodes.each_key.map { |u| u if graph.in_degree(u).zero? }.compact
      
        until zero_indegree.empty?
          node = zero_indegree.shift
          raise ArgumentError, 'Graph changed during iteration!' unless graph.nodes.key?(node)
          graph.adj[node].each_key do |child|
            indegree_map[child] -= 1
            if indegree_map[child].zero?
              zero_indegree << child
              indegree_map.delete(child)
            end
          end
          nodes << node
        end
        raise ArgumentError, 'Graph contains cycle or graph changed during iteration!' unless indegree_map.empty?
        nodes
      end

      .undirected_edges_cross_edges(g_1, g_2) ⇒ Object

      Returns the product of undirected edges with edges

      
      
      55
      56
      57
      58
      59
      60
      61
      62
      63
      # File 'lib/networkx/operators/product.rb', line 55
      
      def self.undirected_edges_cross_edges(g_1, g_2)
        result = []
        edges_in_array(g_1).each do |u, v, c|
          edges_in_array(g_2).each do |x, y, d|
            result << [[v, x], [u, y], hash_product(c, d)]
          end
        end
        result
      end

      .union(g_1, g_2) ⇒ Graph, ...

      Performs the union of two graphs

      Parameters:

      Returns:

      Raises:

      • (ArgumentError)
      
      
      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
      228
      # File 'lib/networkx/operators/binary.rb', line 200
      
      def self.union(g_1, g_2)
        raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?
      
        case g_1
        when NetworkX::MultiGraph
          new_graph = NetworkX::MultiGraph.new
        when NetworkX::MultiDiGraph
          new_graph = NetworkX::MultiDiGraph.new
        when NetworkX::Graph
          new_graph = NetworkX::Graph.new
        when NetworkX::DiGraph
          new_graph = NetworkX::DiGraph.new
        end
      
        new_graph.graph.merge!(g_1.graph)
        new_graph.graph.merge!(g_2.graph)
      
        raise ArgumentError, 'Graphs must be disjoint!' unless (g_1.nodes.keys & g_2.nodes.keys).empty?
      
        g1_edges = get_edges(g_1)
        g2_edges = get_edges(g_2)
      
        new_graph.add_nodes(g_1.nodes.keys)
        new_graph.add_edges(g1_edges)
        new_graph.add_nodes(g_2.nodes.keys)
        new_graph.add_edges(g2_edges)
      
        new_graph
      end

      .union_all(graphs) ⇒ Graph, ...

      Performs the union of many graphs

      Parameters:

      Returns:

      Raises:

      • (ArgumentError)
      
      
      7
      8
      9
      10
      11
      12
      13
      14
      15
      # File 'lib/networkx/operators/all.rb', line 7
      
      def self.union_all(graphs)
        raise ArgumentError, 'Argument array is empty' if graphs.empty?
        result = graphs.shift
      
        graphs.each do |graph|
          result = NetworkX.union(result, graph)
        end
        result
      end

      .wiener_index(graph) ⇒ Numeric

      Returns the wiener index of the graph

      Parameters:

      Returns:

      • (Numeric)

        wiener index of the graph

      
      
      7
      8
      9
      10
      11
      12
      # File 'lib/networkx/auxillary_functions/wiener.rb', line 7
      
      def self.wiener_index(graph)
        total = all_pairs_shortest_path_length(graph)
        wiener_ind = 0
        Hash[total].each { |_, distances| Hash[distances].each { |_, val| wiener_ind += val } }
        graph.directed? ? wiener_ind : wiener_ind / 2
      end

      Instance Method Details

      #augment(path, inf, r_adj) ⇒ Object

      Helper function for augmenting flow

      Raises:

      • (ArgumentError)
      
      
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      # File 'lib/networkx/flow/shortestaugmentingpath.rb', line 114
      
      def augment(path, inf, r_adj)
        flow = inf
        temp_path = path.clone
        u = temp_path.shift
        temp_path.each do |v|
          attr = r_adj[u][v]
          flow = [flow, attr[:capacity] - attr[:flow]].min
          u = v
        end
        raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf
        temp_path = path.clone
        u = temp_path.shift
        temp_path.each do |v|
          r_adj[u][v][:flow] += flow
          r_adj[v][u][:flow] -= flow
          u = v
        end
        flow
      end