module NetworkX

TODO: Reduce module length

TODO: Reduce module length

TODO: Reduce module length

TODO: Reduce module length

TODO: Reduce module length

TODO: Reduce module length

Constants

VERSION

Public Class Methods

_build_flow_dict(graph, residual) click to toggle source

Returns the flowdict of the graph

# File lib/networkx/flow/capacityscaling.rb, line 93
def self._build_flow_dict(graph, residual)
  flow_dict = {}
  inf = Float::INFINITY

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

Returns the residual graph of the given graph

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

  # TODO: Selfloop edges check

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

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

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

Detects the unboundedness in the residual graph

# File lib/networkx/flow/capacityscaling.rb, line 30
def self._detect_unboundedness(residual)
  g = NetworkX::DiGraph.new
  g.add_nodes(residual.nodes.keys.zip(residual.nodes.values))
  inf = residual.graph[:inf]

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

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

# File lib/networkx/flow/preflowpush.rb, line 116
def self.activate(node, source, target, levels, residual_nodes)
  return if node == source || node == target
  return unless level.inactive.include?(node)
  level = levels[residual_nodes[node][:height]]
  level.inactive.delete(node)
  level.active.add(node)
end
all_pairs_dijkstra(graph, cutoff=nil) click to toggle source

Finds shortest weighted paths and lengths between all nodes

@param graph [Graph, DiGrhelp_dijkaph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Array<Object, Array<Hash{ Object => Numeric }, Hash{ Object => Array<Object> }>>]

paths and path lengths between all nodes
# File lib/networkx/shortest_path/weighted.rb, line 184
def self.all_pairs_dijkstra(graph, cutoff=nil)
  path = []
  graph.nodes.each_key { |n| path << [n, singlesource_dijkstra(graph, n, nil, cutoff)] }
  path
end
all_pairs_dijkstra_path(graph, cutoff=nil) click to toggle source

Finds shortest weighted paths between all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Array<Object, Hash{ Object => Array<Object> }>] path lengths between all nodes

# File lib/networkx/shortest_path/weighted.rb, line 208
def self.all_pairs_dijkstra_path(graph, cutoff=nil)
  paths = []
  graph.nodes.each_key { |n| paths << singlesource_dijkstra_path(graph, n, cutoff) }
  paths
end
all_pairs_dijkstra_path_length(graph, cutoff=nil) click to toggle source

Finds shortest weighted path length between all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Array<Object, Hash{ Object => Numeric }>] path lengths between all nodes

# File lib/networkx/shortest_path/weighted.rb, line 196
def self.all_pairs_dijkstra_path_length(graph, cutoff=nil)
  path_lengths = []
  graph.nodes.each_key { |n| path_lengths << [n, singlesource_dijkstra_path_length(graph, n, cutoff)] }
  path_lengths
end
all_pairs_shortest_path(graph, cutoff=nil) click to toggle source

Computes shortest paths to all nodes from all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for the shortest path algorithm

@return [Array<Object, Hash {Object => Array<Object> }>] paths for all nodes from all nodes

# File lib/networkx/shortest_path/unweighted.rb, line 96
def self.all_pairs_shortest_path(graph, cutoff=nil)
  shortest_paths = []
  graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path(graph, n, cutoff)] }
  shortest_paths
end
all_pairs_shortest_path_length(graph, cutoff=nil) click to toggle source

Computes shortest path values to all nodes from all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for the shortest path algorithm

@return [Array<Object, Array<Object, Numeric>>] path lengths for all nodes from all nodes

# File lib/networkx/shortest_path/unweighted.rb, line 47
def self.all_pairs_shortest_path_length(graph, cutoff=nil)
  shortest_paths = []
  graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path_length(graph, n, cutoff)] }
  shortest_paths
end
allpairs_bellmanford_path(graph, cutoff=nil) click to toggle source

Shortest paths between all nodes using Bellman Ford algorithm

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for Bellman Ford algorithm

@return [Array<Object, Hash{ Object => Array<Object> }>] path lengths from source to all nodes

# File lib/networkx/shortest_path/weighted.rb, line 361
def self.allpairs_bellmanford_path(graph, cutoff=nil)
  paths = []
  graph.nodes.each_key { |n| paths << [n, singlesource_bellmanford_path(graph, n, cutoff)] }
  paths
end
allpairs_bellmanford_path_length(graph, cutoff=nil) click to toggle source

Shortest path lengths between all nodes using Bellman Ford algorithm

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param cutoff [Numeric, nil] cutoff for Bellman Ford algorithm

@return [Array<Object, Hash{ Object => Numeric }>] path lengths from source to all nodes

# File lib/networkx/shortest_path/weighted.rb, line 349
def self.allpairs_bellmanford_path_length(graph, cutoff=nil)
  path_lengths = []
  graph.nodes.each_key { |n| path_lengths << [n, singlesource_bellmanford_path_length(graph, n, cutoff)] }
  path_lengths
end
ancestors(graph, source) click to toggle source

Returns the ancestors of a given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to find ancestors of

@return [Array<Object>] Array of the ancestors

# File lib/networkx/auxillary_functions/dag.rb, line 20
def self.ancestors(graph, source)
  raise ArgumentError, 'Source is not present in the graph!' unless graph.node?(source)
  anc = single_source_shortest_path_length(graph.reverse, source).map { |u, _| u }.uniq
  anc - [source]
end
arbitrary_element(iterable) click to toggle source

Helper function to return an arbitrary element from an iterable object

# File lib/networkx/flow/preflowpush.rb, line 5
def self.arbitrary_element(iterable)
  iterable.each { |u| return u }
end
astar_path(graph, source, target, heuristic=nil) click to toggle source

Returns path using astar algorithm between source and target

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] a node to start astar from @param target [Object] a node to end astar @param heuristic [] a lambda to compute heuristic b/w two nodes

@return [Array<Object>] an array of nodes forming a path between source

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

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

    next if explored.key?(curnode)

    explored[curnode] = parent

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

Returns astar path length b/w source and target

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] a node to start astar from @param target [Object] a node to end astar @param heuristic [] a lambda to compute heuristic b/w two nodes

@return [Numeric] the length of the path

# File lib/networkx/shortest_path/astar.rb, line 64
def self.astar_path_length(graph, source, target, heuristic=nil)
  raise ArgumentError, 'Either source or target is not in graph' unless graph.node?(source) && graph.node?(target)
  path = astar_path(graph, source, target, heuristic)
  path_length = 0
  (1..(path.length - 1)).each { |i| path_length += (graph.adj[path[i - 1]][path[i]][:weight] || 1) }
  path_length
end
augment(residual, inf, path) click to toggle source

Helper function to augment the flow in a residual graph

# File lib/networkx/flow/edmondskarp.rb, line 5
def self.augment(residual, inf, path)
  flow = inf
  path_first_elem = path.shift
  u = path_first_elem
  path.each do |v|
    flow = [flow, residual.adj[u][v][:capacity] - residual.adj[u][v][:flow]].min
    u = v
  end
  raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf
  u = path_first_elem
  path.each do |v|
    residual.adj[u][v][:flow] += flow
    residual.adj[v][u][:flow] -= flow
    u = v
  end
  flow
end
authority_matrix(graph) click to toggle source

Computes authority matrix for the graph

@param graph [Graph, DiGraph] a graph

@return [NMatrix] authority matrix for the graph

# File lib/networkx/link_analysis/hits.rb, line 45
def self.authority_matrix(graph)
  matrix, = to_matrix(graph, 0)
  matrix.transpose.dot matrix
end
bellmanford_path(graph, source, target) click to toggle source

Shortest path from source to target using Bellman Ford algorithm

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object] target

@return [Array<Object>] path from source to target

# File lib/networkx/shortest_path/weighted.rb, line 314
def self.bellmanford_path(graph, source, target)
  _, path = singlesource_bellmanford(graph, source, target)
  path
end
bellmanford_path_length(graph, source, target) click to toggle source

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object] target

@return [Numeric] distance between source and target

# File lib/networkx/shortest_path/weighted.rb, line 299
def self.bellmanford_path_length(graph, source, target)
  return 0 if source == target
  weight = get_weight(graph)
  length = help_bellman_ford(graph, [source], weight, nil, nil, nil, nil, target=target)
  raise ArgumentError, 'Node not reachable!' unless length.key?(target)
  length[target]
end
bellmanford_predecesor_distance(graph, source, target=nil, cutoff=nil) click to toggle source

Finds shortest weighted path lengths and predecessors on shortest paths

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object, nil] target @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>] predecessors and distances

# File lib/networkx/shortest_path/weighted.rb, line 271
def self.bellmanford_predecesor_distance(graph, source, target=nil, cutoff=nil)
  raise ArgumentError, 'Node not found!' unless graph.node?(source)
  weight = get_weight(graph)
  # TODO: Detection of selfloop edges
  dist = {source => 0}
  pred = {source => []}
  return [pred, dist] if graph.nodes.length == 1
  dist = help_bellman_ford(graph, [source], weight, pred, nil, dist, cutoff, target)
  [pred, dist]
end
bfs_edges(graph, source) click to toggle source

Returns edges of the graph travelled in breadth first fashion

@example

NetworkX.bfs_edges(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start bfs from

# File lib/networkx/traversals/bfs.rb, line 11
def self.bfs_edges(graph, source)
  raise KeyError, "There exists no node names #{source} in the given graph." unless graph.node?(source)
  bfs_edges = []
  visited = [source]
  queue = Queue.new.push([source, graph.neighbours(source)])
  until queue.empty?
    parent, children = queue.pop
    children.each_key do |child|
      next if visited.include?(child)
      bfs_edges << [parent, child]
      visited << child
      queue.push([child, graph.neighbours(child)])
    end
  end
  bfs_edges
end
bfs_predecessors(graph, source) click to toggle source

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

@example

NetworkX.bfs_predecessors(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start bfs from

# 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) click to toggle source

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

@example

NetworkX.bfs_successors(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start bfs from

# 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) click to toggle source

Helper function for the bidirectional bfs

# File lib/networkx/flow/edmondskarp.rb, line 26
def self.bidirectional_bfs(residual, source, target)
  pred, succ = {source => nil}, {target => nil}
  q_s, q_t = [source], [target]
  loop do
    q = []
    if q_s.length <= q_t.length
      q_s.each do |u|
        residual.adj[u].each do |v, uv_attrs|
          next unless !pred.include?(v) && (uv_attrs[:flow] < uv_attrs[:capacity])
          pred[v] = u
          return [v, pred, succ] if succ.key?(v)
          q << v
        end
      end
      return [nil, nil, nil] if q.empty?
    else
      q_t.each do |u|
        residual.pred[u].each do |v, uv_attrs|
          next unless !succ.key?(v) && uv_attrs[:flow] < uv_attrs[:capacity]
          succ[v] = u
          return [v, pred, succ] if pred.key?(v)
          q << v
        end
      end
      return [nil, nil, nil] if q.empty?
      q_t = q
    end
  end
end
build_flow_dict(graph, residual) click to toggle source

Build flow dictionary of a graph from its residual graph

@param graph [DiGraph] a graph @param residual [DiGraph] residual graph

@return [Hash{ Object => Hash{ Object => Numeric }] flowdict containing all

the flow values in the edges
# File lib/networkx/flow/utils.rb, line 151
def self.build_flow_dict(graph, residual)
  flow_dict = {}
  graph.edges.each do |u, u_edges|
    flow_dict[u] = {}
    u_edges.each_key { |v| flow_dict[u][v] = 0 }
    u_edges.each_key { |v| flow_dict[u][v] = residual[u][v][:flow] if residual[u][v][:flow] > 0 }
  end
  flow_dict
end
build_residual_network(graph) click to toggle source

Builds a residual graph from a constituent graph

@param graph [DiGraph] a graph

@return [DiGraph] residual graph

# File lib/networkx/flow/utils.rb, line 63
def self.build_residual_network(graph)
  raise NotImplementedError, 'MultiGraph and MultiDiGraph not supported!' if graph.multigraph?

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

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

      let(:graph) { described_class.new }

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

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

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

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

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

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

Computes max flow using capacity scaling algorithm

@param graph [DiGraph, MultiDiGraph] a graph

@return [Array<Numeric, Hash{ Object => Hash{ Object => Numeric } }>]

flow cost and flowdict containing all the flow values in the edges
# File lib/networkx/flow/capacityscaling.rb, line 139
def self.capacity_scaling(graph)
  residual = _build_residual_network(graph)
  inf = Float::INFINITY
  flow_cost = 0

  # TODO: Account cost of self-loof edges

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

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

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

    s_set = Set.new
    t_set = Set.new

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

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

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

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

  residual.nodes.each_key do |node|
    residual.adj[node].each_value do |uv_edges|
      uv_edges.each_value do |k_attrs|
        flow = k_attrs[:flow]
        flow_cost += (flow * k_attrs[:weight])
      end
    end
  end
  [flow_cost, _build_flow_dict(graph, residual)]
end
cartesian_product(g_1, g_2) click to toggle source

Returns the cartesian product of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the cartesian product of the two graphs

# File lib/networkx/operators/product.rb, line 133
def self.cartesian_product(g_1, g_2)
  g = init_product_graph(g_1, g_2)
  g.add_nodes(node_product(g_1, g_2))
  g.add_edges(edges_cross_nodes(g_1, g_2))
  g.add_edges(nodes_cross_edges(g_1, g_2))
  g
end
closeness_vitality(graph, node) click to toggle source

Returns the closeness vitality of a node

@param graph [Graph, DiGraph] a graph @param node [Object] node to compute closeness vitality of

@return [Numeric] closeness vitality of the given node

# File lib/networkx/auxillary_functions/vitality.rb, line 8
def self.closeness_vitality(graph, node)
  before = wiener_index(graph)
  after = wiener_index(graph.subgraph(graph.nodes.keys - [node]))
  before - after
end
complement(graph) click to toggle source

Performs the complement operation on the graph

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the complement of the graph

# File lib/networkx/operators/unary.rb, line 7
def self.complement(graph)
  result = Marshal.load(Marshal.dump(graph))
  result.clear

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

Performs the composition of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the composition of the two graphs

# File lib/networkx/operators/binary.rb, line 173
def self.compose(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

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

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

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

Performs the composition of many graphs

@param [Array<Graph>, Array<DiGraph>, Array<MultiGraph>, Array<MultiDiGraph>] Array of graphs

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] composition of all the graphs

# File lib/networkx/operators/all.rb, line 52
def self.compose_all(graphs)
  raise ArgumentError, 'Argument array is empty' if graphs.empty?
  result = graphs.shift

  graphs.each do |graph|
    result = NetworkX.compose(result, graph)
  end
  result
end
convert_to_distinct_labels(graph, starting_int=-1) click to toggle source

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

# File lib/networkx/operators/binary.rb, line 19
def self.convert_to_distinct_labels(graph, starting_int=-1)
  new_graph = Marshal.load(Marshal.dump(graph))
  new_graph.clear

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

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

  graph.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if graph.multigraph?
        uv_attrs.each do |_k, attrs|
          new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, attrs)
        end
      else
        new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, uv_attrs)
      end
    end
  end
  new_graph
end
count() click to toggle source
# File lib/networkx/flow/capacityscaling.rb, line 126
def self.count
  @itr += 1
  @itr
end
cycle_basis(graph, root=nil) click to toggle source

Returns all basis cycles in graph

@param graph [Graph] a graph @param root [Object, Nil] root for the graph cycles

@return [Array<Array<Object>>] Arrays of nodes in the cycles

# File lib/networkx/auxillary_functions/cycles.rb, line 10
def self.cycle_basis(graph, root=nil)
  gnodes = graph.nodes.keys
  cycles = []
  until gnodes.empty?
    root = gnodes.shift if root.nil?
    stack = [root]
    pred = {root => root}
    used = {root => []}
    until stack.empty?
      z = stack.shift
      zused = used[z]
      graph.adj[z].each_key do |u|
        if !used.key?(u)
          pred[u] = z
          stack << u
          used[u] = [z]
        elsif u == z
          cycles << [z]
        elsif !zused.include?(u)
          pn = used[u]
          cycle = [u, z]
          p = pred[z]
          until pn.include?(p)
            cycle << p
            p = pred[p]
          end
          cycle << p
          cycles << cycle
          used[u] << z
          used[u] = used[u].uniq
        end
      end
    end
    gnodes -= pred.keys
    root = nil
  end
  cycles
end
descendants(graph, source) click to toggle source

Returns the descendants of a given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to find descendents of

@return [Array<Object>] Array of the descendants

# 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) click to toggle source

Detects unboundedness in a graph, raises exception when

infinite capacity flow is found

@param r_network [DiGraph] a residual graph @param source [Object] source node @param target [Object] target node

# File lib/networkx/flow/utils.rb, line 129
def self.detect_unboundedness(r_network, source, target)
  q = [source]
  seen = Set.new([source])
  inf = r_network.graph[:inf]
  until q.empty?
    u = q.shift
    r_network.adj[u].each do |v, uv_attrs|
      next unless uv_attrs[:capacity] == inf && !seen.include?(v)
      raise ArgumentError, 'Infinite capacity flow!' if v == target
      seen << v
      q << v
    end
  end
end
dfs_edges(graph, source, depth_limit=nil) click to toggle source

Returns edges of the graph travelled in depth first fashion

@example

NetworkX.dfs_edges(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start dfs from @param depth_limit [Integer, nil] the depth limit of dfs

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

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

@example

NetworkX.dfs_predecessors(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start dfs from @param depth_limit [Integer, nil] the depth limit of dfs

# 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) click to toggle source

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

@example

NetworkX.dfs_successors(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start dfs from @param depth_limit [Integer, nil] the depth limit of dfs

# 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) click to toggle source

Returns dfs tree of the graph

@example

NetworkX.dfs_tree(graph, source)

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start dfs from @param depth_limit [Integer, nil] the depth limit of dfs

# 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) click to toggle source

Returns the diameter of a graph

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [Numeric] diameter of the graph

# File lib/networkx/auxillary_functions/eccentricity.rb, line 24
def self.diameter(graph)
  eccentricity(graph).values.max
end
difference(g_1, g_2) click to toggle source

Performs the difference of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the difference of the two graphs

# File lib/networkx/operators/binary.rb, line 99
def self.difference(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

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

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

  g_1.adj.each do |u, u_edges|
    u_edges.each do |v, uv_attrs|
      if g_1.multigraph?
        uv_attrs.each do |k, attrs|
          result.add_edge(u, v, attrs) unless g_2.edge?(u, v, k)
        end
      else
        result.add_edge(u, v, uv_attrs) unless g_2.edge?(u, v)
      end
    end
  end
  result
end
dijkstra_path(graph, source, target) click to toggle source

Computes shortest path to target from the given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object] target

@return [Numeric] path for target node from given node

# File lib/networkx/shortest_path/weighted.rb, line 158
def self.dijkstra_path(graph, source, target)
  _, path = singlesource_dijkstra(graph, source, target)
  path
end
dijkstra_path_length(graph, source, target) click to toggle source

Computes shortest path length to target from the given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object] target

@return [Numeric] path length for target node from given node

# File lib/networkx/shortest_path/weighted.rb, line 143
def self.dijkstra_path_length(graph, source, target)
  return 0 if source == target
  weight = get_weight(graph)
  length = help_dijkstra(graph, source, weight, nil, nil, nil, target)
  raise KeyError, 'Node not reachable!' unless length.key?(target)
  length[target]
end
dijkstra_predecessor_distance(graph, source, cutoff=nil) click to toggle source

Computes weighted shortest path length and predecessors

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [<Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>]

predcessor hash and distance hash
# File lib/networkx/shortest_path/weighted.rb, line 171
def self.dijkstra_predecessor_distance(graph, source, cutoff=nil)
  weight = get_weight(graph)
  pred = {source => []}
  [pred, help_dijkstra(graph, source, weight, pred, nil, cutoff)]
end
directed_edges_cross_edges(g_1, g_2) click to toggle source

Returns the product of directed edges with edges

# File lib/networkx/operators/product.rb, line 44
def self.directed_edges_cross_edges(g_1, g_2)
  result = []
  edges_in_array(g_1).each do |u, v, c|
    edges_in_array(g_2) do |x, y, d|
      result << [[u, x], [v, y], hash_product(c, d)]
    end
  end
  result
end
discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target) click to toggle source

Helper function for discharging a node

# File lib/networkx/flow/preflowpush.rb, line 133
def self.discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target)
  height_val = residual_nodes[u_node][:height]
  curr_edge = residual_nodes[u_node][:curr_edge]
  next_height = height_val
  levels[height_val].active.delete(u_node)

  loop do
    v, attr = curr_edge.get
    if height_val == residual_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity]
      flow = [residual_nodes[u_node][:excess], attr[:capacity] - attr[:flow]].min
      push(u_node, v, flow, residual_nodes, residual_adj)
      activate(v, source, target, levels, residual_nodes)
      if residual_nodes[u_node][:excess].zero?
        levels[height_val].inactive.add(u_node)
        break
      end
    end
    begin
      curr_edge.move_to_next
    rescue StopIteration
      height_val = relabel(u_node, grt, residual_adj, residual_nodes, source, target, levels)
      if is_phase_1 && height_val >= n - 1
        levels[height].active.add(u_node)
        break
      end
      next_height = height_val
    end
  end
  residual_nodes[u_node][:height] = height_val
  next_height
end
disjoint_union(g_1, g_2) click to toggle source

Performs the disjoint union of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the disjoint union of the two graphs

# File lib/networkx/operators/binary.rb, line 236
def self.disjoint_union(g_1, g_2)
  new_g_1 = convert_to_distinct_labels(g_1)
  new_g_2 = convert_to_distinct_labels(g_2)
  result = union(new_g_1, new_g_2)
  result.graph.merge!(g_1.graph)
  result.graph.merge!(g_2.graph)
  result
end
disjoint_union_all(graphs) click to toggle source

Performs the disjoint union of many graphs

@param [Array<Graph>, Array<DiGraph>, Array<MultiGraph>, Array<MultiDiGraph>] Array of graphs

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] disjoint union of all the graphs

# File lib/networkx/operators/all.rb, line 22
def self.disjoint_union_all(graphs)
  raise ArgumentError, 'Argument array is empty' if graphs.empty?
  result = graphs.shift

  graphs.each do |graph|
    result = NetworkX.disjoint_union(result, graph)
  end
  result
end
dist_path_lambda(_graph, _new_weight) click to toggle source

Helper function to get distances

# File lib/networkx/shortest_path/weighted.rb, line 373
def self.dist_path_lambda(_graph, _new_weight)
  lambda do |graph, v, new_weight|
    paths = {v => [v]}
    _ = help_dijkstra(graph, v, new_weight, nil, paths)
    paths
  end
end
eccentricity(graph, node=nil) click to toggle source

Returns the eccentricity of a particular node or all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param node [Object] node to find the eccentricity of

@return [Array<Numeric>, Numeric] eccentricity/eccentricites of all nodes

# File lib/networkx/auxillary_functions/eccentricity.rb, line 8
def self.eccentricity(graph, node=nil)
  e = {}
  graph.nodes.each do |u, _|
    length = single_source_shortest_path_length(graph, u)
    l = length.length
    raise ArgumentError, 'Found infinite path length!' unless l == graph.nodes.length
    e[u] = length.max_by { |a| a[1] }[1]
  end
  node.nil? ? e : e[node]
end
edge_dfs(graph, start, orientation=nil) click to toggle source

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

@example

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] node to start dfs from @param orientation [:ignore, :reverse', nil] the orientation of edges of graph

# File lib/networkx/traversals/edge_dfs.rb, line 54
def self.edge_dfs(graph, start, orientation=nil)
  case orientation
  when :reverse
    graph = graph.reverse if graph.class.name == 'NetworkX::DiGraph' || graph.class.name == 'NetworkX::MultiDiGraph'
  when :ignore
    graph = graph.to_undirected if graph.class.name == 'NetworkX::DiGraph'
    graph = graph.to_multigraph if graph.class.name == 'NetworkX::MultiDiGraph'
  end

  visited_edges = []
  visited_nodes = []
  stack = [start]
  current_edges = {}

  e = Enumerator.new do |yield_var|
    until stack.empty?
      current = stack.last
      unless visited_nodes.include?(current)
        current_edges[current] = out_edges(graph, current)
        visited_nodes << current
      end

      edge = current_edges[current].shift
      if edge.nil?
        stack.pop
      else
        unless visited_edges.include?(edge_id(graph, edge))
          visited_edges << edge_id(graph, edge)
          stack << edge[1]
          yield_var.yield edge
        end
      end
    end
  end
  e.take(graph.number_of_edges)
end
edge_id(graph, edge) click to toggle source

Helper function of edge_dfs

# File lib/networkx/traversals/edge_dfs.rb, line 33
def self.edge_id(graph, edge)
  return edge if graph.directed?
  return Set.new([edge, (edge[0..1].reverse + edge[2])]) if graph.multigraph?
  Set.new([edge, edge.reverse])
end
edges_cross_nodes(g_1, g_2) click to toggle source

Returns the product of edges with edges

# File lib/networkx/operators/product.rb, line 66
def self.edges_cross_nodes(g_1, g_2)
  result = []
  edges_in_array(g_1).each do |u, v, d|
    g_2.nodes.keys.each do |x|
      result << [[u, x], [v, x], d]
    end
  end
  result
end
edges_cross_nodes_and_nodes(g_1, g_2) click to toggle source

Returns the product of edges with pairs of nodes

# File lib/networkx/operators/product.rb, line 88
def self.edges_cross_nodes_and_nodes(g_1, g_2)
  result = []
  edges_in_array(g_1).each do |u, v, d|
    g_2.nodes.keys.each do |x|
      g_2.nodes.keys.each do |y|
        result << [[u, x], [v, y], d]
      end
    end
  end
  result
end
edges_in_array(graph) click to toggle source

Returns the edges of the graph in an array

# File lib/networkx/operators/product.rb, line 7
def self.edges_in_array(graph)
  edge_array = []
  if graph.multigraph?
    graph.adj.each do |u, u_edges|
      u_edges.each do |v, uv_edges|
        uv_edges.each do |_k, attrs|
          edge_array << [u, v, attrs]
        end
      end
    end
  else
    graph.adj.each do |u, u_edges|
      u_edges.each do |v, attrs|
        edge_array << [u, v, attrs]
      end
    end
  end
  edge_array
end
edmondskarp(graph, source, target, residual=nil, cutoff=nil) click to toggle source

Computes max flow using edmonds karp algorithm

@param graph [Graph, DiGraph] a graph @param source [Object] source node @param target [Object] target node @param residual [DiGraph, nil] residual graph @param cutoff [Numeric] cutoff for the algorithm

@return [DiGraph] a residual graph containing the flow values

# File lib/networkx/flow/edmondskarp.rb, line 110
def self.edmondskarp(graph, source, target, residual=nil, cutoff=nil)
  edmondskarp_impl(graph, source, target, residual, cutoff)
end
edmondskarp_core(residual, source, target, cutoff) click to toggle source

Core helper function for the EdmondsKarp algorithm

# File lib/networkx/flow/edmondskarp.rb, line 59
def self.edmondskarp_core(residual, source, target, cutoff)
  inf = residual.graph[:inf]
  flow_val = 0
  while flow_val < cutoff
    v, pred, succ = bidirectional_bfs(residual, source, target)
    break if pred.nil?
    path = [v]
    u = v
    while u != source
      u = pred[u]
      path << u
    end
    path.reverse!
    u = v
    while u != target
      u = succ[u]
      path << u
    end
    flow_val += augment(residual, inf, path)
  end
  flow_val
end
edmondskarp_impl(graph, source, target, residual, cutoff) click to toggle source

Helper function for the edmondskarp function

# File lib/networkx/flow/edmondskarp.rb, line 85
def self.edmondskarp_impl(graph, source, target, residual, cutoff)
  raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source)
  raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target)
  raise ArgumentError, 'Source and target are same node!' if source == target
  res_graph = residual.nil? ? build_residual_network(graph) : residual.clone
  res_graph.adj.each do |u, u_edges|
    u_edges.each do |v, _attrs|
      res_graph.adj[u][v][:flow] = 0
      res_graph.pred[v][u][:flow] = 0
    end
  end
  cutoff = Float::INFINITY if cutoff.nil?
  res_graph.graph[:flow_val] = edmondskarp_core(res_graph, source, target, cutoff)
  res_graph
end
find_cliques(graph) click to toggle source

Returns all cliques in the graph

@param graph [Graph, MultiGraph] a graph

@return [Array<Array<Object>>] Arrays of nodes in the cliques

# File lib/networkx/auxillary_functions/cliques.rb, line 9
def self.find_cliques(graph)
  return nil if graph.nodes.empty?
  q = [nil]
  adj = {}
  graph.nodes.each_key { |u| adj[u] = [] }
  graph.adj.each { |u, u_edges| u_edges.each_key { |v| adj[u] << v if u != v } }

  subg = graph.nodes.keys
  cand = graph.nodes.keys
  u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length }
  ext_u = cand - adj[u]
  stack = []
  cliques = []
  begin
    loop do
      if !ext_u.empty?
        q_elem = ext_u.pop
        cand.delete(q_elem)
        q[-1] = q_elem
        adj_q = adj[q_elem]
        subg_q = subg & adj_q
        if subg_q.empty?
          cliques << q[0..(q.length - 1)]
        else
          cand_q = cand & adj_q
          unless cand_q.empty?
            stack << [subg, cand, ext_u]
            q << nil
            subg = subg_q
            cand = cand_q
            u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length }
            ext_u = cand - adj[u]
          end
        end
      else
        q.pop
        subg, cand, ext_u = stack.pop
      end
    end
  rescue NoMethodError
    return cliques
  end
end
find_cycle(graph, node) click to toggle source

Returns the cycle containing the given node

@param graph [Graph, DiGraph] a graph @param node [Object] node to be included in the cycle

@return [Array<Array<Object>>] Arrays of nodes in the cycle

# File lib/networkx/auxillary_functions/cycles.rb, line 57
def self.find_cycle(graph, node)
  explored = Set.new
  cycle = []
  final_node = nil
  unless explored.include?(node)
    edges = []
    seen = [node]
    active_nodes = [node]
    previous_head = nil

    edge_dfs(graph, node).each do |edge|
      tail, head = edge
      next if explored.include?(head)
      if !previous_head.nil? && tail != previous_head
        loop do
          popped_edge = edges.pop
          if popped_edge.nil?
            edges = []
            active_nodes = [tail]
            break
          else
            popped_head = popped_edge[1]
            active_nodes.delete!(popped_head)
          end

          unless edges.empty?
            last_head = edges[-1][1]
            break if tail == last_head
          end
        end
      end
      edges << edge

      if active_nodes.include?(head)
        cycle += edges
        final_node = head
        break
      else
        seen << head
        active_nodes << head
        previous_head = head
      end
    end
    cycle.each_with_index { |edge, i| return cycle[i..(cycle.length - 1)] if final_node == edge[0] }
  end
  raise ArgumentError, 'No cycle found!' if cycle.empty?
end
floyd_warshall(graph) click to toggle source

Returns the all pair distance between all the nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [Hash{ Object => { Object => { Numeric }}}] a hash containing distances

b/w all pairs of nodes
# File lib/networkx/shortest_path/dense.rb, line 10
def self.floyd_warshall(graph)
  a, index = to_matrix(graph, Float::INFINITY, 'min')
  nodelen = graph.nodes.length
  (0..(nodelen - 1)).each { |i| a[i, i] = 0 }
  (0..(nodelen - 1)).each do |k|
    (0..(nodelen - 1)).each do |i|
      (0..(nodelen - 1)).each do |j|
        a[i, j] = [a[i, j], a[i, k] + a[k, j]].min
      end
    end
  end

  as_hash = {}
  (0..(nodelen - 1)).each do |i|
    (0..(nodelen - 1)).each do |j|
      as_hash[index[i]] = {} unless as_hash.key?(index[i])
      as_hash[index[i]][index[j]] = a[i, j]
    end
  end
  as_hash
end
gap_heuristic(height, levels, residual_nodes) click to toggle source

Helper function for applying gap heuristic

# 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() click to toggle source

Returns a label for unique node

# File lib/networkx/flow/capacityscaling.rb, line 5
def self.generate_unique_node
  SecureRandom.uuid
end
get_edges(graph) click to toggle source

Returns the edges of the graph in an array

# File lib/networkx/operators/binary.rb, line 5
def self.get_edges(graph)
  edges = []
  graph.adj.each do |u, u_attrs|
    u_attrs.each do |v, uv_attrs|
      edges << [u, v, uv_attrs]
    end
  end
  edges
end
get_edges_weights(graph) click to toggle source

Helper function for the minimum spanning tree

# 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) click to toggle source

Helper function to get sources

# File lib/networkx/shortest_path/weighted.rb, line 368
def self.get_sources(graph)
  graph.nodes.collect { |k, _v| k }
end
get_weight(graph) click to toggle source

Helper function to extract weight from a adjecency hash

# File lib/networkx/shortest_path/weighted.rb, line 5
def self.get_weight(graph)
  weight_get = lambda do |_, _, attrs|
    return attrs[:weight] || 1 unless graph.multigraph?
    attrs.group_by { |_k, vals| vals[:weight] || 1 }.keys.max
  end
  weight_get
end
global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred) click to toggle source

Helper function for global relabel heuristic

# File lib/networkx/flow/preflowpush.rb, line 183
def self.global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred)
  src = from_sink ? target : source
  heights = reverse_bfs(src, residual_pred)
  heights.delete(target) unless from_sink
  max_height = heights.values.max
  if from_sink
    residual_nodes.each { |u, attr| heights[u] = num + 1 if !heights.key?(u) && attr[:height] < num }
  else
    heights.each_key { |u| heights[u] += num }
    max_height += num
  end
  heights.delete(src)
  heights.each do |u, new_height|
    old_height = residual_nodes[u][:height]
    next unless new_height != old_height
    if levels[old_height].active.include?(u)
      levels[old_height].active.delete(u)
      levels[new_height].active.add(u)
    else
      levels[old_height].inactive.delete(u)
      levels[new_height].inactive.add(u)
    end
    residual_nodes[u][:height] = new_height
  end
  max_height
end
graph_to_csv(graph, filename='graph.csv') click to toggle source

Saves the graph in a csv file

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param filename [String] filename of the graph

# File lib/networkx/converters/to_csv.rb, line 8
def self.graph_to_csv(graph, filename='graph.csv')
  CSV.open(filename, 'wb') do |csv|
    csv << [graph.class.name]
    csv << ['graph_values']
    csv << graph.graph.keys
    csv << graph.graph.values
    csv << ['graph_nodes']
    graph.nodes.each do |u, attrs|
      node_attrs = [u]
      attrs.each do |k, v|
        node_attrs << k
        node_attrs << v
      end
      csv << node_attrs
    end
    csv << ['graph_edges']
    graph.adj.each do |u, u_edges|
      u_edges.each do |v, uv_attrs|
        if graph.multigraph?
          uv_attrs.each do |key, attrs|
            node_attrs = [u, v, key]
            attrs.each do |k, k_attrs|
              node_attrs << k
              node_attrs << k_attrs
            end
            csv << node_attrs
          end
        else
          node_attrs = [u, v]
          uv_attrs.each do |k, vals|
            node_attrs << k
            node_attrs << vals
          end
          csv << node_attrs
        end
      end
    end
  end
end
graph_to_json(graph) click to toggle source

Returns a JSON object of the given graph

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [JSON] json encoded graph

# File lib/networkx/converters/to_json.rb, line 7
def self.graph_to_json(graph)
  json_hash = {}
  json_hash[:class] = graph.class.name
  json_hash[:graph] = graph.graph
  json_hash[:nodes] = graph.nodes
  json_hash[:adj] = graph.adj
  json_hash.to_json
end
hash_product(hash_1, hash_2) click to toggle source

Returns the hash product of two hashes

# File lib/networkx/operators/product.rb, line 28
def self.hash_product(hash_1, hash_2)
  Hash[(hash_1.keys | hash_2.keys).map { |n| [n, [hash_1[n], hash_2[n]]] }]
end
help_bellman_ford(graph, sources, weight, pred=nil, paths=nil, dist=nil, cutoff=nil, target=nil) click to toggle source

Helper function for bellman ford

# File lib/networkx/shortest_path/weighted.rb, line 217
def self.help_bellman_ford(graph, sources, weight, pred=nil, paths=nil, dist=nil, cutoff=nil, target=nil)
  pred = sources.product([[]]).to_h if pred.nil?
  dist = sources.product([0]).to_h if dist.nil?

  inf, n, count, q, in_q = Float::INFINITY, graph.nodes.length, {}, sources.clone, Set.new(sources)
  until q.empty?
    u = q.shift
    in_q.delete(u)
    skip = false
    pred[u].each { |k| skip = true if in_q.include?(k) }
    next if skip
    dist_u = dist[u]
    graph.adj[u].each do |v, e|
      dist_v = dist_u + weight.call(u, v, e)
      next if !cutoff.nil? && dist_v > cutoff
      next if !target.nil? && dist_v > (dist[target] || inf)
      if dist_v < (dist[v] || inf)
        unless in_q.include?(v)
          q << v
          in_q.add(v)
          count_v = (count[v] || 0) + 1
          raise ArgumentError, 'Negative edge cycle detected!' if count_v == n
          count[v] = count_v
        end
        dist[v] = dist_v
        pred[v] = [u]
      elsif dist.key?(v) && dist_v == dist[v]
        pred[v] << u
      end
    end
  end
  unless paths.nil?
    dsts = target.nil? ? pred : [target]
    dsts.each_key do |dst|
      path, cur = [dst], dst
      until pred[cur][0].nil?
        cur = pred[cur][0]
        path << cur
      end
      path.reverse
      paths[dst] = path
    end
  end
  dist
end
help_dijkstra(graph, source, weight, pred=nil, paths=nil, cutoff=nil, target=nil) click to toggle source

Helper function for single source dijkstra

# 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) click to toggle source

Helper function for multisource dijkstra

# File lib/networkx/shortest_path/weighted.rb, line 16
def self.help_multisource_dijkstra(graph, sources, weight, pred=nil, paths=nil, cutoff=nil, target=nil)
  count = ->(i) { i + 1 }
  i = -1
  dist = {}
  seen = {}
  fringe = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) }
  sources.each do |s|
    seen[s] = 0
    fringe << [0, count.call(i), s]
  end

  until fringe.empty?
    d, _, v = fringe.pop
    next if dist.key?(v)
    dist[v] = d
    break if v == target
    graph.adj[v].each do |u, attrs|
      cost = weight.call(v, u, attrs)
      next if cost.nil?
      vu_dist = dist[v] + cost
      next if !cutoff.nil? && vu_dist > cutoff
      if dist.key?(u)
        raise ValueError, 'Contradictory weights found!' if vu_dist < dist[u]
      elsif !seen.key?(u) || vu_dist < seen[u]
        seen[u] = vu_dist
        fringe << [vu_dist, count.call(i), u]
        paths[u] = paths[v] + [u] unless paths.nil?
        pred[u] = [v] unless pred.nil?
      elsif vu_dist == seen[u]
        pred[u] << v unless pred.nil?
      end
    end
  end
  dist
end
help_single_shortest_path(adj, firstlevel, paths, cutoff) click to toggle source

Helper function for finding single source shortest path

# File lib/networkx/shortest_path/unweighted.rb, line 56
def self.help_single_shortest_path(adj, firstlevel, paths, cutoff)
  level = 0
  nextlevel = firstlevel
  while !nextlevel.empty? && cutoff > level
    thislevel = nextlevel
    nextlevel = {}
    thislevel.each_key do |u|
      adj[u].each_key do |v|
        unless paths.key?(v)
          paths[v] = paths[u] + [v]
          nextlevel[v] = 1
        end
      end
    end
    level += 1
  end
  paths
end
help_single_shortest_path_length(adj, firstlevel, cutoff) click to toggle source

Helper function for single source shortest path length

# File lib/networkx/shortest_path/unweighted.rb, line 5
def self.help_single_shortest_path_length(adj, firstlevel, cutoff)
  iterator = Enumerator.new do |e|
    seen = {}
    level = 0
    nextlevel = firstlevel

    while !nextlevel.empty? && cutoff >= level
      thislevel = nextlevel
      nextlevel = {}
      thislevel.each do |u, _attrs|
        next if seen.key?(u)
        seen[u] = level
        nextlevel.merge!(adj[u])
        e.yield [u, level]
      end
      level += 1
    end
    seen.clear
  end
  iterator
end
hits(graph, max_iter=100, tol=1e-8, nstart) click to toggle source

Computes hits and authority scores for all the graphs

@param graph [Graph, DiGraph] a graph @param max_iter [Integer] max iterations to run the hits algorithm @param tol [Numeric] tolerences to cut off the loop @param nstart [Array<Numeric>] starting hub values for the nodes

@return [Array<Numeric, Numeric>] hits and authority scores

# File lib/networkx/link_analysis/hits.rb, line 12
def self.hits(graph, max_iter=100, tol=1e-8, nstart)
  return [{}, {}] if graph.nodes.empty?
  h = nstart
  sum = h.values.inject(:+)
  h.each_key { |k| h[k] /= (sum * 1.0) }
  i = 0
  a = {}

  loop do
    hlast = Marshal.load(Marshal.dump(h))
    h, a = {}, {}
    hlast.each do |k, _v|
      h[k] = 0
      a[k] = 0
    end
    h.each_key { |k| graph.adj[k].each { |nbr, attrs| a[k] += hlast[nbr] * (attrs[:weight] || 1) } }
    h.each_key { |k| graph.adj[k].each { |nbr, attrs| h[k] += a[nbr] * (attrs[:weight] || 1) } }
    smax = h.values.max
    h.each_key { |k| h[k] /= smax }
    smax = a.values.max
    a.each_key { |k| a[k] /= smax }
    break if h.keys.map { |k| (h[k] - hlast[k]).abs }.inject(:+) < tol
    raise ArgumentError, 'Power Iteration failed to converge!' if i > max_iter
    i += 1
  end
  [h, a]
end
hub_matrix(graph) click to toggle source

Computes hub matrix for the graph

@param graph [Graph, DiGraph] a graph

@return [NMatrix] hub matrix for the graph

# File lib/networkx/link_analysis/hits.rb, line 55
def self.hub_matrix(graph)
  matrix, = to_matrix(graph, 0)
  matrix.dot matrix.transpose
end
init_product_graph(g_1, g_2) click to toggle source

Initializes the product graph

# File lib/networkx/operators/product.rb, line 101
def self.init_product_graph(g_1, g_2)
  raise ArgumentError, 'Arguments must be both directed or undirected!' unless g_1.directed? == g_2.directed?

  g = if g_1.multigraph? || g_2.multigraph?
        NetworkX::MultiGraph.new
      else
        NetworkX::Graph.new
      end
  g = g.to_directed if g.directed?
  g
end
intersection(g_1, g_2) click to toggle source

Performs the intersection of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the intersection of the two graphs

# File lib/networkx/operators/binary.rb, line 54
def self.intersection(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

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

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

  if g_1.number_of_edges <= g_2.number_of_edges
    g_1.adj.each do |u, u_edges|
      u_edges.each do |v, uv_attrs|
        if g_1.multigraph?
          uv_attrs.each do |k, attrs|
            result.add_edge(u, v, attrs) if g_2.edge?(u, v, k)
          end
        elsif g_2.edge?(u, v)
          result.add_edge(u, v, uv_attrs)
        end
      end
    end
  else
    g_2.adj.each do |u, u_edges|
      u_edges.each do |v, uv_attrs|
        if g_2.multigraph?
          uv_attrs.each do |k, attrs|
            result.add_edge(u, v, attrs) if g_1.edge?(u, v, k)
          end
        elsif g_1.edge?(u, v)
          result.add_edge(u, v, uv_attrs)
        end
      end
    end
  end
  result
end
intersection_all(graphs) click to toggle source

Performs the intersection of many graphs

@param [Array<Graph>, Array<DiGraph>, Array<MultiGraph>, Array<MultiDiGraph>] Array of graphs

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] intersection of all the graphs

# File lib/networkx/operators/all.rb, line 37
def self.intersection_all(graphs)
  raise ArgumentError, 'Argument array is empty' if graphs.empty?
  result = graphs.shift

  graphs.each do |graph|
    result = NetworkX.intersection(result, graph)
  end
  result
end
johnson(graph) click to toggle source

Returns shortest path between all pairs of nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [Array<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes

# File lib/networkx/shortest_path/weighted.rb, line 395
def self.johnson(graph)
  dist, pred = {}, {}
  sources = get_sources(graph)
  graph.nodes.each_key do |n|
    dist[n], pred[n] = 0, []
  end
  weight = get_weight(graph)
  dist_bellman = help_bellman_ford(graph, sources, weight, pred, nil, dist=dist)
  new_weight = ->(u, v, d) { weight.call(u, v, d) + dist_bellman[u] - dist_bellman[v] }
  dist_path = dist_path_lambda(graph, new_weight)
  path_lengths = set_path_lengths_johnson(graph, dist_path, new_weight)
  path_lengths
end
json_to_graph(json_str) click to toggle source

Returns a graph from the json encoded graph

@param json_str [JSON] json encoded string

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] a decoded graph

# File lib/networkx/converters/to_json.rb, line 23
def self.json_to_graph(json_str)
  graph_hash = JSON.parse(json_str)
  case json_str['class']
  when 'NetworkX::Graph'
    graph = NetworkX::Graph.new(graph_hash.graph)
  when 'NetworkX::MultiGraph'
    graph = NetworkX::MultiGraph.new(graph_hash.graph)
  when 'NetworkX::DiGraph'
    graph = NetworkX::DiGraph.new(graph_hash.graph)
  when 'NetworkX::MultiDiGraph'
    graph = NetworkX::MultiDiGraph.new(graph_hash.graph)
  end
  graph.adj = graph_hash['adj']
  graph.nodes = graph_hash['nodes']
  graph
end
lexicographic_product(g_1, g_2) click to toggle source

Returns the lexicographic product of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the lexicographic product of the two graphs

# File lib/networkx/operators/product.rb, line 147
def self.lexicographic_product(g_1, g_2)
  g = init_product_graph(g_1, g_2)
  g.add_nodes(node_product(g_1, g_2))
  g.add_edges(edges_cross_nodes_and_nodes(g_1, g_2))
  g.add_edges(nodes_cross_edges(g_1, g_2))
  g
end
maximal_independent_set(graph, nodes) click to toggle source

Returns the maximal independent set of a graph

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param nodes [Object] nodes to be considered in the MIS

@return [Numeric] radius of the graph

# File lib/networkx/auxillary_functions/mis.rb, line 10
def self.maximal_independent_set(graph, nodes)
  raise 'The array containing the nodes should be a subset of the graph!' if (graph.nodes.keys - nodes).empty?
  neighbours = []
  nodes.each { |u| graph.adj[u].each { |v, _| neighbours |= [v] } }
  raise 'Nodes is not an independent set of graph!' if (neighbours - nodes).empty?
  available_nodes = graph.nodes.keys - (neighbours | nodes)
  until available_nodes.empty?
    node = available_nodes.sample
    nodes << node
    available_nodes -= (graph.adj[node].keys + [node])
  end
  nodes
end
minimum_spanning_tree(graph) click to toggle source

Returns the minimum spanning tree of a graph

@param graph [Graph, DiGraph] a graph

@return [DiGraph, Graph] a minimum spanning tree of the graph

# File lib/networkx/auxillary_functions/mst.rb, line 21
def self.minimum_spanning_tree(graph)
  mst = Marshal.load(Marshal.dump(graph))
  mst.clear
  edges = get_edges_weights(graph).sort_by { |a| a[1] }
  union_find = UnionFind.new(graph.nodes.keys)
  while edges.any? && mst.nodes.length <= graph.nodes.length
    edge = edges.shift
    unless union_find.connected?(edge[0][0], edge[0][1])
      union_find.union(edge[0][0], edge[0][1])
      mst.add_edge(edge[0][0], edge[0][1], graph.adj[edge[0][0]][edge[0][1]])
    end
  end
  mst
end
multisource_dijkstra(graph, sources, target=nil, cutoff=nil) click to toggle source

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param sources [Array<Object>] Array of sources @param target [Object, nil] target node for the dijkstra algorithm @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Numeric, Array<Object>] path lengths for all nodes

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

Computes shortest paths to any from the given nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param sources [Array<Object>] Array of sources @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Hash{ Object => Array<Object> }] paths for any nodes from given nodes

# File lib/networkx/shortest_path/weighted.rb, line 97
def self.multisource_dijkstra_path(graph, sources, cutoff=nil)
  _, path = multisource_dijkstra(graph, sources, nil, cutoff)
  path
end
multisource_dijkstra_path_length(graph, sources, cutoff=nil) click to toggle source

Computes shortest path lengths to any from the given nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param sources [Array<Object>] Array of sources @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Hash{ Object => Numeric }] path lengths for any nodes from given nodes

# File lib/networkx/shortest_path/weighted.rb, line 84
def self.multisource_dijkstra_path_length(graph, sources, cutoff=nil)
  raise ValueError, 'Sources cannot be empty' if sources.empty?
  weight = get_weight(graph)
  help_multisource_dijkstra(graph, sources, weight, nil, nil, cutoff)
end
negative_edge_cycle(graph) click to toggle source

Finds if there is a negative edge cycle in the graph

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [Boolean] whether there exists a negative cycle in graph

# File lib/networkx/flow/capacityscaling.rb, line 14
def self.negative_edge_cycle(graph)
  newnode = generate_unique_node
  graph.add_edges(graph.nodes.keys.map { |n| [newnode, n] })
  begin
    bellmanford_predecesor_distance(graph, newnode)
  rescue ArgumentError
    return true
  ensure
    graph.remove_node(newnode)
  end
  false
end
node_product(g_1, g_2) click to toggle source

Returns the node product of nodes of two graphs

# File lib/networkx/operators/product.rb, line 33
def self.node_product(g_1, g_2)
  n_product = []
  g_1.nodes.each do |k_1, attrs_1|
    g_2.nodes.each do |k_2, attrs_2|
      n_product << [[k_1, k_2], hash_product(attrs_1, attrs_2)]
    end
  end
  n_product
end
nodes_cross_edges(g_1, g_2) click to toggle source

Returns the product of directed nodes with edges

# File lib/networkx/operators/product.rb, line 77
def self.nodes_cross_edges(g_1, g_2)
  result = []
  g_1.nodes.keys.each do |x|
    edges_in_array(g_2).each do |u, v, d|
      result << [[x, u], [x, v], d]
    end
  end
  result
end
number_of_cliques(graph, node) click to toggle source

Returns the number of cliques in a graph containing a node

@param graph [Graph, MultiGraph] a graph @param node [Object] a node

@return [Numeric] Number of cliques containing the given node

# File lib/networkx/auxillary_functions/cliques.rb, line 59
def self.number_of_cliques(graph, node)
  cliques = find_cliques(graph)
  num_cliq_arr = []
  cliques.each { |c| num_cliq_arr << 1 if c.include?(node) }
  num_cliq_arr.length
end
out_edges(graph, node) click to toggle source

Helper function for edge_dfs

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param node [Object] a node in the graph

# File lib/networkx/traversals/edge_dfs.rb, line 8
def self.out_edges(graph, node)
  edges = []
  visited = {}
  case graph.class.name
  when 'NetworkX::Graph', 'NetworkX::DiGraph'
    graph.adj[node].each do |v, _|
      if graph.class.name == 'NetworkX::DiGraph' || visited[[v, node]].nil?
        visited[[node, v]] = true
        edges << [node, v]
      end
    end
  else
    graph.adj[node].each do |v, uv_keys|
      uv_keys.each_key do |k|
        if graph.class.name == 'NetworkX::MultiDiGraph' || visited[[v, node, k]].nil?
          visited[[node, v, k]] = true
          edges << [node, v, k]
        end
      end
    end
  end
  edges
end
pagerank(graph, init, alpha=0.85, eps=1e-4, max_iter=100) click to toggle source

Computes pagerank values for the graph

@param graph [Graph] a graph @param init [Array<Numeric>] initial pagerank values for the nodes @param alpha [Numeric] the alpha value to compute the pagerank @param eps [Numeric] tolerence to check for convergence @param max_iter [Integer] max iterations for the pagerank algorithm to run

@return [Array<Numeric>] pagerank values of the graph

# File lib/networkx/link_analysis/pagerank.rb, line 13
def self.pagerank(graph, init, alpha=0.85, eps=1e-4, max_iter=100)
  dim = graph.nodes.length
  raise ArgumentError, 'Init array needs to have same length as number of graph nodes!'\
                        unless dim == init.length
  matrix = []
  elem_ind = {}
  p = []
  curr = init.values
  init.keys.each_with_index { |n, i| elem_ind[n] = i }
  graph.adj.each do |_u, u_edges|
    adj_arr = Array.new(dim, 0)
    u_edges.each do |v, _|
      adj_arr[elem_ind[v]] = 1
    end
    matrix << adj_arr
  end
  (0..(dim - 1)).each do |i|
    p[i] = []
    (0..(dim - 1)).each { |j| p[i][j] = matrix[i][j] / (matrix[i].inject(:+) * 1.0) }
  end

  max_iter.times do |_|
    prev = curr.clone
    dim.times do |i|
      ip = 0
      dim.times { |j| ip += p.transpose[i][j] * prev[j] }
      curr[i] = (alpha * ip) + (1 - alpha) / (dim * 1.0)
    end
    err = 0
    dim.times { |i| err += (prev[i] - curr[i]).abs }
    return curr if err < eps
  end
  raise ArgumentError, 'PageRank failed to converge!'
end
power(graph, pow) click to toggle source

Returns the specified power of the graph

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Numeric] the power to which to raise the graph to

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the power of the graph

# File lib/networkx/operators/product.rb, line 179
def self.power(graph, pow)
  raise ArgumentError, 'Power must be a positive quantity!' if pow <= 0
  result = NetworkX::Graph.new
  result.add_nodes(graph.nodes.map { |n, attrs| [n, attrs] })
  graph.nodes.each do |n, _attrs|
    seen = {}
    level = 1
    next_level = graph.adj[n]
    until next_level.empty?
      this_level = next_level
      next_level = {}
      this_level.each do |v, _attrs|
        next if v == n
        unless seen.key?(v)
          seen[v] = level
          next_level.merge!(graph.adj[v])
        end
      end
      break if pow <= level
      level += 1
    end
    result.add_edges(seen.map { |v, _| [n, v] })
  end
  result
end
predecessor(graph, source, cutoff=nil, return_seen=false) click to toggle source

Computes shortest paths to all nodes from all nodes

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source for which predecessors are needed @param cutoff [Numeric, nil] cutoff for finding predecessor @param return_seen [Boolean] if true, returns seen dict

@return [Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>,

Hash{ Object => Array<Object> }]
predecessors of a given node and/or seen dict
# File lib/networkx/shortest_path/unweighted.rb, line 114
def self.predecessor(graph, source, cutoff=nil, return_seen=false)
  raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source)
  level = 0
  nextlevel = [source]
  seen = {source => level}
  pred = {source => []}
  until nextlevel.empty?
    level += 1
    thislevel = nextlevel
    nextlevel = []
    thislevel.each do |u|
      graph.adj[u].each_key do |v|
        if !seen.key?(v)
          pred[v] = [u]
          seen[v] = level
          nextlevel << v
        elsif seen[v] == level
          pred[v] << u
        end
      end
    end
    break if cutoff.nil? && cutoff <= level
  end
  return_seen ? [pred, seen] : pred
end
preflowpush(graph, source, target, residual=nil, globalrelabel_freq=1, value_only=false) click to toggle source

Computes max flow using preflow push algorithm

@param graph [DiGraph] a graph @param source [Object] source node @param target [Object] target node @param residual [DiGraph, nil] residual graph @param globalrelabel_freq [Numeric] global relabel freq @param value_only [Boolean] if false, compute maximum flow else

maximum preflow

@return [DiGraph] a residual graph containing the flow values

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

Helper function to apply the preflow push algorithm

# File lib/networkx/flow/preflowpush.rb, line 12
def self.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only)
  raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source)
  raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target)
  raise ArgumentError, 'Source and Target are same!' if source == target

  globalrelabel_freq = 0 if globalrelabel_freq.nil?
  raise ArgumentError, 'Global Relabel Freq must be nonnegative!' if globalrelabel_freq < 0
  r_network = residual.nil? ? build_residual_network(graph) : residual
  detect_unboundedness(r_network, source, target)

  residual_nodes = r_network.nodes
  residual_adj = r_network.adj
  residual_pred = r_network.pred

  residual_nodes.each do |u, u_attrs|
    u_attrs[:excess] = 0
    residual_adj[u].each { |_v, attrs| attrs[:flow] = 0 }
  end

  heights = reverse_bfs(target, residual_pred)

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

  n = r_network.nodes.length
  max_height = heights.map { |u, h| u == source ? -1 : h }.max
  heights[source] = n

  grt = GlobalRelabelThreshold.new(n, r_network.size, globalrelabel_freq)

  residual_nodes.each do |u, u_attrs|
    u_attrs[:height] = heights.key?(u) ? heights[u] : (n + 1)
    u_attrs[:curr_edge] = CurrentEdge.new(residual_adj[u])
  end

  residual_adj[source].each do |u, attr|
    flow = attr[:capacity]
    push(source, u, flow, residual_nodes, residual_adj) if flow > 0
  end

  levels = (0..(2 * n - 1)).map { |_| Level.new }
  residual_nodes.each do |u, attr|
    if u != source && u != target
      level = levels[attr[:height]]
      residual_nodes[u][:excess] > 0 ? level.active.add(u) : level.inactive.add(u)
    end
  end

  height = max_height
  while height > 0
    loop do
      level = levels[height]
      if level.active.empty?
        height -= 1
        break
      end
      old_height = height
      old_level = level
      u = arbitrary_element(level.active)
      height = discharge(u, true, residual_nodes, residual_adj, height, levels, grt, source, target)
      if grt.reached?
        height = global_relabel(true, source, target, residual_nodes, n, levels, residual_pred)
        max_height = height
        grt.clear_work
      elsif old_level.active.empty? && old_level.inactive.empty?
        gap_heuristic(old_height, levels, residual_nodes)
        height = old_height - 1
        max_height = height
      else
        max_height = [max_height, height].max
      end
    end
  end

  if value_only
    r_network.graph[:flow_value] = residual_nodes[target][:excess]
    return r_network
  end

  height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred)
  grt.clear_work

  while height > n
    loop do
      level = levels[height]
      if level.active.empty?
        height -= 1
        break
      end
      u = arbitrary_element(level.active)
      height = discharge(u, false, residual_nodes, residual_adj, height, levels, grt, source, target)
      if grt.reached?
        height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred)
        grt.clear_work
      end
    end
  end
  r_network.graph[:flow_value] = residual_nodes[target][:excess]
  r_network
end
push(node_1, node_2, flow, residual_nodes, residual_adj) click to toggle source

Helper function for augmenting flow

# File lib/networkx/flow/preflowpush.rb, line 211
def self.push(node_1, node_2, flow, residual_nodes, residual_adj)
  residual_adj[node_1][node_2][:flow] += flow
  residual_adj[node_2][node_1][:flow] -= flow
  residual_nodes[node_1][:excess] -= flow
  residual_nodes[node_2][:excess] += flow
end
radius(graph) click to toggle source

Returns the radius of a graph

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph

@return [Numeric] radius of the graph

# File lib/networkx/auxillary_functions/eccentricity.rb, line 33
def self.radius(graph)
  eccentricity(graph).values.min
end
relabel(u_node, grt, r_adj, _r_nodes, _source, _target, _levels) click to toggle source

Helper function to relable a node to create a permissible edge

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

Helper function for reverse bfs

# File lib/networkx/flow/preflowpush.rb, line 221
def self.reverse_bfs(src, residual_pred)
  heights = {src => 0}
  q = [[src, 0]]

  until q.empty?
    u, height = q.shift
    height += 1
    residual_pred[u].each do |v, attr|
      if !heights.key?(v) && attr[:flow] < attr[:capacity]
        heights[v] = height
        q << [v, height]
      end
    end
  end
  heights
end
set_path_lengths_johnson(graph, dist_path, new_weight) click to toggle source

Helper function to set path lengths for Johnson algorithm

# File lib/networkx/shortest_path/weighted.rb, line 382
def self.set_path_lengths_johnson(graph, dist_path, new_weight)
  path_lengths = []
  graph.nodes.each_key { |n| path_lengths << [n, dist_path.call(graph, n, new_weight)] }
  path_lengths
end
shortest_augmenting_path(graph, source, target, residual=nil, _value_only=false, two_phase=false, cutoff=nil) click to toggle source

Computes max flow using shortest augmenting path algorithm

@param graph [DiGraph] a graph @param source [Object] source node @param target [Object] target node @param residual [DiGraph, nil] residual graph @param value_only [Boolean] if true, compute only the maximum flow value @param two_phase [Boolean] if true, two phase variant is used @param cutoff [Numeric] cutoff value for the algorithm

@return [DiGraph] a residual graph containing the flow values

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

Helper function for running the shortest augmenting path algorithm

# File lib/networkx/flow/shortestaugmentingpath.rb, line 7
def self.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff)
  raise ArgumentError, 'Source is not in the graph!' unless graph.nodes.key?(source)
  raise ArgumentError, 'Target is not in the graph!' unless graph.nodes.key?(target)
  raise ArgumentError, 'Source and Target are the same!' if source == target

  residual = residual.nil? ? build_residual_network(graph) : residual
  r_nodes = residual.nodes
  r_pred = residual.pred
  r_adj = residual.adj

  r_adj.each_value do |u_edges|
    u_edges.each_value do |attrs|
      attrs[:flow] = 0
    end
  end

  heights = {target => 0}
  q = [[target, 0]]

  until q.empty?
    u, height = q.shift
    height += 1
    r_pred[u].each do |v, attrs|
      if !heights.key?(v) && attrs[:flow] < attrs[:capacity]
        heights[v] = height
        q << [v, height]
      end
    end
  end

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

  n = graph.nodes.length
  m = residual.size / 2

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

  counts = Array.new(2 * n - 1, 0)
  counts.fill(0)
  r_nodes.each_value { |attrs| counts[attrs[:height]] += 1 }
  inf = graph.graph[:inf]

  cutoff = Float::INFINITY if cutoff.nil?
  flow_value = 0
  path = [source]
  u = source
  d = two_phase ? n : [m ** 0.5, 2 * n ** (2. / 3)].min.floor
  done = r_nodes[source][:height] >= d

  until done
    height = r_nodes[u][:height]
    curr_edge = r_nodes[u][:curr_edge]

    loop do
      v, attr = curr_edge.get
      if height == r_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity]
        path << v
        u = v
        break
      end
      begin
        curr_edge.move_to_next
      rescue StopIteration
        if counts[height].zero?
          residual.graph[:flow_value] = flow_value
          return residual
        end
        height = relabel(u, n, r_adj, r_nodes)
        if u == source && height >= d
          if !two_phase
            residual.graph[:flow_value] = flow_value
            return residual
          else
            done = true
            break
          end
        end
        counts[height] += 1
        r_nodes[u][:height] = height
        unless u == source
          path.pop
          u = path[-1]
          break
        end
      end
    end
    next unless u == target
    flow_value += augment(path, inf, r_adj)
    if flow_value >= cutoff
      residual.graph[:flow_value] = flow_value
      return residual
    end
  end
  flow_value += edmondskarp_core(residual, source, target, cutoff - flow_value)
  residual.graph[:flow_value] = flow_value
  residual
end
single_source_shortest_path(graph, source, cutoff=nil) click to toggle source

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source from which shortest paths are needed @param cutoff [Numeric, nil] cutoff for the shortest path algorithm

@return [Array<Object, Array<Object, Array<Object>>>] path lengths for all nodes from all nodes

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

Computes shortest path values to all nodes from a given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source to compute path length from @param cutoff [Numeric, nil] cutoff for the shortest path algorithm

@return [Array<Object, Numeric>] path lengths for all nodes

# File lib/networkx/shortest_path/unweighted.rb, line 34
def self.single_source_shortest_path_length(graph, source, cutoff=nil)
  raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source)
  cutoff = Float::INFINITY if cutoff.nil?
  nextlevel = {source => 1}
  help_single_shortest_path_length(graph.adj, nextlevel, cutoff).take(graph.nodes.length)
end
singlesource_bellmanford(graph, source, target=nil, cutoff=nil) click to toggle source
# File lib/networkx/shortest_path/weighted.rb, line 282
def self.singlesource_bellmanford(graph, source, target=nil, cutoff=nil)
  return [0, [source]] if source == target
  weight = get_weight(graph)
  paths = {source => [source]}
  dist = help_bellman_ford(graph, [source], weight, nil, paths, nil, cutoff, target)
  return [dist, paths] if target.nil?
  raise ArgumentError, 'Node not reachable!' unless dist.key?(target)
  [dist[target], paths[target]]
end
singlesource_bellmanford_path(graph, source, cutoff=nil) click to toggle source

Shortest path from source to all nodes using Bellman Ford algorithm

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param cutoff [Numeric, nil] cutoff for Bellman Ford algorithm

@return [Hash{ Object => Array<Object> }] path from source to all nodes

# File lib/networkx/shortest_path/weighted.rb, line 326
def self.singlesource_bellmanford_path(graph, source, cutoff=nil)
  _, path = singlesource_bellmanford(graph, source, cutoff)
  path
end
singlesource_bellmanford_path_length(graph, source, cutoff=nil) click to toggle source

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param cutoff [Numeric, nil] cutoff for Bellman Ford algorithm

@return [Hash{ Object => Numeric }] path lengths from source to all nodes

# File lib/networkx/shortest_path/weighted.rb, line 338
def self.singlesource_bellmanford_path_length(graph, source, cutoff=nil)
  weight = get_weight(graph)
  help_bellman_ford(graph, [source], weight, nil, nil, nil, cutoff)
end
singlesource_dijkstra(graph, source, target=nil, cutoff=nil) click to toggle source

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

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param target [Object] target @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Hash{ Object => Array<Object> }, Array<Object>] paths for all nodes/target node from given node

# File lib/networkx/shortest_path/weighted.rb, line 110
def self.singlesource_dijkstra(graph, source, target=nil, cutoff=nil)
  multisource_dijkstra(graph, [source], target, cutoff)
end
singlesource_dijkstra_path(graph, source, cutoff=nil) click to toggle source

Computes shortest paths to all nodes from the given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Hash{ Object => Array<Object> }] paths for all nodes from given node

# File lib/networkx/shortest_path/weighted.rb, line 132
def self.singlesource_dijkstra_path(graph, source, cutoff=nil)
  multisource_dijkstra_path(graph, [source], cutoff)
end
singlesource_dijkstra_path_length(graph, source, cutoff=nil) click to toggle source

Computes shortest path lengths to all nodes from the given node

@param graph [Graph, DiGraph, MultiGraph, MultiDiGraph] a graph @param source [Object] source @param cutoff [Numeric, nil] cutoff for the dijkstra algorithm

@return [Hash{ Object => Numeric }] path lengths for all nodes from given node

# File lib/networkx/shortest_path/weighted.rb, line 121
def self.singlesource_dijkstra_path_length(graph, source, cutoff=nil)
  multisource_dijkstra_path_length(graph, [source], cutoff)
end
strong_product(g_1, g_2) click to toggle source

Returns the strong product of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the strong product of the two graphs

# File lib/networkx/operators/product.rb, line 161
def self.strong_product(g_1, g_2)
  g = init_product_graph(g_1, g_2)
  g.add_nodes(node_product(g_1, g_2))
  g.add_edges(nodes_cross_edges(g_1, g_2))
  g.add_edges(edges_cross_nodes(g_1, g_2))
  g.add_edges(directed_edges_cross_edges(g_1, g_2))
  g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed?
  g
end
symmetric_difference(g_1, g_2) click to toggle source

Performs the symmetric difference of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the symmetric difference of the two graphs

# File lib/networkx/operators/binary.rb, line 130
def self.symmetric_difference(g_1, g_2)
  result = Marshal.load(Marshal.dump(g_1))
  result.clear

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

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

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

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

Returns the tensor product of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the tensor product of the two graphs

# File lib/networkx/operators/product.rb, line 119
def self.tensor_product(g_1, g_2)
  g = init_product_graph(g_1, g_2)
  g.add_nodes(node_product(g_1, g_2))
  g.add_edges(directed_edges_cross_edges(g_1, g_2))
  g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed?
  g
end
to_matrix(graph, val, multigraph_weight='sum') click to toggle source

TODO: Reduce condition branches and method length

# File lib/networkx/to_matrix.rb, line 3
def self.to_matrix(graph, val, multigraph_weight='sum')
  is_undirected = !graph.directed?
  is_multigraph = graph.multigraph?
  nodelen = graph.nodes.length

  m = NMatrix.new(nodelen, val)
  index = {}
  inv_index = {}
  ind = 0

  graph.nodes.each do |u, _|
    index[u] = ind
    inv_index[ind] = u
    ind += 1
  end

  if is_multigraph
    graph.adj.each do |u, edge_hash|
      edge_hash.each do |v, keys|
        all_weights = []
        keys.each do |_key, attrs|
          all_weights << attrs[:weight]
        end

        edge_attr = 0

        case multigraph_weight
        when 'sum'
          edge_attr = all_weights.inject(0, :+)
        when 'max'
          edge_attr = all_weights.max
        when 'min'
          edge_attr = all_weights.min
        end

        m[index[u], index[v]] = edge_attr
        m[index[v], index[u]] = edge_attr || 1 if is_undirected
      end
    end
  else
    graph.adj.each do |u, edge_hash|
      edge_hash.each do |v, attrs|
        m[index[u], index[v]] = (attrs[:weight] || 1)
        m[index[v], index[u]] = (attrs[:weight] || 1) if is_undirected
      end
    end
  end
  [m, inv_index]
end
topological_sort(graph) click to toggle source

Returns the nodes arranged in the topologically sorted fashion

@param graph [DiGraph] a graph

@return [Array<Object>] Array of the nodes

# File lib/networkx/auxillary_functions/dag.rb, line 33
def self.topological_sort(graph)
  raise ArgumentError, 'Topological Sort not defined on undirected graphs!' unless graph.directed?
  nodes = []
  indegree_map = Hash[graph.nodes.each_key.map { |u| [u, graph.in_degree(u)] if graph.in_degree(u) > 0 }.compact]
  zero_indegree = graph.nodes.each_key.map { |u| u if graph.in_degree(u).zero? }.compact

  until zero_indegree.empty?
    node = zero_indegree.shift
    raise ArgumentError, 'Graph changed during iteration!' unless graph.nodes.key?(node)
    graph.adj[node].each_key do |child|
      indegree_map[child] -= 1
      if indegree_map[child].zero?
        zero_indegree << child
        indegree_map.delete(child)
      end
    end
    nodes << node
  end
  raise ArgumentError, 'Graph contains cycle or graph changed during iteration!' unless indegree_map.empty?
  nodes
end
undirected_edges_cross_edges(g_1, g_2) click to toggle source

Returns the product of undirected edges with edges

# File lib/networkx/operators/product.rb, line 55
def self.undirected_edges_cross_edges(g_1, g_2)
  result = []
  edges_in_array(g_1).each do |u, v, c|
    edges_in_array(g_2).each do |x, y, d|
      result << [[v, x], [u, y], hash_product(c, d)]
    end
  end
  result
end
union(g_1, g_2) click to toggle source

Performs the union of two graphs

@param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.1 @param [Graph, DiGraph, MultiGraph, MultiDiGraph] graph no.2

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] the union of the two graphs

# File lib/networkx/operators/binary.rb, line 200
def self.union(g_1, g_2)
  raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph?

  case g_1
  when NetworkX::MultiGraph
    new_graph = NetworkX::MultiGraph.new
  when NetworkX::MultiDiGraph
    new_graph = NetworkX::MultiDiGraph.new
  when NetworkX::Graph
    new_graph = NetworkX::Graph.new
  when NetworkX::DiGraph
    new_graph = NetworkX::DiGraph.new
  end

  new_graph.graph.merge!(g_1.graph)
  new_graph.graph.merge!(g_2.graph)

  raise ArgumentError, 'Graphs must be disjoint!' unless (g_1.nodes.keys & g_2.nodes.keys).empty?

  g1_edges = get_edges(g_1)
  g2_edges = get_edges(g_2)

  new_graph.add_nodes(g_1.nodes.keys)
  new_graph.add_edges(g1_edges)
  new_graph.add_nodes(g_2.nodes.keys)
  new_graph.add_edges(g2_edges)

  new_graph
end
union_all(graphs) click to toggle source

Performs the union of many graphs

@param [Array<Graph>, Array<DiGraph>, Array<MultiGraph>, Array<MultiDiGraph>] Array of graphs

@return [Graph, DiGraph, MultiGraph, MultiDiGraph] union of all the graphs

# 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) click to toggle source

Returns the wiener index of the graph

@param graph [Graph, DiGraph] a graph

@return [Numeric] wiener index of the graph

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

Public Instance Methods

augment(path, inf, r_adj) click to toggle source

Helper function for augmenting flow

# File lib/networkx/flow/shortestaugmentingpath.rb, line 114
def augment(path, inf, r_adj)
  flow = inf
  temp_path = path.clone
  u = temp_path.shift
  temp_path.each do |v|
    attr = r_adj[u][v]
    flow = [flow, attr[:capacity] - attr[:flow]].min
    u = v
  end
  raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf
  temp_path = path.clone
  u = temp_path.shift
  temp_path.each do |v|
    r_adj[u][v][:flow] += flow
    r_adj[v][u][:flow] -= flow
    u = v
  end
  flow
end