module NetworkX

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# File lib/networkx/flow/preflowpush.rb, line 5
def self.arbitrary_element(iterable)
  iterable.each { |u| return u }
end

# 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

# 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

# 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

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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# File lib/networkx/flow/capacityscaling.rb, line 126
def self.count
  @itr += 1
  @itr
end

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# File lib/networkx/auxillary_functions/eccentricity.rb, line 24
def self.diameter(graph)
  eccentricity(graph).values.max
end

# 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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

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

# 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

# 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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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