Module: NetworkX

Defined in:
lib/networkx/others/grid_2d_graph.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/others/info.rb,
lib/networkx/multidigraph.rb,
lib/networkx/others/reads.rb,
lib/networkx/operators/all.rb,
lib/networkx/others/bridges.rb,
lib/networkx/traversals/bfs.rb,
lib/networkx/traversals/dfs.rb,
lib/networkx/operators/unary.rb,
lib/networkx/flow/edmondskarp.rb,
lib/networkx/flow/preflowpush.rb,
lib/networkx/operators/binary.rb,
lib/networkx/converters/to_csv.rb,
lib/networkx/operators/product.rb,
lib/networkx/others/generators.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,
lib/networkx/others/number_connected_components.rb

Overview

Reference: networkx.org/documentation/stable/_modules/networkx/generators/lattice.html#grid_2d_graph

Defined Under Namespace

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

Constant Summary collapse

VERSION = 
'0.4.0'.freeze

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

._build_flow_dict(graph, residual) ⇒ Object

Returns the flowdict of the graph



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/capacityscaling.rb', line 88

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

  if graph.multigraph?
    graph.nodes(data: true).each_key do |u|
      flow_dict[u] = {}
      graph.adj[u].each do |v, uv_edges|
        flow_dict[u][v] = uv_edges.transform_values do |e|
          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!(uv_edges.to_h do |_, val|
                                 [val[:temp_key][0], val[:flow]] if (val[:flow]).positive?
                               end)
      end
    end
  else
    graph.nodes(data: true).each_key do |u|
      flow_dict[u] = graph.adj[u].to_h 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]).positive? }
      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) 


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
 
# File 'lib/networkx/flow/capacityscaling.rb', line 42

def self._build_residual_network(graph)
  raise ArgumentError, 'Sum of demands should be 0!' \
    unless graph.nodes(data: true).values.map { |attr| attr[:demand] || 0 }.sum.zero?

  residual = NetworkX::MultiDiGraph.new(inf: 0)
  residual.add_nodes(graph.nodes(data: true).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).positive?
        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).positive?
      end
    end
  end

  temp_inf = [
    residual.nodes(data: true).map { |_u, attrs| attrs[:excess].abs }.sum,
    edge_list.map {|_, _, _, e| (e.has_key?(:capacity) && e[:capacity] != inf ? e[:capacity] : 0) }.sum * 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) 


26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/networkx/flow/capacityscaling.rb', line 26

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

  residual.nodes(data: true).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



119
120
121
122
123
124
125
126
 
# File 'lib/networkx/flow/preflowpush.rb', line 119

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



189
190
191
192
193
 
# File 'lib/networkx/shortest_path/weighted.rb', line 189

def self.all_pairs_dijkstra(graph, cutoff = nil)
  path = []
  graph.nodes(data: true).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



213
214
215
216
217
 
# File 'lib/networkx/shortest_path/weighted.rb', line 213

def self.all_pairs_dijkstra_path(graph, cutoff = nil)
  paths = []
  graph.nodes(data: true).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



201
202
203
204
205
 
# File 'lib/networkx/shortest_path/weighted.rb', line 201

def self.all_pairs_dijkstra_path_length(graph, cutoff = nil)
  path_lengths = []
  graph.nodes(data: true).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



94
95
96
97
98
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 94

def self.all_pairs_shortest_path(graph, cutoff = nil)
  shortest_paths = []
  graph.nodes(data: true).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



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

def self.all_pairs_shortest_path_length(graph, cutoff = nil)
  shortest_paths = []
  graph.nodes(data: true).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



373
374
375
376
377
 
# File 'lib/networkx/shortest_path/weighted.rb', line 373

def self.allpairs_bellmanford_path(graph, cutoff = nil)
  paths = []
  graph.nodes(data: true).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



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

def self.allpairs_bellmanford_path_length(graph, cutoff = nil)
  path_lengths = []
  graph.nodes(data: true).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) 


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

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



3
4
5
6
7
8
9
10
11
 
# File 'lib/networkx/flow/preflowpush.rb', line 3

def self.arbitrary_element(iterable)
  if iterable.is_a?(Hash)
    iterable.first[0]
  elsif iterable.respond_to?(:first)
    iterable.first
  elsif iterable.respond_to?(:[])
    iterable[0]
  end
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) 


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
 
# File 'lib/networkx/shortest_path/astar.rb', line 11

def self.astar_path(graph, source, target, heuristic = nil)
  warn 'A* is not implemented for MultiGraph and MultiDiGraph' if graph.is_a?(MultiGraph) || graph.is_a?(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.has_key?(curnode)

    explored[curnode] = parent

    graph.adj[curnode].each do |u, attrs|
      next if explored.has_key?(u)

      ncost = dist + (attrs[:weight] || 1)
      if enqueued.has_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) 


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

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) 


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

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) ⇒ Matrix

Computes authority matrix for the graph

Parameters:

Returns:

  • (Matrix) —

    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 * 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



326
327
328
329
 
# File 'lib/networkx/shortest_path/weighted.rb', line 326

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) 


309
310
311
312
313
314
315
316
317
 
# File 'lib/networkx/shortest_path/weighted.rb', line 309

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)
  raise ArgumentError, 'Node not reachable!' unless length.has_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) 


277
278
279
280
281
282
283
284
285
286
287
288
 
# File 'lib/networkx/shortest_path/weighted.rb', line 277

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(data: true).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) 


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

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



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
 
# File 'lib/networkx/flow/edmondskarp.rb', line 23

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.has_key?(v)

          q << v
        end
      end
      return [nil, nil, nil] if q.empty?

      q_s = q
    else
      q_t.each do |u|
        residual.pred[u].each do |v, uv_attrs|
          next unless !succ.has_key?(v) && uv_attrs[:flow] < uv_attrs[:capacity]

          succ[v] = u
          return [v, pred, succ] if pred.has_key?(v)

          q << v
        end
      end
      return [nil, nil, nil] if q.empty?

      q_t = q
    end
  end
end

.bridges(graph) ⇒ [Object, Object]

Returns bridges.

Parameters:

  • graph (Graph) —

    Graph

Returns:

  • ([Object, Object]) —

    bridges



7
8
9
 
# File 'lib/networkx/others/bridges.rb', line 7

def self.bridges(graph)
  each_bridge(graph).to_a
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



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

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]).positive? }
  end
  flow_dict
end

.build_residual_network(graph) ⇒ DiGraph

Builds a residual graph from a constituent graph

Parameters:

Returns:

Raises:

  • (NotImplementedError) 


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
 
# File 'lib/networkx/flow/utils.rb', line 61

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(data: true).keys)
  inf = Float::INFINITY
  edge_list = []

  graph.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      edge_list << [u, v, uv_attrs] if (uv_attrs[:capacity] || inf).positive? && u != v
    end
  end

  inf_chk = 3 * edge_list.inject(0) do |result, arr|
    arr[2].has_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



127
128
129
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
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
 
# File 'lib/networkx/flow/capacityscaling.rb', line 127

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]).negative?

          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(data: true).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.has_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?
        s_set.delete(s)
      else
        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) }
      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(data: true).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(g1, g2) ⇒ Graph, ...

Returns the cartesian product of two graphs

Parameters:

Returns:



129
130
131
132
133
134
135
 
# File 'lib/networkx/operators/product.rb', line 129

def self.cartesian_product(g1, g2)
  g = init_product_graph(g1, g2)
  g.add_nodes(node_product(g1, g2))
  g.add_edges(edges_cross_nodes(g1, g2))
  g.add_edges(nodes_cross_edges(g1, g2))
  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(data: true).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(data: true).map { |u, attrs| [u, attrs] })
  graph.adj.each do |u, u_edges|
    graph.nodes(data: true).each { |v, attrs| result.add_edge(u, v, **attrs) if !u_edges.has_key?(v) && u != v }
  end
  result
end

.compose(g1, g2) ⇒ 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
 
# File 'lib/networkx/operators/binary.rb', line 173

def self.compose(g1, g2)
  result = g1.class.new

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

  result.add_nodes(g1.nodes(data: true).map { |u, attrs| [u, attrs] })
  result.add_nodes(g2.nodes(data: true).map { |u, attrs| [u, attrs] })

  if g1.multigraph?
    g1.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, **attrs) } } }
    g2.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, **attrs) } } }
  else
    g1.adj.each { |u, u_edges| u_edges.each { |v, attrs| result.add_edge(u, v, **attrs) } }
    g2.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) 


55
56
57
58
59
60
61
62
63
64
 
# File 'lib/networkx/operators/all.rb', line 55

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.



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/operators/binary.rb', line 27

def self.convert_to_distinct_labels(graph, starting_int = -1)
  new_graph = graph.class.new

  idx_dict = graph.nodes(data: true).keys.to_h do |v|
    starting_int += 1
    [v, starting_int]
  end

  graph.nodes(data: true).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

.cycle?(undirected_graph) ⇒ book

Returns whether the given undirected cycle has cycle.

Parameters:

  • undirected_graph (Graph) —

    an undirected graph

Returns:

  • (book) —

    true if the given graph has cycle. otherwise, false.



107
108
109
110
111
112
113
 
# File 'lib/networkx/auxillary_functions/cycles.rb', line 107

def self.cycle?(undirected_graph)
  uf = NetworkX::UnionFind.new
  undirected_graph.edges.each do |x, y|
    uf[x] == uf[y] ? (return [x, y]) : uf.unite(x, y)
  end
  false
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



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
 
# File 'lib/networkx/auxillary_functions/cycles.rb', line 8

def self.cycle_basis(graph, root = nil)
  gnodes = graph.nodes(data: true).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.has_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
13
 
# 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



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/networkx/flow/utils.rb', line 107

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) 


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/dfs.rb', line 10

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 += 1 if depth_limit
  depth_limit = graph.nodes(data: true).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



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

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

.difference(g1, g2) ⇒ Graph, ...

Performs the difference of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


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
 
# File 'lib/networkx/operators/binary.rb', line 93

def self.difference(g1, g2)
  result = g1.class.new

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

  unless (g1.nodes(data: true).keys - g2.nodes(data: true).keys).empty?
    raise ArgumentError, 'Node sets must be equal!'
  end

  g1.nodes(data: true).each { |u, attrs| result.add_node(u, **attrs) }

  g1.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if g1.multigraph?
        next if u > v && g1.instance_of?(MultiGraph)

        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, **attrs) unless g2.edge?(u, v, k)
        end
      else
        result.add_edge(u, v, **uv_attrs) unless g2.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



163
164
165
166
 
# File 'lib/networkx/shortest_path/weighted.rb', line 163

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) 


146
147
148
149
150
151
152
153
154
 
# File 'lib/networkx/shortest_path/weighted.rb', line 146

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.has_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 => Array<Object> }, Hash{ Object => Numeric }>] predcessor hash and distance hash



176
177
178
179
180
 
# File 'lib/networkx/shortest_path/weighted.rb', line 176

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(g1, g2) ⇒ Object

Returns the product of directed edges with edges



40
41
42
43
44
45
46
47
48
 
# File 'lib/networkx/operators/product.rb', line 40

def self.directed_edges_cross_edges(g1, g2)
  result = []
  edges_in_array(g1).each do |u, v, c|
    edges_in_array(g2).each do |x, y, d|
      result << [[u, x], [v, y], hash_product(c, d)]
    end
  end
  result
end

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

Helper function for discharging a node



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
164
165
 
# File 'lib/networkx/flow/preflowpush.rb', line 135

def self.discharge(u_node, is_phase1, 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_phase1 && 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(g1, g2) ⇒ Graph, ...

Performs the disjoint union of two graphs

Parameters:

Returns:



225
226
227
228
229
230
231
232
 
# File 'lib/networkx/operators/binary.rb', line 225

def self.disjoint_union(g1, g2)
  new_g1 = convert_to_distinct_labels(g1)
  new_g2 = convert_to_distinct_labels(g2)
  result = union(new_g1, new_g2)
  result.graph.merge!(g1.graph)
  result.graph.merge!(g2.graph)
  result
end

.disjoint_union_all(graphs) ⇒ Graph, ...

Performs the disjoint union of many graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


23
24
25
26
27
28
29
30
31
32
 
# File 'lib/networkx/operators/all.rb', line 23

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



385
386
387
388
389
390
391
 
# File 'lib/networkx/shortest_path/weighted.rb', line 385

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

.each_bridge(graph) ⇒ Object

Parameters:

  • graph (Graph) —

    Graph



12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/networkx/others/bridges.rb', line 12

def self.each_bridge(graph)
  return enum_for(:each_bridge, graph) unless block_given?

  graph.each_edge.with_index do |(s_i, t_i), i|
    uf = UnionFind.new(1..graph.number_of_nodes)
    graph.each_edge.with_index do |(s_j, t_j), j|
      uf.unite(s_j, t_j) if i != j
    end
    yield [s_i, t_i] unless uf.same?(s_i, t_i)
  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
18
 
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 8

def self.eccentricity(graph, node = nil)
  e = {}
  graph.nodes(data: true).each do |u, _|
    length = single_source_shortest_path_length(graph, u)
    l = length.length
    raise ArgumentError, 'Found infinite path length!' unless l == graph.nodes(data: true).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

  • start (Object) —

    node to start dfs from

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

    the orientation of edges of graph



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
 
# File 'lib/networkx/traversals/edge_dfs.rb', line 51

def self.edge_dfs(graph, start, orientation = nil)
  case orientation
  when :reverse
    graph = graph.reverse if graph.instance_of?(::NetworkX::DiGraph) || graph.instance_of?(::NetworkX::MultiDiGraph)
  when :ignore
    graph = graph.to_undirected if graph.instance_of?(::NetworkX::DiGraph)
    graph = graph.to_multigraph if graph.instance_of?(::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



31
32
33
34
35
36
 
# File 'lib/networkx/traversals/edge_dfs.rb', line 31

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(g1, g2) ⇒ Object

Returns the product of edges with edges



62
63
64
65
66
67
68
69
70
 
# File 'lib/networkx/operators/product.rb', line 62

def self.edges_cross_nodes(g1, g2)
  result = []
  edges_in_array(g1).each do |u, v, d|
    g2.nodes(data: true).each_key do |x|
      result << [[u, x], [v, x], d]
    end
  end
  result
end

.edges_cross_nodes_and_nodes(g1, g2) ⇒ Object

Returns the product of edges with pairs of nodes



84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/networkx/operators/product.rb', line 84

def self.edges_cross_nodes_and_nodes(g1, g2)
  result = []
  edges_in_array(g1).each do |u, v, d|
    g2.nodes(data: true).each_key do |x|
      g2.nodes(data: true).each_key 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



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

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



112
113
114
 
# File 'lib/networkx/flow/edmondskarp.rb', line 112

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



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/networkx/flow/edmondskarp.rb', line 61

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) 


86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/networkx/flow/edmondskarp.rb', line 86

def self.edmondskarp_impl(graph, source, target, residual, cutoff)
  raise ArgumentError, 'Source not in graph!' unless graph.nodes(data: true).has_key?(source)
  raise ArgumentError, 'Target not in graph!' unless graph.nodes(data: true).has_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_value] = 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



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
 
# File 'lib/networkx/auxillary_functions/cliques.rb', line 7

def self.find_cliques(graph)
  return nil if graph.nodes(data: true).empty?

  q = [nil]
  adj = {}
  graph.nodes(data: true).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(data: true).keys
  cand = graph.nodes(data: true).keys
  u = subg.max { |n1, n2| (cand & adj[n1]).length <=> (cand & adj[n2]).length }
  ext_u = cand - adj[u]
  stack = []
  cliques = []
  begin
    loop do
      if ext_u.empty?
        q.pop
        subg, cand, ext_u = stack.pop
      else
        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 { |n1, n2| (cand & adj[n1]).length <=> (cand & adj[n2]).length }
            ext_u = cand - adj[u]
          end
        end
      end
    end
  rescue NoMethodError
    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) 


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
 
# File 'lib/networkx/auxillary_functions/cycles.rb', line 53

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



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/networkx/shortest_path/dense.rb', line 8

def self.floyd_warshall(graph)
  a, index = to_matrix(graph, Float::INFINITY, 'min')
  nodelen = graph.nodes(data: true).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.has_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_node ⇒ Object

Returns a label for unique node



3
4
5
 
# File 'lib/networkx/flow/capacityscaling.rb', line 3

def self.generate_unique_node
  SecureRandom.uuid
end

.get_edges(graph) ⇒ Object

Returns the edges of the graph in an array



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/networkx/operators/binary.rb', line 3

def self.get_edges(graph)
  edges = []
  if graph.is_a?(MultiGraph)
    graph.adj.each do |u, v_keys|
      v_keys.each do |v, key_attrs|
        next if u > v

        key_attrs.each do |_key, attributes|
          edges << [u, v, attributes]
        end
      end
    end
  else
    graph.adj.each do |u, u_attrs|
      u_attrs.each do |v, uv_attrs|
        edges << [u, v, uv_attrs]
      end
    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



380
381
382
 
# File 'lib/networkx/shortest_path/weighted.rb', line 380

def self.get_sources(graph)
  graph.nodes(data: true).collect { |k, _v| k }
end

.get_weight(graph) ⇒ Object

Helper function to extract weight from a adjecency hash



3
4
5
6
7
8
9
 
# File 'lib/networkx/shortest_path/weighted.rb', line 3

def self.get_weight(graph)
  lambda do |_, _, attrs|
    return attrs[:weight] || 1 unless graph.multigraph?

    attrs.group_by { |_k, vals| vals[:weight] || 1 }.keys.max
  end
end

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

Helper function for global relabel heuristic



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
 
# File 'lib/networkx/flow/preflowpush.rb', line 181

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.has_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:



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
 
# File 'lib/networkx/converters/to_csv.rb', line 6

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(data: true).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

.grid_2d_graph(m, n, periodic: false, create_using: NetworkX::Graph) ⇒ Object

Parameters:

  • m (Integer) —

    the number of rows

  • n (Integer) —

    the number of columns

  • create_using (Class) (defaults to: NetworkX::Graph) —

    graph class. this is optional. default is NetworkX::Graph.



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
 
# File 'lib/networkx/others/grid_2d_graph.rb', line 12

def self.grid_2d_graph(m, n, periodic: false, create_using: NetworkX::Graph)
  warn('sorry, periodic is not done yet') if periodic

  m.is_a?(Integer) or raise(ArgumentError, "[NetworkX] argument m: Integer, not #{m.class}")
  n.is_a?(Integer) or raise(ArgumentError, "[NetworkX] argument n: Integer, not #{n.class}")
  create_using.is_a?(Class) \
    or raise(ArgumentError, "[NetworkX] argument create_using: `Graph` class or children, not #{create_using.class}")

  g = create_using.new

  a = []
  m.times { |i| n.times { |j| a << [i, j] } }
  g.add_nodes_from(a)

  e1 = []
  (m - 1).times { |i| n.times { |j| e1 << [[i, j], [i + 1, j]] } }
  g.add_edges_from(e1)

  e2 = []
  m.times { |i| (n - 1).times { |j| e2 << [[i, j], [i, j + 1]] } }
  g.add_edges_from(e2)

  g.add_edges_from(g.edges.map { |i, j| [j, i] }) if g.directed?

  g
end

.hash_product(hash1, hash2) ⇒ Object

Returns the hash product of two hashes



24
25
26
 
# File 'lib/networkx/operators/product.rb', line 24

def self.hash_product(hash1, hash2)
  (hash1.keys | hash2.keys).to_h { |n| [n, [hash1[n], hash2[n]]] }
end

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

Helper function for bellman ford



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
262
263
264
265
266
267
 
# File 'lib/networkx/shortest_path/weighted.rb', line 220

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(data: true).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.has_key?(v) && dist_v == dist[v]
        pred[v] << u
      end
    end
  end
  unless paths.nil?
    dsts = pred
    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



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
 
# File 'lib/networkx/shortest_path/weighted.rb', line 12

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.has_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.has_key?(u)
        raise ValueError, 'Contradictory weights found!' if vu_dist < dist[u]
      elsif !seen.has_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



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 53

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.has_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



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 3

def self.help_single_shortest_path_length(adj, firstlevel, cutoff)
  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.has_key?(u)

        seen[u] = level
        nextlevel.merge!(adj[u])
        e.yield [u, level]
      end
      level += 1
    end
    seen.clear
  end
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



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
 
# File 'lib/networkx/link_analysis/hits.rb', line 10

def self.hits(graph, max_iter = 100, tol = 1e-8, nstart)
  return [{}, {}] if graph.nodes(data: true).empty?

  h = nstart
  sum = h.values.sum
  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 }.sum < tol
    raise ArgumentError, 'Power Iteration failed to converge!' if i > max_iter

    i += 1
  end
  [h, a]
end

.hub_matrix(graph) ⇒ Matrix

Computes hub matrix for the graph

Parameters:

Returns:

  • (Matrix) —

    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 * matrix.transpose
end

.info(graph) ⇒ Object 



4
5
6
7
8
9
10
 
# File 'lib/networkx/others/info.rb', line 4

def self.info(graph)
  info = ''
  info << "Type: #{graph.class}\n"
  info << "Number of nodes: #{graph.number_of_nodes}\n"
  info << "Number of edges: #{graph.number_of_edges}\n"
  info
end

.init_product_graph(g1, g2) ⇒ Object

Initializes the product graph

Raises:

  • (ArgumentError) 


97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/networkx/operators/product.rb', line 97

def self.init_product_graph(g1, g2)
  raise ArgumentError, 'Arguments must be both directed or undirected!' unless g1.directed? == g2.directed?

  g = if g1.multigraph? || g2.multigraph?
        NetworkX::MultiGraph.new
      else
        NetworkX::Graph.new
      end
  g = g.to_directed if g.directed?
  g
end

.intersection(g1, g2) ⇒ Graph, ...

Performs the intersection of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


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
 
# File 'lib/networkx/operators/binary.rb', line 59

def self.intersection(g1, g2)
  result = g1.class.new

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

  unless (g1.nodes(data: true).keys - g2.nodes(data: true).keys).empty?
    raise ArgumentError, 'Node sets must be equal!'
  end

  g1.nodes(data: true).each { |u, attrs| result.add_node(u, **attrs) }

  g1, g2 = g2, g1 if g1.number_of_edges > g2.number_of_edges
  g1.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if g1.multigraph?
        next if u > v && g1.instance_of?(MultiGraph)

        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, **attrs) if g2.edge?(u, v, k)
        end
      elsif g2.edge?(u, v)
        result.add_edge(u, v, **uv_attrs)
      end
    end
  end
  result
end

.intersection_all(graphs) ⇒ Graph, ...

Performs the intersection of many graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


39
40
41
42
43
44
45
46
47
48
 
# File 'lib/networkx/operators/all.rb', line 39

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<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes



405
406
407
408
409
410
411
412
413
414
415
416
 
# File 'lib/networkx/shortest_path/weighted.rb', line 405

def self.johnson(graph)
  dist, pred = {}, {}
  sources = get_sources(graph)
  graph.nodes(data: true).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)
  new_weight = ->(u, v, d) { weight.call(u, v, d) + dist_bellman[u] - dist_bellman[v] }
  dist_path = dist_path_lambda(graph, new_weight)
  set_path_lengths_johnson(graph, dist_path, new_weight)
end

.json_to_graph(json_str) ⇒ Graph, ...

Returns a graph from the json encoded graph

Parameters:

  • json_str (JSON) —

    json encoded string

Returns:



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/networkx/converters/to_json.rb', line 21

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(g1, g2) ⇒ Graph, ...

Returns the lexicographic product of two graphs

Parameters:

Returns:



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

def self.lexicographic_product(g1, g2)
  g = init_product_graph(g1, g2)
  g.add_nodes(node_product(g1, g2))
  g.add_edges(edges_cross_nodes_and_nodes(g1, g2))
  g.add_edges(nodes_cross_edges(g1, g2))
  g
end

.maximal_independent_set(graph, nodes) ⇒ Numeric

Returns the maximal independent set of a graph

Parameters:

Returns:

  • (Numeric) —

    radius of the graph



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/networkx/auxillary_functions/mis.rb', line 8

def self.maximal_independent_set(graph, nodes)
  if (graph.nodes(data: true).keys - nodes).empty?
    raise 'The array containing the nodes should be a subset of the graph!'
  end

  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(data: true).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:



19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/networkx/auxillary_functions/mst.rb', line 19

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(data: true).keys)
  while edges.any? && mst.nodes(data: true).length <= graph.nodes(data: true).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
76
77
 
# 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.has_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:

Returns:

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

    paths for any nodes from given nodes



100
101
102
103
 
# File 'lib/networkx/shortest_path/weighted.rb', line 100

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:

Returns:

  • (Hash{ Object => Numeric }) —

    path lengths for any nodes from given nodes

Raises:

  • (ValueError) 


86
87
88
89
90
91
 
# File 'lib/networkx/shortest_path/weighted.rb', line 86

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



12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/networkx/flow/capacityscaling.rb', line 12

def self.negative_edge_cycle(graph)
  newnode = generate_unique_node
  graph.add_edges(graph.nodes(data: true).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(g1, g2) ⇒ Object

Returns the node product of nodes of two graphs



29
30
31
32
33
34
35
36
37
 
# File 'lib/networkx/operators/product.rb', line 29

def self.node_product(g1, g2)
  n_product = []
  g1.nodes(data: true).each do |k1, attrs1|
    g2.nodes(data: true).each do |k2, attrs2|
      n_product << [[k1, k2], hash_product(attrs1, attrs2)]
    end
  end
  n_product
end

.nodes_cross_edges(g1, g2) ⇒ Object

Returns the product of directed nodes with edges



73
74
75
76
77
78
79
80
81
 
# File 'lib/networkx/operators/product.rb', line 73

def self.nodes_cross_edges(g1, g2)
  result = []
  g1.nodes(data: true).each_key do |x|
    edges_in_array(g2).each do |u, v, d|
      result << [[x, u], [x, v], d]
    end
  end
  result
end

.number_connected_components(graph) ⇒ Integer Also known as: number_of_connected_components

Returns the number of connected components on graph.

Parameters:

Returns:

  • (Integer) —

    the number of connected components on graph



8
9
10
11
12
 
# File 'lib/networkx/others/number_connected_components.rb', line 8

def self.number_connected_components(graph)
  uf = NetworkX::UnionFind.new(graph.nodes(data: false))
  graph.each_edge { |x, y| uf.unite(x, y) }
  uf.groups.size
end

.number_of_bridges(graph) ⇒ Integer

Returns the number of bridges.

Parameters:

  • graph (Graph) —

    Graph

Returns:

  • (Integer) —

    the number of bridges



27
28
29
 
# File 'lib/networkx/others/bridges.rb', line 27

def self.number_of_bridges(graph)
  bridges(graph).size
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



58
59
60
61
 
# File 'lib/networkx/auxillary_functions/cliques.rb', line 58

def self.number_of_cliques(graph, node)
  cliques = find_cliques(graph)
  cliques.count { |c| c.include?(node) }
end

.out_edges(graph, node) ⇒ Object

Helper function for edge_dfs

Parameters:



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/networkx/traversals/edge_dfs.rb', line 6

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.instance_of?(::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.instance_of?(::NetworkX::MultiDiGraph) || visited[[v, node, k]].nil?
          visited[[node, v, k]] = true
          edges << [node, v, k]
        end
      end
    end
  end
  edges
end

.pagerank(graph, alpha: 0.85, personalization: nil, eps: 1e-6, max_iter: 100) ⇒ Hash of Object => Float

Computes pagerank values for the graph

Parameters:

  • graph (Graph) —

    a graph

  • alpha (Numeric) (defaults to: 0.85) —

    the alpha value to compute the pagerank

  • eps (Numeric) (defaults to: 1e-6) —

    tolerence to check for convergence

  • max_iter (Integer) (defaults to: 100) —

    max iterations for the pagerank algorithm to run

Returns:

  • (Hash of Object => Float) —

    pagerank values of the graph



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
 
# File 'lib/networkx/link_analysis/pagerank.rb', line 10

def self.pagerank(graph, alpha: 0.85, personalization: nil, eps: 1e-6, max_iter: 100)
  n = graph.number_of_nodes

  matrix, index_to_node = NetworkX.to_matrix(graph, 0)

  index_from_node = index_to_node.invert

  probabilities = Array.new(n) do |i|
    total = matrix.row(i).sum
    (matrix.row(i) / total.to_f).to_a
  end

  curr = personalization
  unless curr
    curr = Array.new(n)
    graph.each_node{|node| curr[index_from_node[node]] = 1.0 / n }
  end

  max_iter.times do
    prev = curr.clone

    n.times do |i|
      ip = 0.0
      n.times do |j|
        ip += probabilities[j][i] * prev[j]
      end
      curr[i] = (alpha * ip) + ((1.0 - alpha) / n * 1.0)
    end

    err = (0...n).map{|i| (prev[i] - curr[i]).abs }.sum
    return (0...n).map{|i| [index_to_node[i], curr[i]] }.sort.to_h if err < eps
  end
  warn "pagerank() failed within #{max_iter} iterations. Please inclease max_iter: or loosen eps:"
  (0...n).map{|i| [index_to_node[i], curr[i]] }.sort.to_h
end

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

Returns the specified power of the graph

Parameters:

Returns:

Raises:

  • (ArgumentError) 


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
 
# File 'lib/networkx/operators/product.rb', line 173

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(data: true).map { |n, attrs| [n, attrs] })
  graph.nodes(data: true).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.has_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) 


110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 110

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.has_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



246
247
248
 
# File 'lib/networkx/flow/preflowpush.rb', line 246

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) 


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
114
115
116
 
# File 'lib/networkx/flow/preflowpush.rb', line 14

def self.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only)
  raise ArgumentError, 'Source not in graph!' unless graph.nodes(data: true).has_key?(source)
  raise ArgumentError, 'Target not in graph!' unless graph.nodes(data: true).has_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.negative?

  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.has_key?(source)
    r_network.graph[:flow_value] = 0
    return r_network
  end

  n = r_network.nodes(data: true).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.has_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.positive?
  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]).positive? ? level.active.add(u) : level.inactive.add(u)
    end
  end

  height = max_height
  while height.positive?
    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(node1, node2, flow, residual_nodes, residual_adj) ⇒ Object

Helper function for augmenting flow



210
211
212
213
214
215
 
# File 'lib/networkx/flow/preflowpush.rb', line 210

def self.push(node1, node2, flow, residual_nodes, residual_adj)
  residual_adj[node1][node2][:flow] += flow
  residual_adj[node2][node1][:flow] -= flow
  residual_nodes[node1][:excess] -= flow
  residual_nodes[node2][:excess] += flow
end

.radius(graph) ⇒ Numeric

Returns the radius of a graph

Parameters:

Returns:

  • (Numeric) —

    radius of the graph



34
35
36
 
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 34

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



129
130
131
132
 
# File 'lib/networkx/flow/preflowpush.rb', line 129

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



218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/networkx/flow/preflowpush.rb', line 218

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.has_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



394
395
396
397
398
 
# File 'lib/networkx/shortest_path/weighted.rb', line 394

def self.set_path_lengths_johnson(graph, dist_path, new_weight)
  path_lengths = []
  graph.nodes(data: true).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) (defaults to: false) —

    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



149
150
151
152
153
 
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 149

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) 


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
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
 
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 3

def self.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff)
  raise ArgumentError, 'Source is not in the graph!' unless graph.nodes(data: true).has_key?(source)
  raise ArgumentError, 'Target is not in the graph!' unless graph.nodes(data: true).has_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.has_key?(v) && attrs[:flow] < attrs[:capacity]
        heights[v] = height
        q << [v, height]
      end
    end
  end

  unless heights.has_key?(source)
    residual.graph[:flow_value] = 0
    return residual
  end

  n = graph.nodes(data: true).length
  m = residual.size / 2

  r_nodes.each do |node, attrs|
    attrs[:height] = heights.has_key?(node) ? heights[node] : n
    attrs[:curr_edge] = CurrentEdge.new(r_adj[node])
  end

  counts = [0] * (2 * n - 1)
  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
            done = true
            break
          else
            residual.graph[:flow_value] = flow_value
            return residual
          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) 


79
80
81
82
83
84
85
86
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 79

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) 


32
33
34
35
36
37
38
 
# File 'lib/networkx/shortest_path/unweighted.rb', line 32

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(data: true).length)
end

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

Raises:

  • (ArgumentError) 


290
291
292
293
294
295
296
297
298
299
300
 
# File 'lib/networkx/shortest_path/weighted.rb', line 290

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.has_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



338
339
340
341
 
# File 'lib/networkx/shortest_path/weighted.rb', line 338

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



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

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



113
114
115
 
# File 'lib/networkx/shortest_path/weighted.rb', line 113

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



135
136
137
 
# File 'lib/networkx/shortest_path/weighted.rb', line 135

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



124
125
126
 
# File 'lib/networkx/shortest_path/weighted.rb', line 124

def self.singlesource_dijkstra_path_length(graph, source, cutoff = nil)
  multisource_dijkstra_path_length(graph, [source], cutoff)
end

.strong_product(g1, g2) ⇒ Graph, ...

Returns the strong product of two graphs

Parameters:

Returns:



157
158
159
160
161
162
163
164
165
 
# File 'lib/networkx/operators/product.rb', line 157

def self.strong_product(g1, g2)
  g = init_product_graph(g1, g2)
  g.add_nodes(node_product(g1, g2))
  g.add_edges(nodes_cross_edges(g1, g2))
  g.add_edges(edges_cross_nodes(g1, g2))
  g.add_edges(directed_edges_cross_edges(g1, g2))
  g.add_edges(undirected_edges_cross_edges(g1, g2)) unless g.directed?
  g
end

.symmetric_difference(g1, g2) ⇒ Graph, ...

Performs the symmetric difference of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


126
127
128
129
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
164
165
 
# File 'lib/networkx/operators/binary.rb', line 126

def self.symmetric_difference(g1, g2)
  result = g1.class.new

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

  unless (g1.nodes(data: true).keys - g2.nodes(data: true).keys).empty?
    raise ArgumentError, 'Node sets must be equal!'
  end

  g1.nodes(data: true).each { |u, attrs| result.add_node(u, **attrs) }

  g1.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if g1.multigraph?
        next if u > v && g1.instance_of?(MultiGraph)

        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, **attrs) unless g2.edge?(u, v, k)
        end
      else
        result.add_edge(u, v, **uv_attrs) unless g2.edge?(u, v)
      end
    end
  end

  g2.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      next if u > v && g1.instance_of?(MultiGraph)

      if g2.multigraph?
        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, **attrs) unless g1.edge?(u, v, k)
        end
      else
        result.add_edge(u, v, **uv_attrs) unless g1.edge?(u, v)
      end
    end
  end
  result
end

.tensor_product(g1, g2) ⇒ Graph, ...

Returns the tensor product of two graphs

Parameters:

Returns:



115
116
117
118
119
120
121
 
# File 'lib/networkx/operators/product.rb', line 115

def self.tensor_product(g1, g2)
  g = init_product_graph(g1, g2)
  g.add_nodes(node_product(g1, g2))
  g.add_edges(directed_edges_cross_edges(g1, g2))
  g.add_edges(undirected_edges_cross_edges(g1, g2)) unless g.directed?
  g
end

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



2
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
 
# File 'lib/networkx/to_matrix.rb', line 2

def self.to_matrix(graph, val, multigraph_weight = 'sum')
  is_undirected = !graph.directed?
  is_multigraph = graph.multigraph?
  nodelen = graph.nodes(data: true).length

  m = Matrix.build(nodelen) { val }
  index = {}
  inv_index = {}
  ind = 0

  graph.nodes(data: true).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.sum
        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

.to_number_if_possible(str) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
 
# File 'lib/networkx/others/reads.rb', line 42

def self.to_number_if_possible(str)
  case str
  when /^[+-]?[0-9]+$/
    str.to_i
  when /^([+-]?\d*\.\d*)|(\d*[eE][+-]?\d+)$/
    str.to_f
  else
    str
  end
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
54
55
56
57
58
 
# 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 = graph.nodes(data: true).each_key.map do |u|
    [u, graph.in_degree(u)] if graph.in_degree(u).positive?
  end.compact.to_h
  zero_indegree = graph.nodes(data: true).each_key.select { |u| graph.in_degree(u).zero? }

  until zero_indegree.empty?
    node = zero_indegree.shift
    raise ArgumentError, 'Graph changed during iteration!' unless graph.nodes(data: true).has_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(g1, g2) ⇒ Object

Returns the product of undirected edges with edges



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

def self.undirected_edges_cross_edges(g1, g2)
  result = []
  edges_in_array(g1).each do |u, v, c|
    edges_in_array(g2).each do |x, y, d|
      result << [[v, x], [u, y], hash_product(c, d)]
    end
  end
  result
end

.union(g1, g2) ⇒ Graph, ...

Performs the union of two graphs

Parameters:

Returns:

Raises:

  • (ArgumentError) 


197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/networkx/operators/binary.rb', line 197

def self.union(g1, g2)
  raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g1.multigraph? == g2.multigraph?

  new_graph = g1.class.new
  new_graph.graph.merge!(g1.graph)
  new_graph.graph.merge!(g2.graph)

  unless (g1.nodes(data: true).keys & g2.nodes(data: true).keys).empty?
    raise ArgumentError, 'Graphs must be disjoint!'
  end

  g1_edges = get_edges(g1)
  g2_edges = get_edges(g2)

  new_graph.add_nodes(g1.nodes(data: true).keys)
  new_graph.add_edges(g1_edges)
  new_graph.add_nodes(g2.nodes(data: true).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
16
 
# 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
  total.to_h.each { |_, distances| distances.to_h.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) 


108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 108

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