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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 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
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
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
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
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
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
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
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
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
# File lib/networkx/flow/capacityscaling.rb, line 126 def self.count @itr += 1 @itr end
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Returns a label for unique node
# File lib/networkx/flow/capacityscaling.rb, line 5 def self.generate_unique_node SecureRandom.uuid end
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
# 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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