Module: NetworkX
- Defined in:
- lib/networkx/flow/preflowpush.rb,
lib/networkx/graph.rb,
lib/networkx/digraph.rb,
lib/networkx/version.rb,
lib/networkx/to_matrix.rb,
lib/networkx/flow/utils.rb,
lib/networkx/multigraph.rb,
lib/networkx/multidigraph.rb,
lib/networkx/operators/all.rb,
lib/networkx/traversals/bfs.rb,
lib/networkx/traversals/dfs.rb,
lib/networkx/operators/unary.rb,
lib/networkx/flow/edmondskarp.rb,
lib/networkx/operators/binary.rb,
lib/networkx/converters/to_csv.rb,
lib/networkx/operators/product.rb,
lib/networkx/converters/to_json.rb,
lib/networkx/link_analysis/hits.rb,
lib/networkx/shortest_path/astar.rb,
lib/networkx/shortest_path/dense.rb,
lib/networkx/traversals/edge_dfs.rb,
lib/networkx/flow/capacityscaling.rb,
lib/networkx/link_analysis/pagerank.rb,
lib/networkx/shortest_path/weighted.rb,
lib/networkx/auxillary_functions/dag.rb,
lib/networkx/auxillary_functions/mis.rb,
lib/networkx/auxillary_functions/mst.rb,
lib/networkx/shortest_path/unweighted.rb,
lib/networkx/auxillary_functions/cycles.rb,
lib/networkx/auxillary_functions/wiener.rb,
lib/networkx/auxillary_functions/cliques.rb,
lib/networkx/flow/shortestaugmentingpath.rb,
lib/networkx/auxillary_functions/vitality.rb,
lib/networkx/auxillary_functions/union_find.rb,
lib/networkx/auxillary_functions/eccentricity.rb
Overview
TODO: Reduce module length
Defined Under Namespace
Classes: CurrentEdge, DiGraph, GlobalRelabelThreshold, Graph, Level, MultiDiGraph, MultiGraph, UnionFind
Constant Summary collapse
- VERSION =
'0.1.1'.freeze
Class Method Summary collapse
-
._build_flow_dict(graph, residual) ⇒ Object
Returns the flowdict of the graph.
-
._build_residual_network(graph) ⇒ Object
Returns the residual graph of the given graph.
-
._detect_unboundedness(residual) ⇒ Object
Detects the unboundedness in the residual graph.
-
.activate(node, source, target, levels, residual_nodes) ⇒ Object
Helper function to move a node from inactive set to active set.
-
.all_pairs_dijkstra(graph, cutoff = nil) ⇒ Array<Object, Array<Hash{ Object => Numeric }, Hash{ Object => Array<Object> }>>
Finds shortest weighted paths and lengths between all nodes.
-
.all_pairs_dijkstra_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>
Finds shortest weighted paths between all nodes.
-
.all_pairs_dijkstra_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>
Finds shortest weighted path length between all nodes.
-
.all_pairs_shortest_path(graph, cutoff = nil) ⇒ Array<Object, Hash {Object => Array<Object> }>
Computes shortest paths to all nodes from all nodes.
-
.all_pairs_shortest_path_length(graph, cutoff = nil) ⇒ Array<Object, Array<Object, Numeric>>
Computes shortest path values to all nodes from all nodes.
-
.allpairs_bellmanford_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>
Shortest paths between all nodes using Bellman Ford algorithm.
-
.allpairs_bellmanford_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>
Shortest path lengths between all nodes using Bellman Ford algorithm.
-
.ancestors(graph, source) ⇒ Array<Object>
Returns the ancestors of a given node.
-
.arbitrary_element(iterable) ⇒ Object
Helper function to return an arbitrary element from an iterable object.
-
.astar_path(graph, source, target, heuristic = nil) ⇒ Array<Object>
Returns path using astar algorithm between source and target.
-
.astar_path_length(graph, source, target, heuristic = nil) ⇒ Numeric
Returns astar path length b/w source and target.
-
.augment(residual, inf, path) ⇒ Object
Helper function to augment the flow in a residual graph.
-
.authority_matrix(graph) ⇒ NMatrix
Computes authority matrix for the graph.
-
.bellmanford_path(graph, source, target) ⇒ Array<Object>
Shortest path from source to target using Bellman Ford algorithm.
-
.bellmanford_path_length(graph, source, target) ⇒ Numeric
Length of shortest path from source to target using Bellman Ford algorithm.
-
.bellmanford_predecesor_distance(graph, source, target = nil, cutoff = nil) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>
Finds shortest weighted path lengths and predecessors on shortest paths.
-
.bfs_edges(graph, source) ⇒ Object
Returns edges of the graph travelled in breadth first fashion.
-
.bfs_predecessors(graph, source) ⇒ Object
Returns predecessor child pair of the graph travelled in breadth first fashion.
-
.bfs_successors(graph, source) ⇒ Object
Returns parent successor pair of the graph travelled in breadth first fashion.
-
.bidirectional_bfs(residual, source, target) ⇒ Object
Helper function for the bidirectional bfs.
-
.build_flow_dict(graph, residual) ⇒ Hash{ Object => Hash{ Object => Numeric }] flowdict containing all the flow values in the edges
Build flow dictionary of a graph from its residual graph.
-
.build_residual_network(graph) ⇒ DiGraph
Builds a residual graph from a constituent graph.
-
.capacity_scaling(graph) ⇒ Array<Numeric, Hash{ Object => Hash{ Object => Numeric } }>
Computes max flow using capacity scaling algorithm.
-
.cartesian_product(g_1, g_2) ⇒ Graph, ...
Returns the cartesian product of two graphs.
-
.closeness_vitality(graph, node) ⇒ Numeric
Returns the closeness vitality of a node.
-
.complement(graph) ⇒ Graph, ...
Performs the complement operation on the graph.
-
.compose(g_1, g_2) ⇒ Graph, ...
Performs the composition of two graphs.
-
.compose_all(graphs) ⇒ Graph, ...
Performs the composition of many graphs.
-
.convert_to_distinct_labels(graph, starting_int = -1)) ⇒ Object
Transforms the labels of the nodes of the graphs so that they are disjoint.
- .count ⇒ Object
-
.cycle_basis(graph, root = nil) ⇒ Array<Array<Object>>
Returns all basis cycles in graph.
-
.descendants(graph, source) ⇒ Array<Object>
Returns the descendants of a given node.
-
.detect_unboundedness(r_network, source, target) ⇒ Object
Detects unboundedness in a graph, raises exception when infinite capacity flow is found.
-
.dfs_edges(graph, source, depth_limit = nil) ⇒ Object
Returns edges of the graph travelled in depth first fashion.
-
.dfs_predecessors(graph, source, depth_limit = nil) ⇒ Object
Returns predecessor child pair of the graph travelled in depth first fashion.
-
.dfs_successors(graph, source, depth_limit = nil) ⇒ Object
Returns parent successor pair of the graph travelled in depth first fashion.
-
.dfs_tree(graph, source, depth_limit = nil) ⇒ Object
Returns dfs tree of the graph.
-
.diameter(graph) ⇒ Numeric
Returns the diameter of a graph.
-
.difference(g_1, g_2) ⇒ Graph, ...
Performs the difference of two graphs.
-
.dijkstra_path(graph, source, target) ⇒ Numeric
Computes shortest path to target from the given node.
-
.dijkstra_path_length(graph, source, target) ⇒ Numeric
Computes shortest path length to target from the given node.
-
.dijkstra_predecessor_distance(graph, source, cutoff = nil) ⇒ <Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>] predcessor hash and distance hash
Computes weighted shortest path length and predecessors.
-
.directed_edges_cross_edges(g_1, g_2) ⇒ Object
Returns the product of directed edges with edges.
-
.discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target) ⇒ Object
Helper function for discharging a node.
-
.disjoint_union(g_1, g_2) ⇒ Graph, ...
Performs the disjoint union of two graphs.
-
.disjoint_union_all(graphs) ⇒ Graph, ...
Performs the disjoint union of many graphs.
-
.dist_path_lambda(_graph, _new_weight) ⇒ Object
Helper function to get distances.
-
.eccentricity(graph, node = nil) ⇒ Array<Numeric>, Numeric
Returns the eccentricity of a particular node or all nodes.
-
.edge_dfs(graph, start, orientation = nil) ⇒ Object
Performs edge dfs on the graph Orientation :ignore, directed edges can be travelled in both fashions Orientation reverse, directed edges can be travelled in reverse fashion Orientation :nil, the graph is not meddled with.
-
.edge_id(graph, edge) ⇒ Object
Helper function of edge_dfs.
-
.edges_cross_nodes(g_1, g_2) ⇒ Object
Returns the product of edges with edges.
-
.edges_cross_nodes_and_nodes(g_1, g_2) ⇒ Object
Returns the product of edges with pairs of nodes.
-
.edges_in_array(graph) ⇒ Object
Returns the edges of the graph in an array.
-
.edmondskarp(graph, source, target, residual = nil, cutoff = nil) ⇒ DiGraph
Computes max flow using edmonds karp algorithm.
-
.edmondskarp_core(residual, source, target, cutoff) ⇒ Object
Core helper function for the EdmondsKarp algorithm.
-
.edmondskarp_impl(graph, source, target, residual, cutoff) ⇒ Object
Helper function for the edmondskarp function.
-
.find_cliques(graph) ⇒ Array<Array<Object>>
Returns all cliques in the graph.
-
.find_cycle(graph, node) ⇒ Array<Array<Object>>
Returns the cycle containing the given node.
-
.floyd_warshall(graph) ⇒ Hash{ Object => { Object => { Numeric }}}
Returns the all pair distance between all the nodes.
-
.gap_heuristic(height, levels, residual_nodes) ⇒ Object
Helper function for applying gap heuristic.
-
.generate_unique_node ⇒ Object
Returns a label for unique node.
-
.get_edges(graph) ⇒ Object
Returns the edges of the graph in an array.
-
.get_edges_weights(graph) ⇒ Object
Helper function for the minimum spanning tree.
-
.get_sources(graph) ⇒ Object
Helper function to get sources.
-
.get_weight(graph) ⇒ Object
Helper function to extract weight from a adjecency hash.
-
.global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred) ⇒ Object
Helper function for global relabel heuristic.
-
.graph_to_csv(graph, filename = 'graph.csv') ⇒ Object
Saves the graph in a csv file.
-
.graph_to_json(graph) ⇒ JSON
Returns a JSON object of the given graph.
-
.hash_product(hash_1, hash_2) ⇒ Object
Returns the hash product of two hashes.
-
.help_bellman_ford(graph, sources, weight, pred = nil, paths = nil, dist = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for bellman ford.
-
.help_dijkstra(graph, source, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for single source dijkstra.
-
.help_multisource_dijkstra(graph, sources, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for multisource dijkstra.
-
.help_single_shortest_path(adj, firstlevel, paths, cutoff) ⇒ Object
Helper function for finding single source shortest path.
-
.help_single_shortest_path_length(adj, firstlevel, cutoff) ⇒ Object
Helper function for single source shortest path length.
-
.hits(graph, max_iter = 100, tol = 1e-8, nstart) ⇒ Array<Numeric, Numeric>
Computes hits and authority scores for all the graphs.
-
.hub_matrix(graph) ⇒ NMatrix
Computes hub matrix for the graph.
-
.init_product_graph(g_1, g_2) ⇒ Object
Initializes the product graph.
-
.intersection(g_1, g_2) ⇒ Graph, ...
Performs the intersection of two graphs.
-
.intersection_all(graphs) ⇒ Graph, ...
Performs the intersection of many graphs.
-
.johnson(graph) ⇒ Array<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes
Returns shortest path between all pairs of nodes.
-
.json_to_graph(json_str) ⇒ Graph, ...
Returns a graph from the json encoded graph.
-
.lexicographic_product(g_1, g_2) ⇒ Graph, ...
Returns the lexicographic product of two graphs.
-
.maximal_independent_set(graph, nodes) ⇒ Numeric
Returns the maximal independent set of a graph.
-
.minimum_spanning_tree(graph) ⇒ DiGraph, Graph
Returns the minimum spanning tree of a graph.
-
.multisource_dijkstra(graph, sources, target = nil, cutoff = nil) ⇒ Numeric, Array<Object>
Computes shortest paths and path lengths to a target from one of the nodes.
-
.multisource_dijkstra_path(graph, sources, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Computes shortest paths to any from the given nodes.
-
.multisource_dijkstra_path_length(graph, sources, cutoff = nil) ⇒ Hash{ Object => Numeric }
Computes shortest path lengths to any from the given nodes.
-
.negative_edge_cycle(graph) ⇒ Boolean
Finds if there is a negative edge cycle in the graph.
-
.node_product(g_1, g_2) ⇒ Object
Returns the node product of nodes of two graphs.
-
.nodes_cross_edges(g_1, g_2) ⇒ Object
Returns the product of directed nodes with edges.
-
.number_of_cliques(graph, node) ⇒ Numeric
Returns the number of cliques in a graph containing a node.
-
.out_edges(graph, node) ⇒ Object
Helper function for edge_dfs.
-
.pagerank(graph, init, alpha = 0.85, eps = 1e-4, max_iter = 100) ⇒ Array<Numeric>
Computes pagerank values for the graph.
-
.power(graph, pow) ⇒ Graph, ...
Returns the specified power of the graph.
-
.predecessor(graph, source, cutoff = nil, return_seen = false) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>, Hash{ Object => Array<Object> }
Computes shortest paths to all nodes from all nodes.
-
.preflowpush(graph, source, target, residual = nil, globalrelabel_freq = 1, value_only = false) ⇒ DiGraph
Computes max flow using preflow push algorithm.
-
.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only) ⇒ Object
Helper function to apply the preflow push algorithm.
-
.push(node_1, node_2, flow, residual_nodes, residual_adj) ⇒ Object
Helper function for augmenting flow.
-
.radius(graph) ⇒ Numeric
Returns the radius of a graph.
-
.relabel(node, num, r_adj, r_nodes) ⇒ Object
Helper function to relable a node to create a permissible edge.
-
.reverse_bfs(src, residual_pred) ⇒ Object
Helper function for reverse bfs.
-
.set_path_lengths_johnson(graph, dist_path, new_weight) ⇒ Object
Helper function to set path lengths for Johnson algorithm.
-
.shortest_augmenting_path(graph, source, target, residual = nil, _value_only = false, two_phase = false, cutoff = nil) ⇒ DiGraph
Computes max flow using shortest augmenting path algorithm.
-
.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff) ⇒ Object
Helper function for running the shortest augmenting path algorithm.
-
.single_source_shortest_path(graph, source, cutoff = nil) ⇒ Array<Object, Array<Object, Array<Object>>>
Computes single source shortest path from a node to every other node.
-
.single_source_shortest_path_length(graph, source, cutoff = nil) ⇒ Array<Object, Numeric>
Computes shortest path values to all nodes from a given node.
- .singlesource_bellmanford(graph, source, target = nil, cutoff = nil) ⇒ Object
-
.singlesource_bellmanford_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Shortest path from source to all nodes using Bellman Ford algorithm.
-
.singlesource_bellmanford_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }
Shortest path length from source to all nodes using Bellman Ford algorithm.
-
.singlesource_dijkstra(graph, source, target = nil, cutoff = nil) ⇒ Hash{ Object => Array<Object> }, Array<Object>
Computes shortest paths and path distances to all nodes/target from the given node.
-
.singlesource_dijkstra_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Computes shortest paths to all nodes from the given node.
-
.singlesource_dijkstra_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }
Computes shortest path lengths to all nodes from the given node.
-
.strong_product(g_1, g_2) ⇒ Graph, ...
Returns the strong product of two graphs.
-
.symmetric_difference(g_1, g_2) ⇒ Graph, ...
Performs the symmetric difference of two graphs.
-
.tensor_product(g_1, g_2) ⇒ Graph, ...
Returns the tensor product of two graphs.
-
.to_matrix(graph, val, multigraph_weight = 'sum') ⇒ Object
TODO: Reduce condition branches and method length.
-
.topological_sort(graph) ⇒ Array<Object>
Returns the nodes arranged in the topologically sorted fashion.
-
.undirected_edges_cross_edges(g_1, g_2) ⇒ Object
Returns the product of undirected edges with edges.
-
.union(g_1, g_2) ⇒ Graph, ...
Performs the union of two graphs.
-
.union_all(graphs) ⇒ Graph, ...
Performs the union of many graphs.
-
.wiener_index(graph) ⇒ Numeric
Returns the wiener index of the graph.
Instance Method Summary collapse
-
#augment(path, inf, r_adj) ⇒ Object
Helper function for augmenting flow.
Class Method Details
._build_flow_dict(graph, residual) ⇒ Object
Returns the flowdict of the graph
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
# File 'lib/networkx/flow/capacityscaling.rb', line 93 def self._build_flow_dict(graph, residual) flow_dict = {} inf = Float::INFINITY if graph.multigraph? graph.nodes.each_key do |u| flow_dict[u] = {} graph.adj[u].each do |v, uv_edges| flow_dict[u][v] = Hash[uv_edges.map do |k, e| [k, u != v || (e[:capacity] || inf) <= 0 || (e[:weight] || 0) >= 0 ? 0 : e[:capacity]] end] end residual.adj[u].each do |v, uv_edges| flow_dict[u][v].merge!(Hash[uv_edges.map { |_, val| [val[:temp_key][0], val[:flow]] if val[:flow] > 0 }]) end end else graph.nodes.each_key do |u| flow_dict[u] = Hash[graph.adj[u].map do |v, e| [v, u != v || (e[:capacity] || inf) <= 0 || (e[:weight] || 0) >= 0 ? 0 : e[:capacity]] end] merge_dict = {} residual.adj[u].each do |v, uv_edges| uv_edges.each_value { |attrs| merge_dict[v] = attrs[:flow] if attrs[:flow] > 0 } end flow_dict[u].merge!(merge_dict) end end flow_dict end |
._build_residual_network(graph) ⇒ Object
Returns the residual graph of the given graph
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
# File 'lib/networkx/flow/capacityscaling.rb', line 48 def self._build_residual_network(graph) raise ArgumentError, 'Sum of demands should be 0!' unless\ graph.nodes.values.map { |attr| attr[:demand] || 0 }.inject(0, :+).zero? residual = NetworkX::MultiDiGraph.new(inf: 0) residual.add_nodes(graph.nodes.map { |u, attr| [u, excess: (attr[:demand] || 0) * -1, potential: 0] }) inf = Float::INFINITY edge_list = [] # TODO: Selfloop edges check if graph.multigraph? graph.adj.each do |u, u_edges| u_edges.each do |v, uv_edges| uv_edges.each do |k, attrs| edge_list << [u, v, k, e] if u != v && (attrs[:capacity] || inf) > 0 end end end else graph.adj.each do |u, u_edges| u_edges.each do |v, attrs| edge_list << [u, v, 0, attrs] if u != v && (attrs[:capacity] || inf) > 0 end end end temp_inf = [residual.nodes.map { |_u, attrs| attrs[:excess].abs }.inject(0, :+), edge_list.map do |_, _, _, e| (e.key?(:capacity) && e[:capacity] != inf ? e[:capacity] : 0) end.inject(0, :+) * 2].max inf = temp_inf.zero? ? 1 : temp_inf edge_list.each do |u, v, k, e| r = [e[:capacity] || inf, inf].min w = e[:weight] || 0 residual.add_edge(u, v, temp_key: [k, true], capacity: r, weight: w, flow: 0) residual.add_edge(v, u, temp_key: [k, false], capacity: 0, weight: -w, flow: 0) end residual.graph[:inf] = inf _detect_unboundedness(residual) residual end |
._detect_unboundedness(residual) ⇒ Object
Detects the unboundedness in the residual graph
30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
# File 'lib/networkx/flow/capacityscaling.rb', line 30 def self._detect_unboundedness(residual) g = NetworkX::DiGraph.new g.add_nodes(residual.nodes.keys.zip(residual.nodes.values)) inf = residual.graph[:inf] residual.nodes.each do |u, _attr| residual.adj[u].each do |v, uv_attrs| w = inf uv_attrs.each { |_key, edge_attrs| w = [w, edge_attrs[:weight]].min if edge_attrs[:capacity] == inf } g.add_edge(u, v, weight: w) unless w == inf end end raise ArgumentError, 'Negative cost cycle of infinite capacity found!' if negative_edge_cycle(g) end |
.activate(node, source, target, levels, residual_nodes) ⇒ Object
Helper function to move a node from inactive set to active set
116 117 118 119 120 121 122 |
# File 'lib/networkx/flow/preflowpush.rb', line 116 def self.activate(node, source, target, levels, residual_nodes) return if node == source || node == target return unless level.inactive.include?(node) level = levels[residual_nodes[node][:height]] level.inactive.delete(node) level.active.add(node) end |
.all_pairs_dijkstra(graph, cutoff = nil) ⇒ Array<Object, Array<Hash{ Object => Numeric }, Hash{ Object => Array<Object> }>>
Finds shortest weighted paths and lengths between all nodes
184 185 186 187 188 |
# File 'lib/networkx/shortest_path/weighted.rb', line 184 def self.all_pairs_dijkstra(graph, cutoff=nil) path = [] graph.nodes.each_key { |n| path << [n, singlesource_dijkstra(graph, n, nil, cutoff)] } path end |
.all_pairs_dijkstra_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>
Finds shortest weighted paths between all nodes
208 209 210 211 212 |
# File 'lib/networkx/shortest_path/weighted.rb', line 208 def self.all_pairs_dijkstra_path(graph, cutoff=nil) paths = [] graph.nodes.each_key { |n| paths << singlesource_dijkstra_path(graph, n, cutoff) } paths end |
.all_pairs_dijkstra_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>
Finds shortest weighted path length between all nodes
196 197 198 199 200 |
# File 'lib/networkx/shortest_path/weighted.rb', line 196 def self.all_pairs_dijkstra_path_length(graph, cutoff=nil) path_lengths = [] graph.nodes.each_key { |n| path_lengths << [n, singlesource_dijkstra_path_length(graph, n, cutoff)] } path_lengths end |
.all_pairs_shortest_path(graph, cutoff = nil) ⇒ Array<Object, Hash {Object => Array<Object> }>
Computes shortest paths to all nodes from all nodes
96 97 98 99 100 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 96 def self.all_pairs_shortest_path(graph, cutoff=nil) shortest_paths = [] graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path(graph, n, cutoff)] } shortest_paths end |
.all_pairs_shortest_path_length(graph, cutoff = nil) ⇒ Array<Object, Array<Object, Numeric>>
Computes shortest path values to all nodes from all nodes
47 48 49 50 51 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 47 def self.all_pairs_shortest_path_length(graph, cutoff=nil) shortest_paths = [] graph.nodes.each_key { |n| shortest_paths << [n, single_source_shortest_path_length(graph, n, cutoff)] } shortest_paths end |
.allpairs_bellmanford_path(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Array<Object> }>
Shortest paths between all nodes using Bellman Ford algorithm
361 362 363 364 365 |
# File 'lib/networkx/shortest_path/weighted.rb', line 361 def self.allpairs_bellmanford_path(graph, cutoff=nil) paths = [] graph.nodes.each_key { |n| paths << [n, singlesource_bellmanford_path(graph, n, cutoff)] } paths end |
.allpairs_bellmanford_path_length(graph, cutoff = nil) ⇒ Array<Object, Hash{ Object => Numeric }>
Shortest path lengths between all nodes using Bellman Ford algorithm
349 350 351 352 353 |
# File 'lib/networkx/shortest_path/weighted.rb', line 349 def self.allpairs_bellmanford_path_length(graph, cutoff=nil) path_lengths = [] graph.nodes.each_key { |n| path_lengths << [n, singlesource_bellmanford_path_length(graph, n, cutoff)] } path_lengths end |
.ancestors(graph, source) ⇒ Array<Object>
Returns the ancestors of a given node
20 21 22 23 24 |
# File 'lib/networkx/auxillary_functions/dag.rb', line 20 def self.ancestors(graph, source) raise ArgumentError, 'Source is not present in the graph!' unless graph.node?(source) anc = single_source_shortest_path_length(graph.reverse, source).map { |u, _| u }.uniq anc - [source] end |
.arbitrary_element(iterable) ⇒ Object
Helper function to return an arbitrary element from an iterable object
5 6 7 |
# File 'lib/networkx/flow/preflowpush.rb', line 5 def self.arbitrary_element(iterable) iterable.each { |u| return u } end |
.astar_path(graph, source, target, heuristic = nil) ⇒ Array<Object>
Returns path using astar algorithm between source and target
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
# File 'lib/networkx/shortest_path/astar.rb', line 13 def self.astar_path(graph, source, target, heuristic=nil) warn 'A* is not implemented for MultiGraph and MultiDiGraph' raise ArgumentError, 'Either source or target is not in graph' unless graph.node?(source) && graph.node?(target) count = ->(i) { i + 1 } i = -1 heuristic ||= (->(_u, _v) { 0 }) heap = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) } heap << [0, count.call(i), source, 0, nil] enqueued, explored = {}, {} until heap.empty? _, _, curnode, dist, parent = heap.pop if curnode == target path = [curnode] node = parent until node.nil? path << node node = explored[node] end path.reverse return path end next if explored.key?(curnode) explored[curnode] = parent graph.adj[curnode].each do |u, attrs| next if explored.key?(u) ncost = dist + (attrs[:weight] || 1) if enqueued.key?(u) qcost, = enqueued[u] next if qcost <= ncost else h = heuristic.call(u, target) enqueued[u] = ncost, h heap << [ncost + h, count.call(i), u, ncost, curnode] end end end raise ArgumentError, 'Target not reachable!' end |
.astar_path_length(graph, source, target, heuristic = nil) ⇒ Numeric
Returns astar path length b/w source and target
64 65 66 67 68 69 70 |
# File 'lib/networkx/shortest_path/astar.rb', line 64 def self.astar_path_length(graph, source, target, heuristic=nil) raise ArgumentError, 'Either source or target is not in graph' unless graph.node?(source) && graph.node?(target) path = astar_path(graph, source, target, heuristic) path_length = 0 (1..(path.length - 1)).each { |i| path_length += (graph.adj[path[i - 1]][path[i]][:weight] || 1) } path_length end |
.augment(residual, inf, path) ⇒ Object
Helper function to augment the flow in a residual graph
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# File 'lib/networkx/flow/edmondskarp.rb', line 5 def self.augment(residual, inf, path) flow = inf path_first_elem = path.shift u = path_first_elem path.each do |v| flow = [flow, residual.adj[u][v][:capacity] - residual.adj[u][v][:flow]].min u = v end raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf u = path_first_elem path.each do |v| residual.adj[u][v][:flow] += flow residual.adj[v][u][:flow] -= flow u = v end flow end |
.authority_matrix(graph) ⇒ NMatrix
Computes authority matrix for the graph
45 46 47 48 |
# File 'lib/networkx/link_analysis/hits.rb', line 45 def self.(graph) matrix, = to_matrix(graph, 0) matrix.transpose.dot matrix end |
.bellmanford_path(graph, source, target) ⇒ Array<Object>
Shortest path from source to target using Bellman Ford algorithm
314 315 316 317 |
# File 'lib/networkx/shortest_path/weighted.rb', line 314 def self.bellmanford_path(graph, source, target) _, path = singlesource_bellmanford(graph, source, target) path end |
.bellmanford_path_length(graph, source, target) ⇒ Numeric
Length of shortest path from source to target using Bellman Ford algorithm
299 300 301 302 303 304 305 |
# File 'lib/networkx/shortest_path/weighted.rb', line 299 def self.bellmanford_path_length(graph, source, target) return 0 if source == target weight = get_weight(graph) length = help_bellman_ford(graph, [source], weight, nil, nil, nil, nil, target=target) raise ArgumentError, 'Node not reachable!' unless length.key?(target) length[target] end |
.bellmanford_predecesor_distance(graph, source, target = nil, cutoff = nil) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>
Finds shortest weighted path lengths and predecessors on shortest paths
271 272 273 274 275 276 277 278 279 280 |
# File 'lib/networkx/shortest_path/weighted.rb', line 271 def self.bellmanford_predecesor_distance(graph, source, target=nil, cutoff=nil) raise ArgumentError, 'Node not found!' unless graph.node?(source) weight = get_weight(graph) # TODO: Detection of selfloop edges dist = {source => 0} pred = {source => []} return [pred, dist] if graph.nodes.length == 1 dist = help_bellman_ford(graph, [source], weight, pred, nil, dist, cutoff, target) [pred, dist] end |
.bfs_edges(graph, source) ⇒ Object
Returns edges of the graph travelled in breadth first fashion
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# File 'lib/networkx/traversals/bfs.rb', line 11 def self.bfs_edges(graph, source) raise KeyError, "There exists no node names #{source} in the given graph." unless graph.node?(source) bfs_edges = [] visited = [source] queue = Queue.new.push([source, graph.neighbours(source)]) until queue.empty? parent, children = queue.pop children.each_key do |child| next if visited.include?(child) bfs_edges << [parent, child] visited << child queue.push([child, graph.neighbours(child)]) end end bfs_edges end |
.bfs_predecessors(graph, source) ⇒ Object
Returns predecessor child pair of the graph travelled in breadth first fashion
52 53 54 55 56 57 |
# File 'lib/networkx/traversals/bfs.rb', line 52 def self.bfs_predecessors(graph, source) bfs_edges = bfs_edges(graph, source) predecessors = {} bfs_edges.each { |u, v| predecessors[v] = u } predecessors end |
.bfs_successors(graph, source) ⇒ Object
Returns parent successor pair of the graph travelled in breadth first fashion
35 36 37 38 39 40 41 42 43 |
# File 'lib/networkx/traversals/bfs.rb', line 35 def self.bfs_successors(graph, source) bfs_edges = bfs_edges(graph, source) successors = {} bfs_edges.each do |u, v| successors[u] = [] if successors[u].nil? successors[u] << v end successors end |
.bidirectional_bfs(residual, source, target) ⇒ Object
Helper function for the bidirectional bfs
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
# File 'lib/networkx/flow/edmondskarp.rb', line 26 def self.bidirectional_bfs(residual, source, target) pred, succ = {source => nil}, {target => nil} q_s, q_t = [source], [target] loop do q = [] if q_s.length <= q_t.length q_s.each do |u| residual.adj[u].each do |v, uv_attrs| next unless !pred.include?(v) && (uv_attrs[:flow] < uv_attrs[:capacity]) pred[v] = u return [v, pred, succ] if succ.key?(v) q << v end end return [nil, nil, nil] if q.empty? else q_t.each do |u| residual.pred[u].each do |v, uv_attrs| next unless !succ.key?(v) && uv_attrs[:flow] < uv_attrs[:capacity] succ[v] = u return [v, pred, succ] if pred.key?(v) q << v end end return [nil, nil, nil] if q.empty? q_t = q end end end |
.build_flow_dict(graph, residual) ⇒ Hash{ Object => Hash{ Object => Numeric }] flowdict containing all the flow values in the edges
Build flow dictionary of a graph from its residual graph
151 152 153 154 155 156 157 158 159 |
# File 'lib/networkx/flow/utils.rb', line 151 def self.build_flow_dict(graph, residual) flow_dict = {} graph.edges.each do |u, u_edges| flow_dict[u] = {} u_edges.each_key { |v| flow_dict[u][v] = 0 } u_edges.each_key { |v| flow_dict[u][v] = residual[u][v][:flow] if residual[u][v][:flow] > 0 } end flow_dict end |
.build_residual_network(graph) ⇒ DiGraph
Builds a residual graph from a constituent graph
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
# File 'lib/networkx/flow/utils.rb', line 63 def self.build_residual_network(graph) raise NotImplementedError, 'MultiGraph and MultiDiGraph not supported!' if graph.multigraph? r_network = NetworkX::DiGraph.new(inf: 0, flow_value: 0) r_network.add_nodes(graph.nodes.keys) inf = Float::INFINITY edge_list = [] graph.adj.each do |u, u_edges| require 'spec_helper' RSpec.describe NetworkX::DiGraph do subject { graph } let(:graph) { described_class.new } before do graph.add_edge(1, 2) graph.add_edge(2, 4) end context 'when capacity_scaling is called' do subject { NetworkX.capacity_scaling(graph) } it { is_expected.to eq([0, {1=>{2=>0}, 2=>{4=>0}, 4=>{}}]) } end end u_edges.each do |v, uv_attrs| edge_list << [u, v, uv_attrs] if (uv_attrs[:capacity] || inf) > 0 && u != v end end inf_chk = 3 * edge_list.inject(0) do |result, arr| arr[2].key?(:capacity) && arr[2][:capacity] != inf ? (result + arr[2][:capacity]) : result end inf = inf_chk.zero? ? 1 : inf_chk if graph.directed? edge_list.each do |u, v, attrs| r = [attrs[:capacity] || inf, inf].min if r_network.adj[u][v].nil? r_network.add_edge(u, v, capacity: r) r_network.add_edge(v, u, capacity: 0) else r_network[u][v][:capacity] = r end end else edge_list.each do |u, v, attrs| r = [attrs[:capacity] || inf, inf].min r_network.add_edge(u, v, capacity: r) r_network.add_edge(v, u, capacity: r) end end r_network.graph[:inf] = inf r_network end |
.capacity_scaling(graph) ⇒ Array<Numeric, Hash{ Object => Hash{ Object => Numeric } }>
Computes max flow using capacity scaling algorithm
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 |
# File 'lib/networkx/flow/capacityscaling.rb', line 139 def self.capacity_scaling(graph) residual = _build_residual_network(graph) inf = Float::INFINITY flow_cost = 0 # TODO: Account cost of self-loof edges wmax = ([-inf] + residual.adj.each_with_object([]) do |u, arr| u[1].each { |_, key_attrs| key_attrs.each { |_, attrs| arr << attrs[:capacity] } } end).max return flow_cost, _build_flow_dict(graph, residual) if wmax == -inf r_nodes = residual.nodes r_adj = residual.adj delta = 2 ** Math.log2(wmax).floor while delta >= 1 r_nodes.each do |u, u_attrs| p_u = u_attrs[:potential] r_adj[u].each do |v, uv_edges| uv_edges.each do |_k, e| flow = e[:capacity] next unless e[:weight] - p_u + r_nodes[v][:potential] < 0 flow = e[:capacity] - e[:flow] next unless flow >= delta e[:flow] += flow r_adj[v][u].each_key do |val| val[:flow] += val[:temp_key][0] == e[:temp_key][0] && val[:temp_key][1] != e[:temp_key][1] ? -flow : 0 end r_nodes[u][:excess] -= flow r_nodes[v][:excess] += flow end end end s_set = Set.new t_set = Set.new residual.nodes.each do |u, _attrs| excess = r_nodes[u][:excess] if excess >= delta s_set.add(u) elsif excess <= -delta t_set.add(u) end end while !s_set.empty? && !t_set.empty? s = arbitrary_element t = nil d = {} pred = {s => nil} h = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) } h_dict = {s => 0} h << [0, count, s] until h.empty? d_u, _, u = h.pop h_dict.delete(u) d[u] = d_u if t_set.include?(u) t = u break end p_u = r_nodes[u][:potential] r_adj[u].each do |v, uv_edges| next if d.key?(v) wmin = inf uv_edges.each_value do |e| next unless e[:capacity] - e[:flow] >= delta w = e[:weight] next unless w < wmin wmin = w end next if wmin == inf d_v = d_u + wmin - p_u + r_nodes[v][:potential] next unless h_dict[v] > d_v h << [d_v, count, v] h_dict[v] = d_v pred[v] = [u, kmin, emin] end end if !t.nil? while u != s v = u u, k, e = pred[v] e[:flow] += delta r_adj[v][u].each_key do |val| val[:flow] += val[:temp_key][0] == k[0] && val[:temp_key][1] != k[1] ? -delta : 0 end end r_nodes[s][:excess] -= delta r_nodes[t][:excess] += delta s_set.delete(s) if r_nodes[s][:excess] < delta t_set.delete(t) if r_nodes[t][:excess] > -delta d_t = d[t] d.each { |node, d_u_node| r_nodes[node][:potential] -= (d_u_node - d_t) } else s_set.delete(s) end end delta = (delta / 2).floor end r_nodes.each_value { |attrs| raise ArgumentError, 'No flow satisfying all demands!' if attrs[:excess] != 0 } residual.nodes.each_key do |node| residual.adj[node].each_value do |uv_edges| uv_edges.each_value do |k_attrs| flow = k_attrs[:flow] flow_cost += (flow * k_attrs[:weight]) end end end [flow_cost, _build_flow_dict(graph, residual)] end |
.cartesian_product(g_1, g_2) ⇒ Graph, ...
Returns the cartesian product of two graphs
133 134 135 136 137 138 139 |
# File 'lib/networkx/operators/product.rb', line 133 def self.cartesian_product(g_1, g_2) g = init_product_graph(g_1, g_2) g.add_nodes(node_product(g_1, g_2)) g.add_edges(edges_cross_nodes(g_1, g_2)) g.add_edges(nodes_cross_edges(g_1, g_2)) g end |
.closeness_vitality(graph, node) ⇒ Numeric
Returns the closeness vitality of a node
8 9 10 11 12 |
# File 'lib/networkx/auxillary_functions/vitality.rb', line 8 def self.closeness_vitality(graph, node) before = wiener_index(graph) after = wiener_index(graph.subgraph(graph.nodes.keys - [node])) before - after end |
.complement(graph) ⇒ Graph, ...
Performs the complement operation on the graph
7 8 9 10 11 12 13 14 15 16 |
# File 'lib/networkx/operators/unary.rb', line 7 def self.complement(graph) result = Marshal.load(Marshal.dump(graph)) result.clear result.add_nodes(graph.nodes.map { |u, attrs| [u, attrs] }) graph.adj.each do |u, u_edges| graph.nodes.each { |v, attrs| result.add_edge(u, v, attrs) if !u_edges.key?(v) && u != v } end result end |
.compose(g_1, g_2) ⇒ Graph, ...
Performs the composition of two graphs
173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 |
# File 'lib/networkx/operators/binary.rb', line 173 def self.compose(g_1, g_2) result = Marshal.load(Marshal.dump(g_1)) result.clear raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph? result.add_nodes(g_1.nodes.map { |u, attrs| [u, attrs] }) result.add_nodes(g_2.nodes.map { |u, attrs| [u, attrs] }) if g_1.multigraph? g_1.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, attrs) } } } g_2.adj.each { |u, e| e.each { |v, uv_edges| uv_edges.each_value { |attrs| result.add_edge(u, v, attrs) } } } else g_1.adj.each { |u, u_edges| u_edges.each { |v, attrs| result.add_edge(u, v, attrs) } } g_2.adj.each { |u, u_edges| u_edges.each { |v, attrs| result.add_edge(u, v, attrs) } } end result end |
.compose_all(graphs) ⇒ Graph, ...
Performs the composition of many graphs
52 53 54 55 56 57 58 59 60 |
# File 'lib/networkx/operators/all.rb', line 52 def self.compose_all(graphs) raise ArgumentError, 'Argument array is empty' if graphs.empty? result = graphs.shift graphs.each do |graph| result = NetworkX.compose(result, graph) end result end |
.convert_to_distinct_labels(graph, starting_int = -1)) ⇒ Object
Transforms the labels of the nodes of the graphs so that they are disjoint.
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# File 'lib/networkx/operators/binary.rb', line 19 def self.convert_to_distinct_labels(graph, starting_int=-1) new_graph = Marshal.load(Marshal.dump(graph)) new_graph.clear idx_dict = Hash[graph.nodes.keys.map do |v| starting_int += 1 [v, starting_int] end] graph.nodes.each do |u, attrs| new_graph.add_node(u.to_s + idx_dict[u].to_s, attrs) end graph.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if graph.multigraph? uv_attrs.each do |_k, attrs| new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, attrs) end else new_graph.add_edge(u.to_s + idx_dict[u].to_s, v.to_s + idx_dict[v].to_s, uv_attrs) end end end new_graph end |
.count ⇒ Object
126 127 128 129 |
# File 'lib/networkx/flow/capacityscaling.rb', line 126 def self.count @itr += 1 @itr end |
.cycle_basis(graph, root = nil) ⇒ Array<Array<Object>>
Returns all basis cycles in graph
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# File 'lib/networkx/auxillary_functions/cycles.rb', line 10 def self.cycle_basis(graph, root=nil) gnodes = graph.nodes.keys cycles = [] until gnodes.empty? root = gnodes.shift if root.nil? stack = [root] pred = {root => root} used = {root => []} until stack.empty? z = stack.shift zused = used[z] graph.adj[z].each_key do |u| if !used.key?(u) pred[u] = z stack << u used[u] = [z] elsif u == z cycles << [z] elsif !zused.include?(u) pn = used[u] cycle = [u, z] p = pred[z] until pn.include?(p) cycle << p p = pred[p] end cycle << p cycles << cycle used[u] << z used[u] = used[u].uniq end end end gnodes -= pred.keys root = nil end cycles end |
.descendants(graph, source) ⇒ Array<Object>
Returns the descendants of a given node
8 9 10 11 12 |
# File 'lib/networkx/auxillary_functions/dag.rb', line 8 def self.descendants(graph, source) raise ArgumentError, 'Source is not present in the graph!' unless graph.node?(source) des = single_source_shortest_path_length(graph, source).map { |u, _| u }.uniq des - [source] end |
.detect_unboundedness(r_network, source, target) ⇒ Object
Detects unboundedness in a graph, raises exception when infinite capacity flow is found
129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
# File 'lib/networkx/flow/utils.rb', line 129 def self.detect_unboundedness(r_network, source, target) q = [source] seen = Set.new([source]) inf = r_network.graph[:inf] until q.empty? u = q.shift r_network.adj[u].each do |v, uv_attrs| next unless uv_attrs[:capacity] == inf && !seen.include?(v) raise ArgumentError, 'Infinite capacity flow!' if v == target seen << v q << v end end end |
.dfs_edges(graph, source, depth_limit = nil) ⇒ Object
Returns edges of the graph travelled in depth first fashion
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# File 'lib/networkx/traversals/dfs.rb', line 12 def self.dfs_edges(graph, source, depth_limit=nil) raise KeyError, "There exists no node names #{source} in the given graph." unless graph.node?(source) depth_limit = graph.nodes.length if depth_limit.nil? dfs_edges = [] visited = [source] stack = [[-1, source, depth_limit, graph.neighbours(source)]] until stack.empty? earlier_node, parent, depth_now, children = stack.pop dfs_edges << [earlier_node, parent] children.each_key do |child| unless visited.include?(child) visited << child stack.push([parent, child, depth_now - 1, graph.neighbours(child)]) if depth_now > 1 end end end dfs_edges.shift dfs_edges end |
.dfs_predecessors(graph, source, depth_limit = nil) ⇒ Object
Returns predecessor child pair of the graph travelled in depth first fashion
73 74 75 76 77 78 |
# File 'lib/networkx/traversals/dfs.rb', line 73 def self.dfs_predecessors(graph, source, depth_limit=nil) dfs_edges = dfs_edges(graph, source, depth_limit) predecessors = {} dfs_edges.each { |u, v| predecessors[v] = u } predecessors end |
.dfs_successors(graph, source, depth_limit = nil) ⇒ Object
Returns parent successor pair of the graph travelled in depth first fashion
55 56 57 58 59 60 61 62 63 |
# File 'lib/networkx/traversals/dfs.rb', line 55 def self.dfs_successors(graph, source, depth_limit=nil) dfs_edges = dfs_edges(graph, source, depth_limit) successors = {} dfs_edges.each do |u, v| successors[u] = [] if successors[u].nil? successors[u] << v end successors end |
.dfs_tree(graph, source, depth_limit = nil) ⇒ Object
Returns dfs tree of the graph
40 41 42 43 44 45 |
# File 'lib/networkx/traversals/dfs.rb', line 40 def self.dfs_tree(graph, source, depth_limit=nil) t = NetworkX::DiGraph.new t.add_node(source) t.add_edges_from(dfs_edges(graph, source, depth_limit)) t end |
.diameter(graph) ⇒ Numeric
Returns the diameter of a graph
24 25 26 |
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 24 def self.diameter(graph) eccentricity(graph).values.max end |
.difference(g_1, g_2) ⇒ Graph, ...
Performs the difference of two graphs
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
# File 'lib/networkx/operators/binary.rb', line 99 def self.difference(g_1, g_2) result = Marshal.load(Marshal.dump(g_1)) result.clear raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph? raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty? g_1.nodes.each { |u, attrs| result.add_node(u, attrs) } g_1.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if g_1.multigraph? uv_attrs.each do |k, attrs| result.add_edge(u, v, attrs) unless g_2.edge?(u, v, k) end else result.add_edge(u, v, uv_attrs) unless g_2.edge?(u, v) end end end result end |
.dijkstra_path(graph, source, target) ⇒ Numeric
Computes shortest path to target from the given node
158 159 160 161 |
# File 'lib/networkx/shortest_path/weighted.rb', line 158 def self.dijkstra_path(graph, source, target) _, path = singlesource_dijkstra(graph, source, target) path end |
.dijkstra_path_length(graph, source, target) ⇒ Numeric
Computes shortest path length to target from the given node
143 144 145 146 147 148 149 |
# File 'lib/networkx/shortest_path/weighted.rb', line 143 def self.dijkstra_path_length(graph, source, target) return 0 if source == target weight = get_weight(graph) length = help_dijkstra(graph, source, weight, nil, nil, nil, target) raise KeyError, 'Node not reachable!' unless length.key?(target) length[target] end |
.dijkstra_predecessor_distance(graph, source, cutoff = nil) ⇒ <Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>] predcessor hash and distance hash
Computes weighted shortest path length and predecessors
171 172 173 174 175 |
# File 'lib/networkx/shortest_path/weighted.rb', line 171 def self.dijkstra_predecessor_distance(graph, source, cutoff=nil) weight = get_weight(graph) pred = {source => []} [pred, help_dijkstra(graph, source, weight, pred, nil, cutoff)] end |
.directed_edges_cross_edges(g_1, g_2) ⇒ Object
Returns the product of directed edges with edges
44 45 46 47 48 49 50 51 52 |
# File 'lib/networkx/operators/product.rb', line 44 def self.directed_edges_cross_edges(g_1, g_2) result = [] edges_in_array(g_1).each do |u, v, c| edges_in_array(g_2) do |x, y, d| result << [[u, x], [v, y], hash_product(c, d)] end end result end |
.discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target) ⇒ Object
Helper function for discharging a node
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
# File 'lib/networkx/flow/preflowpush.rb', line 133 def self.discharge(u_node, is_phase_1, residual_nodes, residual_adj, height, levels, grt, source, target) height_val = residual_nodes[u_node][:height] curr_edge = residual_nodes[u_node][:curr_edge] next_height = height_val levels[height_val].active.delete(u_node) loop do v, attr = curr_edge.get if height_val == residual_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity] flow = [residual_nodes[u_node][:excess], attr[:capacity] - attr[:flow]].min push(u_node, v, flow, residual_nodes, residual_adj) activate(v, source, target, levels, residual_nodes) if residual_nodes[u_node][:excess].zero? levels[height_val].inactive.add(u_node) break end end begin curr_edge.move_to_next rescue StopIteration height_val = relabel(u_node, grt, residual_adj, residual_nodes, source, target, levels) if is_phase_1 && height_val >= n - 1 levels[height].active.add(u_node) break end next_height = height_val end end residual_nodes[u_node][:height] = height_val next_height end |
.disjoint_union(g_1, g_2) ⇒ Graph, ...
Performs the disjoint union of two graphs
236 237 238 239 240 241 242 243 |
# File 'lib/networkx/operators/binary.rb', line 236 def self.disjoint_union(g_1, g_2) new_g_1 = convert_to_distinct_labels(g_1) new_g_2 = convert_to_distinct_labels(g_2) result = union(new_g_1, new_g_2) result.graph.merge!(g_1.graph) result.graph.merge!(g_2.graph) result end |
.disjoint_union_all(graphs) ⇒ Graph, ...
Performs the disjoint union of many graphs
22 23 24 25 26 27 28 29 30 |
# File 'lib/networkx/operators/all.rb', line 22 def self.disjoint_union_all(graphs) raise ArgumentError, 'Argument array is empty' if graphs.empty? result = graphs.shift graphs.each do |graph| result = NetworkX.disjoint_union(result, graph) end result end |
.dist_path_lambda(_graph, _new_weight) ⇒ Object
Helper function to get distances
373 374 375 376 377 378 379 |
# File 'lib/networkx/shortest_path/weighted.rb', line 373 def self.dist_path_lambda(_graph, _new_weight) lambda do |graph, v, new_weight| paths = {v => [v]} _ = help_dijkstra(graph, v, new_weight, nil, paths) paths end end |
.eccentricity(graph, node = nil) ⇒ Array<Numeric>, Numeric
Returns the eccentricity of a particular node or all nodes
8 9 10 11 12 13 14 15 16 17 |
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 8 def self.eccentricity(graph, node=nil) e = {} graph.nodes.each do |u, _| length = single_source_shortest_path_length(graph, u) l = length.length raise ArgumentError, 'Found infinite path length!' unless l == graph.nodes.length e[u] = length.max_by { |a| a[1] }[1] end node.nil? ? e : e[node] end |
.edge_dfs(graph, start, orientation = nil) ⇒ Object
Performs edge dfs on the graph Orientation :ignore, directed edges can be travelled in both fashions Orientation reverse, directed edges can be travelled in reverse fashion Orientation :nil, the graph is not meddled with
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
# File 'lib/networkx/traversals/edge_dfs.rb', line 54 def self.edge_dfs(graph, start, orientation=nil) case orientation when :reverse graph = graph.reverse if graph.class.name == 'NetworkX::DiGraph' || graph.class.name == 'NetworkX::MultiDiGraph' when :ignore graph = graph.to_undirected if graph.class.name == 'NetworkX::DiGraph' graph = graph.to_multigraph if graph.class.name == 'NetworkX::MultiDiGraph' end visited_edges = [] visited_nodes = [] stack = [start] current_edges = {} e = Enumerator.new do |yield_var| until stack.empty? current = stack.last unless visited_nodes.include?(current) current_edges[current] = out_edges(graph, current) visited_nodes << current end edge = current_edges[current].shift if edge.nil? stack.pop else unless visited_edges.include?(edge_id(graph, edge)) visited_edges << edge_id(graph, edge) stack << edge[1] yield_var.yield edge end end end end e.take(graph.number_of_edges) end |
.edge_id(graph, edge) ⇒ Object
Helper function of edge_dfs
33 34 35 36 37 |
# File 'lib/networkx/traversals/edge_dfs.rb', line 33 def self.edge_id(graph, edge) return edge if graph.directed? return Set.new([edge, (edge[0..1].reverse + edge[2])]) if graph.multigraph? Set.new([edge, edge.reverse]) end |
.edges_cross_nodes(g_1, g_2) ⇒ Object
Returns the product of edges with edges
66 67 68 69 70 71 72 73 74 |
# File 'lib/networkx/operators/product.rb', line 66 def self.edges_cross_nodes(g_1, g_2) result = [] edges_in_array(g_1).each do |u, v, d| g_2.nodes.keys.each do |x| result << [[u, x], [v, x], d] end end result end |
.edges_cross_nodes_and_nodes(g_1, g_2) ⇒ Object
Returns the product of edges with pairs of nodes
88 89 90 91 92 93 94 95 96 97 98 |
# File 'lib/networkx/operators/product.rb', line 88 def self.edges_cross_nodes_and_nodes(g_1, g_2) result = [] edges_in_array(g_1).each do |u, v, d| g_2.nodes.keys.each do |x| g_2.nodes.keys.each do |y| result << [[u, x], [v, y], d] end end end result end |
.edges_in_array(graph) ⇒ Object
Returns the edges of the graph in an array
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# File 'lib/networkx/operators/product.rb', line 7 def self.edges_in_array(graph) edge_array = [] if graph.multigraph? graph.adj.each do |u, u_edges| u_edges.each do |v, uv_edges| uv_edges.each do |_k, attrs| edge_array << [u, v, attrs] end end end else graph.adj.each do |u, u_edges| u_edges.each do |v, attrs| edge_array << [u, v, attrs] end end end edge_array end |
.edmondskarp(graph, source, target, residual = nil, cutoff = nil) ⇒ DiGraph
Computes max flow using edmonds karp algorithm
110 111 112 |
# File 'lib/networkx/flow/edmondskarp.rb', line 110 def self.edmondskarp(graph, source, target, residual=nil, cutoff=nil) edmondskarp_impl(graph, source, target, residual, cutoff) end |
.edmondskarp_core(residual, source, target, cutoff) ⇒ Object
Core helper function for the EdmondsKarp algorithm
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
# File 'lib/networkx/flow/edmondskarp.rb', line 59 def self.edmondskarp_core(residual, source, target, cutoff) inf = residual.graph[:inf] flow_val = 0 while flow_val < cutoff v, pred, succ = bidirectional_bfs(residual, source, target) break if pred.nil? path = [v] u = v while u != source u = pred[u] path << u end path.reverse! u = v while u != target u = succ[u] path << u end flow_val += augment(residual, inf, path) end flow_val end |
.edmondskarp_impl(graph, source, target, residual, cutoff) ⇒ Object
Helper function for the edmondskarp function
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
# File 'lib/networkx/flow/edmondskarp.rb', line 85 def self.edmondskarp_impl(graph, source, target, residual, cutoff) raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source) raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target) raise ArgumentError, 'Source and target are same node!' if source == target res_graph = residual.nil? ? build_residual_network(graph) : residual.clone res_graph.adj.each do |u, u_edges| u_edges.each do |v, _attrs| res_graph.adj[u][v][:flow] = 0 res_graph.pred[v][u][:flow] = 0 end end cutoff = Float::INFINITY if cutoff.nil? res_graph.graph[:flow_val] = edmondskarp_core(res_graph, source, target, cutoff) res_graph end |
.find_cliques(graph) ⇒ Array<Array<Object>>
Returns all cliques in the graph
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
# File 'lib/networkx/auxillary_functions/cliques.rb', line 9 def self.find_cliques(graph) return nil if graph.nodes.empty? q = [nil] adj = {} graph.nodes.each_key { |u| adj[u] = [] } graph.adj.each { |u, u_edges| u_edges.each_key { |v| adj[u] << v if u != v } } subg = graph.nodes.keys cand = graph.nodes.keys u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length } ext_u = cand - adj[u] stack = [] cliques = [] begin loop do if !ext_u.empty? q_elem = ext_u.pop cand.delete(q_elem) q[-1] = q_elem adj_q = adj[q_elem] subg_q = subg & adj_q if subg_q.empty? cliques << q[0..(q.length - 1)] else cand_q = cand & adj_q unless cand_q.empty? stack << [subg, cand, ext_u] q << nil subg = subg_q cand = cand_q u = subg.max { |n_1, n_2| (cand & adj[n_1]).length <=> (cand & adj[n_2]).length } ext_u = cand - adj[u] end end else q.pop subg, cand, ext_u = stack.pop end end rescue NoMethodError return cliques end end |
.find_cycle(graph, node) ⇒ Array<Array<Object>>
Returns the cycle containing the given node
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
# File 'lib/networkx/auxillary_functions/cycles.rb', line 57 def self.find_cycle(graph, node) explored = Set.new cycle = [] final_node = nil unless explored.include?(node) edges = [] seen = [node] active_nodes = [node] previous_head = nil edge_dfs(graph, node).each do |edge| tail, head = edge next if explored.include?(head) if !previous_head.nil? && tail != previous_head loop do popped_edge = edges.pop if popped_edge.nil? edges = [] active_nodes = [tail] break else popped_head = popped_edge[1] active_nodes.delete!(popped_head) end unless edges.empty? last_head = edges[-1][1] break if tail == last_head end end end edges << edge if active_nodes.include?(head) cycle += edges final_node = head break else seen << head active_nodes << head previous_head = head end end cycle.each_with_index { |edge, i| return cycle[i..(cycle.length - 1)] if final_node == edge[0] } end raise ArgumentError, 'No cycle found!' if cycle.empty? end |
.floyd_warshall(graph) ⇒ Hash{ Object => { Object => { Numeric }}}
Returns the all pair distance between all the nodes
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# File 'lib/networkx/shortest_path/dense.rb', line 10 def self.floyd_warshall(graph) a, index = to_matrix(graph, Float::INFINITY, 'min') nodelen = graph.nodes.length (0..(nodelen - 1)).each { |i| a[i, i] = 0 } (0..(nodelen - 1)).each do |k| (0..(nodelen - 1)).each do |i| (0..(nodelen - 1)).each do |j| a[i, j] = [a[i, j], a[i, k] + a[k, j]].min end end end as_hash = {} (0..(nodelen - 1)).each do |i| (0..(nodelen - 1)).each do |j| as_hash[index[i]] = {} unless as_hash.key?(index[i]) as_hash[index[i]][index[j]] = a[i, j] end end as_hash end |
.gap_heuristic(height, levels, residual_nodes) ⇒ Object
Helper function for applying gap heuristic
168 169 170 171 172 173 174 175 176 177 178 |
# File 'lib/networkx/flow/preflowpush.rb', line 168 def self.gap_heuristic(height, levels, residual_nodes) ((height + 1)..(max_height)).each do |idx| level = levels[idx] level.active.each { |u| residual_nodes[u][:height] = n + 1 } level.inactive.each { |u| residual_nodes[u][:height] = n + 1 } levels[n + 1].active.merge!(level.active) level.active.clear levels[n + 1].inactive.merge!(level.inactive) level.inactive.clear end end |
.generate_unique_node ⇒ Object
Returns a label for unique node
5 6 7 |
# File 'lib/networkx/flow/capacityscaling.rb', line 5 def self.generate_unique_node SecureRandom.uuid end |
.get_edges(graph) ⇒ Object
Returns the edges of the graph in an array
5 6 7 8 9 10 11 12 13 |
# File 'lib/networkx/operators/binary.rb', line 5 def self.get_edges(graph) edges = [] graph.adj.each do |u, u_attrs| u_attrs.each do |v, uv_attrs| edges << [u, v, uv_attrs] end end edges end |
.get_edges_weights(graph) ⇒ Object
Helper function for the minimum spanning tree
4 5 6 7 8 9 10 11 12 |
# File 'lib/networkx/auxillary_functions/mst.rb', line 4 def self.get_edges_weights(graph) edges = [] graph.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| edges << [[u, v], uv_attrs[:weight] || Float::INFINITY] end end edges end |
.get_sources(graph) ⇒ Object
Helper function to get sources
368 369 370 |
# File 'lib/networkx/shortest_path/weighted.rb', line 368 def self.get_sources(graph) graph.nodes.collect { |k, _v| k } end |
.get_weight(graph) ⇒ Object
Helper function to extract weight from a adjecency hash
5 6 7 8 9 10 11 |
# File 'lib/networkx/shortest_path/weighted.rb', line 5 def self.get_weight(graph) weight_get = lambda do |_, _, attrs| return attrs[:weight] || 1 unless graph.multigraph? attrs.group_by { |_k, vals| vals[:weight] || 1 }.keys.max end weight_get end |
.global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred) ⇒ Object
Helper function for global relabel heuristic
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |
# File 'lib/networkx/flow/preflowpush.rb', line 183 def self.global_relabel(from_sink, source, target, residual_nodes, num, levels, residual_pred) src = from_sink ? target : source heights = reverse_bfs(src, residual_pred) heights.delete(target) unless from_sink max_height = heights.values.max if from_sink residual_nodes.each { |u, attr| heights[u] = num + 1 if !heights.key?(u) && attr[:height] < num } else heights.each_key { |u| heights[u] += num } max_height += num end heights.delete(src) heights.each do |u, new_height| old_height = residual_nodes[u][:height] next unless new_height != old_height if levels[old_height].active.include?(u) levels[old_height].active.delete(u) levels[new_height].active.add(u) else levels[old_height].inactive.delete(u) levels[new_height].inactive.add(u) end residual_nodes[u][:height] = new_height end max_height end |
.graph_to_csv(graph, filename = 'graph.csv') ⇒ Object
Saves the graph in a csv file
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# File 'lib/networkx/converters/to_csv.rb', line 8 def self.graph_to_csv(graph, filename='graph.csv') CSV.open(filename, 'wb') do |csv| csv << [graph.class.name] csv << ['graph_values'] csv << graph.graph.keys csv << graph.graph.values csv << ['graph_nodes'] graph.nodes.each do |u, attrs| node_attrs = [u] attrs.each do |k, v| node_attrs << k node_attrs << v end csv << node_attrs end csv << ['graph_edges'] graph.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if graph.multigraph? uv_attrs.each do |key, attrs| node_attrs = [u, v, key] attrs.each do |k, k_attrs| node_attrs << k node_attrs << k_attrs end csv << node_attrs end else node_attrs = [u, v] uv_attrs.each do |k, vals| node_attrs << k node_attrs << vals end csv << node_attrs end end end end end |
.graph_to_json(graph) ⇒ JSON
Returns a JSON object of the given graph
7 8 9 10 11 12 13 14 |
# File 'lib/networkx/converters/to_json.rb', line 7 def self.graph_to_json(graph) json_hash = {} json_hash[:class] = graph.class.name json_hash[:graph] = graph.graph json_hash[:nodes] = graph.nodes json_hash[:adj] = graph.adj json_hash.to_json end |
.hash_product(hash_1, hash_2) ⇒ Object
Returns the hash product of two hashes
28 29 30 |
# File 'lib/networkx/operators/product.rb', line 28 def self.hash_product(hash_1, hash_2) Hash[(hash_1.keys | hash_2.keys).map { |n| [n, [hash_1[n], hash_2[n]]] }] end |
.help_bellman_ford(graph, sources, weight, pred = nil, paths = nil, dist = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for bellman ford
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 |
# File 'lib/networkx/shortest_path/weighted.rb', line 217 def self.help_bellman_ford(graph, sources, weight, pred=nil, paths=nil, dist=nil, cutoff=nil, target=nil) pred = sources.product([[]]).to_h if pred.nil? dist = sources.product([0]).to_h if dist.nil? inf, n, count, q, in_q = Float::INFINITY, graph.nodes.length, {}, sources.clone, Set.new(sources) until q.empty? u = q.shift in_q.delete(u) skip = false pred[u].each { |k| skip = true if in_q.include?(k) } next if skip dist_u = dist[u] graph.adj[u].each do |v, e| dist_v = dist_u + weight.call(u, v, e) next if !cutoff.nil? && dist_v > cutoff next if !target.nil? && dist_v > (dist[target] || inf) if dist_v < (dist[v] || inf) unless in_q.include?(v) q << v in_q.add(v) count_v = (count[v] || 0) + 1 raise ArgumentError, 'Negative edge cycle detected!' if count_v == n count[v] = count_v end dist[v] = dist_v pred[v] = [u] elsif dist.key?(v) && dist_v == dist[v] pred[v] << u end end end unless paths.nil? dsts = target.nil? ? pred : [target] dsts.each_key do |dst| path, cur = [dst], dst until pred[cur][0].nil? cur = pred[cur][0] path << cur end path.reverse paths[dst] = path end end dist end |
.help_dijkstra(graph, source, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for single source dijkstra
53 54 55 |
# File 'lib/networkx/shortest_path/weighted.rb', line 53 def self.help_dijkstra(graph, source, weight, pred=nil, paths=nil, cutoff=nil, target=nil) help_multisource_dijkstra(graph, [source], weight, pred, paths, cutoff, target) end |
.help_multisource_dijkstra(graph, sources, weight, pred = nil, paths = nil, cutoff = nil, target = nil) ⇒ Object
Helper function for multisource dijkstra
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# File 'lib/networkx/shortest_path/weighted.rb', line 16 def self.help_multisource_dijkstra(graph, sources, weight, pred=nil, paths=nil, cutoff=nil, target=nil) count = ->(i) { i + 1 } i = -1 dist = {} seen = {} fringe = Heap.new { |x, y| x[0] < y[0] || (x[0] == y[0] && x[1] < y[1]) } sources.each do |s| seen[s] = 0 fringe << [0, count.call(i), s] end until fringe.empty? d, _, v = fringe.pop next if dist.key?(v) dist[v] = d break if v == target graph.adj[v].each do |u, attrs| cost = weight.call(v, u, attrs) next if cost.nil? vu_dist = dist[v] + cost next if !cutoff.nil? && vu_dist > cutoff if dist.key?(u) raise ValueError, 'Contradictory weights found!' if vu_dist < dist[u] elsif !seen.key?(u) || vu_dist < seen[u] seen[u] = vu_dist fringe << [vu_dist, count.call(i), u] paths[u] = paths[v] + [u] unless paths.nil? pred[u] = [v] unless pred.nil? elsif vu_dist == seen[u] pred[u] << v unless pred.nil? end end end dist end |
.help_single_shortest_path(adj, firstlevel, paths, cutoff) ⇒ Object
Helper function for finding single source shortest path
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 56 def self.help_single_shortest_path(adj, firstlevel, paths, cutoff) level = 0 nextlevel = firstlevel while !nextlevel.empty? && cutoff > level thislevel = nextlevel nextlevel = {} thislevel.each_key do |u| adj[u].each_key do |v| unless paths.key?(v) paths[v] = paths[u] + [v] nextlevel[v] = 1 end end end level += 1 end paths end |
.help_single_shortest_path_length(adj, firstlevel, cutoff) ⇒ Object
Helper function for single source shortest path length
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 5 def self.help_single_shortest_path_length(adj, firstlevel, cutoff) iterator = Enumerator.new do |e| seen = {} level = 0 nextlevel = firstlevel while !nextlevel.empty? && cutoff >= level thislevel = nextlevel nextlevel = {} thislevel.each do |u, _attrs| next if seen.key?(u) seen[u] = level nextlevel.merge!(adj[u]) e.yield [u, level] end level += 1 end seen.clear end iterator end |
.hits(graph, max_iter = 100, tol = 1e-8, nstart) ⇒ Array<Numeric, Numeric>
Computes hits and authority scores for all the graphs
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
# File 'lib/networkx/link_analysis/hits.rb', line 12 def self.hits(graph, max_iter=100, tol=1e-8, nstart) return [{}, {}] if graph.nodes.empty? h = nstart sum = h.values.inject(:+) h.each_key { |k| h[k] /= (sum * 1.0) } i = 0 a = {} loop do hlast = Marshal.load(Marshal.dump(h)) h, a = {}, {} hlast.each do |k, _v| h[k] = 0 a[k] = 0 end h.each_key { |k| graph.adj[k].each { |nbr, attrs| a[k] += hlast[nbr] * (attrs[:weight] || 1) } } h.each_key { |k| graph.adj[k].each { |nbr, attrs| h[k] += a[nbr] * (attrs[:weight] || 1) } } smax = h.values.max h.each_key { |k| h[k] /= smax } smax = a.values.max a.each_key { |k| a[k] /= smax } break if h.keys.map { |k| (h[k] - hlast[k]).abs }.inject(:+) < tol raise ArgumentError, 'Power Iteration failed to converge!' if i > max_iter i += 1 end [h, a] end |
.hub_matrix(graph) ⇒ NMatrix
Computes hub matrix for the graph
55 56 57 58 |
# File 'lib/networkx/link_analysis/hits.rb', line 55 def self.hub_matrix(graph) matrix, = to_matrix(graph, 0) matrix.dot matrix.transpose end |
.init_product_graph(g_1, g_2) ⇒ Object
Initializes the product graph
101 102 103 104 105 106 107 108 109 110 111 |
# File 'lib/networkx/operators/product.rb', line 101 def self.init_product_graph(g_1, g_2) raise ArgumentError, 'Arguments must be both directed or undirected!' unless g_1.directed? == g_2.directed? g = if g_1.multigraph? || g_2.multigraph? NetworkX::MultiGraph.new else NetworkX::Graph.new end g = g.to_directed if g.directed? g end |
.intersection(g_1, g_2) ⇒ Graph, ...
Performs the intersection of two graphs
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
# File 'lib/networkx/operators/binary.rb', line 54 def self.intersection(g_1, g_2) result = Marshal.load(Marshal.dump(g_1)) result.clear raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph? raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty? g_1.nodes.each { |u, attrs| result.add_node(u, attrs) } if g_1.number_of_edges <= g_2.number_of_edges g_1.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if g_1.multigraph? uv_attrs.each do |k, attrs| result.add_edge(u, v, attrs) if g_2.edge?(u, v, k) end elsif g_2.edge?(u, v) result.add_edge(u, v, uv_attrs) end end end else g_2.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if g_2.multigraph? uv_attrs.each do |k, attrs| result.add_edge(u, v, attrs) if g_1.edge?(u, v, k) end elsif g_1.edge?(u, v) result.add_edge(u, v, uv_attrs) end end end end result end |
.intersection_all(graphs) ⇒ Graph, ...
Performs the intersection of many graphs
37 38 39 40 41 42 43 44 45 |
# File 'lib/networkx/operators/all.rb', line 37 def self.intersection_all(graphs) raise ArgumentError, 'Argument array is empty' if graphs.empty? result = graphs.shift graphs.each do |graph| result = NetworkX.intersection(result, graph) end result end |
.johnson(graph) ⇒ Array<Object, Hash { Object => Array<Object> }] shortest paths between all pairs of nodes
Returns shortest path between all pairs of nodes
395 396 397 398 399 400 401 402 403 404 405 406 407 |
# File 'lib/networkx/shortest_path/weighted.rb', line 395 def self.johnson(graph) dist, pred = {}, {} sources = get_sources(graph) graph.nodes.each_key do |n| dist[n], pred[n] = 0, [] end weight = get_weight(graph) dist_bellman = help_bellman_ford(graph, sources, weight, pred, nil, dist=dist) new_weight = ->(u, v, d) { weight.call(u, v, d) + dist_bellman[u] - dist_bellman[v] } dist_path = dist_path_lambda(graph, new_weight) path_lengths = set_path_lengths_johnson(graph, dist_path, new_weight) path_lengths end |
.json_to_graph(json_str) ⇒ Graph, ...
Returns a graph from the json encoded graph
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
# File 'lib/networkx/converters/to_json.rb', line 23 def self.json_to_graph(json_str) graph_hash = JSON.parse(json_str) case json_str['class'] when 'NetworkX::Graph' graph = NetworkX::Graph.new(graph_hash.graph) when 'NetworkX::MultiGraph' graph = NetworkX::MultiGraph.new(graph_hash.graph) when 'NetworkX::DiGraph' graph = NetworkX::DiGraph.new(graph_hash.graph) when 'NetworkX::MultiDiGraph' graph = NetworkX::MultiDiGraph.new(graph_hash.graph) end graph.adj = graph_hash['adj'] graph.nodes = graph_hash['nodes'] graph end |
.lexicographic_product(g_1, g_2) ⇒ Graph, ...
Returns the lexicographic product of two graphs
147 148 149 150 151 152 153 |
# File 'lib/networkx/operators/product.rb', line 147 def self.lexicographic_product(g_1, g_2) g = init_product_graph(g_1, g_2) g.add_nodes(node_product(g_1, g_2)) g.add_edges(edges_cross_nodes_and_nodes(g_1, g_2)) g.add_edges(nodes_cross_edges(g_1, g_2)) g end |
.maximal_independent_set(graph, nodes) ⇒ Numeric
Returns the maximal independent set of a graph
10 11 12 13 14 15 16 17 18 19 20 21 22 |
# File 'lib/networkx/auxillary_functions/mis.rb', line 10 def self.maximal_independent_set(graph, nodes) raise 'The array containing the nodes should be a subset of the graph!' if (graph.nodes.keys - nodes).empty? neighbours = [] nodes.each { |u| graph.adj[u].each { |v, _| neighbours |= [v] } } raise 'Nodes is not an independent set of graph!' if (neighbours - nodes).empty? available_nodes = graph.nodes.keys - (neighbours | nodes) until available_nodes.empty? node = available_nodes.sample nodes << node available_nodes -= (graph.adj[node].keys + [node]) end nodes end |
.minimum_spanning_tree(graph) ⇒ DiGraph, Graph
Returns the minimum spanning tree of a graph
21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
# File 'lib/networkx/auxillary_functions/mst.rb', line 21 def self.minimum_spanning_tree(graph) mst = Marshal.load(Marshal.dump(graph)) mst.clear edges = get_edges_weights(graph).sort_by { |a| a[1] } union_find = UnionFind.new(graph.nodes.keys) while edges.any? && mst.nodes.length <= graph.nodes.length edge = edges.shift unless union_find.connected?(edge[0][0], edge[0][1]) union_find.union(edge[0][0], edge[0][1]) mst.add_edge(edge[0][0], edge[0][1], graph.adj[edge[0][0]][edge[0][1]]) end end mst end |
.multisource_dijkstra(graph, sources, target = nil, cutoff = nil) ⇒ Numeric, Array<Object>
Computes shortest paths and path lengths to a target from one of the nodes
65 66 67 68 69 70 71 72 73 74 75 |
# File 'lib/networkx/shortest_path/weighted.rb', line 65 def self.multisource_dijkstra(graph, sources, target=nil, cutoff=nil) raise ValueError, 'Sources cannot be empty' if sources.empty? return [0, [target]] if sources.include?(target) paths = {} weight = get_weight(graph) sources.each { |source| paths[source] = [source] } dist = help_multisource_dijkstra(graph, sources, weight, nil, paths, cutoff, target) return [dist, paths] if target.nil? raise KeyError, "No path to #{target}!" unless dist.key?(target) [dist[target], paths[target]] end |
.multisource_dijkstra_path(graph, sources, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Computes shortest paths to any from the given nodes
97 98 99 100 |
# File 'lib/networkx/shortest_path/weighted.rb', line 97 def self.multisource_dijkstra_path(graph, sources, cutoff=nil) _, path = multisource_dijkstra(graph, sources, nil, cutoff) path end |
.multisource_dijkstra_path_length(graph, sources, cutoff = nil) ⇒ Hash{ Object => Numeric }
Computes shortest path lengths to any from the given nodes
84 85 86 87 88 |
# File 'lib/networkx/shortest_path/weighted.rb', line 84 def self.multisource_dijkstra_path_length(graph, sources, cutoff=nil) raise ValueError, 'Sources cannot be empty' if sources.empty? weight = get_weight(graph) help_multisource_dijkstra(graph, sources, weight, nil, nil, cutoff) end |
.negative_edge_cycle(graph) ⇒ Boolean
Finds if there is a negative edge cycle in the graph
14 15 16 17 18 19 20 21 22 23 24 25 |
# File 'lib/networkx/flow/capacityscaling.rb', line 14 def self.negative_edge_cycle(graph) newnode = generate_unique_node graph.add_edges(graph.nodes.keys.map { |n| [newnode, n] }) begin bellmanford_predecesor_distance(graph, newnode) rescue ArgumentError return true ensure graph.remove_node(newnode) end false end |
.node_product(g_1, g_2) ⇒ Object
Returns the node product of nodes of two graphs
33 34 35 36 37 38 39 40 41 |
# File 'lib/networkx/operators/product.rb', line 33 def self.node_product(g_1, g_2) n_product = [] g_1.nodes.each do |k_1, attrs_1| g_2.nodes.each do |k_2, attrs_2| n_product << [[k_1, k_2], hash_product(attrs_1, attrs_2)] end end n_product end |
.nodes_cross_edges(g_1, g_2) ⇒ Object
Returns the product of directed nodes with edges
77 78 79 80 81 82 83 84 85 |
# File 'lib/networkx/operators/product.rb', line 77 def self.nodes_cross_edges(g_1, g_2) result = [] g_1.nodes.keys.each do |x| edges_in_array(g_2).each do |u, v, d| result << [[x, u], [x, v], d] end end result end |
.number_of_cliques(graph, node) ⇒ Numeric
Returns the number of cliques in a graph containing a node
59 60 61 62 63 64 |
# File 'lib/networkx/auxillary_functions/cliques.rb', line 59 def self.number_of_cliques(graph, node) cliques = find_cliques(graph) num_cliq_arr = [] cliques.each { |c| num_cliq_arr << 1 if c.include?(node) } num_cliq_arr.length end |
.out_edges(graph, node) ⇒ Object
Helper function for edge_dfs
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# File 'lib/networkx/traversals/edge_dfs.rb', line 8 def self.out_edges(graph, node) edges = [] visited = {} case graph.class.name when 'NetworkX::Graph', 'NetworkX::DiGraph' graph.adj[node].each do |v, _| if graph.class.name == 'NetworkX::DiGraph' || visited[[v, node]].nil? visited[[node, v]] = true edges << [node, v] end end else graph.adj[node].each do |v, uv_keys| uv_keys.each_key do |k| if graph.class.name == 'NetworkX::MultiDiGraph' || visited[[v, node, k]].nil? visited[[node, v, k]] = true edges << [node, v, k] end end end end edges end |
.pagerank(graph, init, alpha = 0.85, eps = 1e-4, max_iter = 100) ⇒ Array<Numeric>
Computes pagerank values for the graph
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# File 'lib/networkx/link_analysis/pagerank.rb', line 13 def self.pagerank(graph, init, alpha=0.85, eps=1e-4, max_iter=100) dim = graph.nodes.length raise ArgumentError, 'Init array needs to have same length as number of graph nodes!'\ unless dim == init.length matrix = [] elem_ind = {} p = [] curr = init.values init.keys.each_with_index { |n, i| elem_ind[n] = i } graph.adj.each do |_u, u_edges| adj_arr = Array.new(dim, 0) u_edges.each do |v, _| adj_arr[elem_ind[v]] = 1 end matrix << adj_arr end (0..(dim - 1)).each do |i| p[i] = [] (0..(dim - 1)).each { |j| p[i][j] = matrix[i][j] / (matrix[i].inject(:+) * 1.0) } end max_iter.times do |_| prev = curr.clone dim.times do |i| ip = 0 dim.times { |j| ip += p.transpose[i][j] * prev[j] } curr[i] = (alpha * ip) + (1 - alpha) / (dim * 1.0) end err = 0 dim.times { |i| err += (prev[i] - curr[i]).abs } return curr if err < eps end raise ArgumentError, 'PageRank failed to converge!' end |
.power(graph, pow) ⇒ Graph, ...
Returns the specified power of the graph
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
# File 'lib/networkx/operators/product.rb', line 179 def self.power(graph, pow) raise ArgumentError, 'Power must be a positive quantity!' if pow <= 0 result = NetworkX::Graph.new result.add_nodes(graph.nodes.map { |n, attrs| [n, attrs] }) graph.nodes.each do |n, _attrs| seen = {} level = 1 next_level = graph.adj[n] until next_level.empty? this_level = next_level next_level = {} this_level.each do |v, _attrs| next if v == n unless seen.key?(v) seen[v] = level next_level.merge!(graph.adj[v]) end end break if pow <= level level += 1 end result.add_edges(seen.map { |v, _| [n, v] }) end result end |
.predecessor(graph, source, cutoff = nil, return_seen = false) ⇒ Array<Hash{ Object => Array<Object> }, Hash{ Object => Numeric }>, Hash{ Object => Array<Object> }
Computes shortest paths to all nodes from all nodes
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 114 def self.predecessor(graph, source, cutoff=nil, return_seen=false) raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source) level = 0 nextlevel = [source] seen = {source => level} pred = {source => []} until nextlevel.empty? level += 1 thislevel = nextlevel nextlevel = [] thislevel.each do |u| graph.adj[u].each_key do |v| if !seen.key?(v) pred[v] = [u] seen[v] = level nextlevel << v elsif seen[v] == level pred[v] << u end end end break if cutoff.nil? && cutoff <= level end return_seen ? [pred, seen] : pred end |
.preflowpush(graph, source, target, residual = nil, globalrelabel_freq = 1, value_only = false) ⇒ DiGraph
Computes max flow using preflow push algorithm
249 250 251 |
# File 'lib/networkx/flow/preflowpush.rb', line 249 def self.preflowpush(graph, source, target, residual=nil, globalrelabel_freq=1, value_only=false) preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only) end |
.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only) ⇒ Object
Helper function to apply the preflow push algorithm
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
# File 'lib/networkx/flow/preflowpush.rb', line 12 def self.preflowpush_impl(graph, source, target, residual, globalrelabel_freq, value_only) raise ArgumentError, 'Source not in graph!' unless graph.nodes.key?(source) raise ArgumentError, 'Target not in graph!' unless graph.nodes.key?(target) raise ArgumentError, 'Source and Target are same!' if source == target globalrelabel_freq = 0 if globalrelabel_freq.nil? raise ArgumentError, 'Global Relabel Freq must be nonnegative!' if globalrelabel_freq < 0 r_network = residual.nil? ? build_residual_network(graph) : residual detect_unboundedness(r_network, source, target) residual_nodes = r_network.nodes residual_adj = r_network.adj residual_pred = r_network.pred residual_nodes.each do |u, u_attrs| u_attrs[:excess] = 0 residual_adj[u].each { |_v, attrs| attrs[:flow] = 0 } end heights = reverse_bfs(target, residual_pred) unless heights.key?(source) r_network.graph[:flow_value] = 0 return r_network end n = r_network.nodes.length max_height = heights.map { |u, h| u == source ? -1 : h }.max heights[source] = n grt = GlobalRelabelThreshold.new(n, r_network.size, globalrelabel_freq) residual_nodes.each do |u, u_attrs| u_attrs[:height] = heights.key?(u) ? heights[u] : (n + 1) u_attrs[:curr_edge] = CurrentEdge.new(residual_adj[u]) end residual_adj[source].each do |u, attr| flow = attr[:capacity] push(source, u, flow, residual_nodes, residual_adj) if flow > 0 end levels = (0..(2 * n - 1)).map { |_| Level.new } residual_nodes.each do |u, attr| if u != source && u != target level = levels[attr[:height]] residual_nodes[u][:excess] > 0 ? level.active.add(u) : level.inactive.add(u) end end height = max_height while height > 0 loop do level = levels[height] if level.active.empty? height -= 1 break end old_height = height old_level = level u = arbitrary_element(level.active) height = discharge(u, true, residual_nodes, residual_adj, height, levels, grt, source, target) if grt.reached? height = global_relabel(true, source, target, residual_nodes, n, levels, residual_pred) max_height = height grt.clear_work elsif old_level.active.empty? && old_level.inactive.empty? gap_heuristic(old_height, levels, residual_nodes) height = old_height - 1 max_height = height else max_height = [max_height, height].max end end end if value_only r_network.graph[:flow_value] = residual_nodes[target][:excess] return r_network end height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred) grt.clear_work while height > n loop do level = levels[height] if level.active.empty? height -= 1 break end u = arbitrary_element(level.active) height = discharge(u, false, residual_nodes, residual_adj, height, levels, grt, source, target) if grt.reached? height = global_relabel(false, source, target, residual_nodes, n, levels, residual_pred) grt.clear_work end end end r_network.graph[:flow_value] = residual_nodes[target][:excess] r_network end |
.push(node_1, node_2, flow, residual_nodes, residual_adj) ⇒ Object
Helper function for augmenting flow
211 212 213 214 215 216 |
# File 'lib/networkx/flow/preflowpush.rb', line 211 def self.push(node_1, node_2, flow, residual_nodes, residual_adj) residual_adj[node_1][node_2][:flow] += flow residual_adj[node_2][node_1][:flow] -= flow residual_nodes[node_1][:excess] -= flow residual_nodes[node_2][:excess] += flow end |
.radius(graph) ⇒ Numeric
Returns the radius of a graph
33 34 35 |
# File 'lib/networkx/auxillary_functions/eccentricity.rb', line 33 def self.radius(graph) eccentricity(graph).values.min end |
.relabel(node, num, r_adj, r_nodes) ⇒ Object
Helper function to relable a node to create a permissible edge
125 126 127 128 |
# File 'lib/networkx/flow/preflowpush.rb', line 125 def self.relabel(u_node, grt, r_adj, _r_nodes, _source, _target, _levels) grt.add_work(r_adj[u_node].length) r_adj[u_node].map { |v, attr| attr[:flow] < (attr[:capacity] + 1) ? _nodes[v][:height] : Float::INFINITY }.min end |
.reverse_bfs(src, residual_pred) ⇒ Object
Helper function for reverse bfs
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 |
# File 'lib/networkx/flow/preflowpush.rb', line 221 def self.reverse_bfs(src, residual_pred) heights = {src => 0} q = [[src, 0]] until q.empty? u, height = q.shift height += 1 residual_pred[u].each do |v, attr| if !heights.key?(v) && attr[:flow] < attr[:capacity] heights[v] = height q << [v, height] end end end heights end |
.set_path_lengths_johnson(graph, dist_path, new_weight) ⇒ Object
Helper function to set path lengths for Johnson algorithm
382 383 384 385 386 |
# File 'lib/networkx/shortest_path/weighted.rb', line 382 def self.set_path_lengths_johnson(graph, dist_path, new_weight) path_lengths = [] graph.nodes.each_key { |n| path_lengths << [n, dist_path.call(graph, n, new_weight)] } path_lengths end |
.shortest_augmenting_path(graph, source, target, residual = nil, _value_only = false, two_phase = false, cutoff = nil) ⇒ DiGraph
Computes max flow using shortest augmenting path algorithm
154 155 156 |
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 154 def self.shortest_augmenting_path(graph, source, target, residual=nil, _value_only=false, two_phase=false, cutoff=nil) shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff) end |
.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff) ⇒ Object
Helper function for running the shortest augmenting path algorithm
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 7 def self.shortest_augmenting_path_impl(graph, source, target, residual, two_phase, cutoff) raise ArgumentError, 'Source is not in the graph!' unless graph.nodes.key?(source) raise ArgumentError, 'Target is not in the graph!' unless graph.nodes.key?(target) raise ArgumentError, 'Source and Target are the same!' if source == target residual = residual.nil? ? build_residual_network(graph) : residual r_nodes = residual.nodes r_pred = residual.pred r_adj = residual.adj r_adj.each_value do |u_edges| u_edges.each_value do |attrs| attrs[:flow] = 0 end end heights = {target => 0} q = [[target, 0]] until q.empty? u, height = q.shift height += 1 r_pred[u].each do |v, attrs| if !heights.key?(v) && attrs[:flow] < attrs[:capacity] heights[v] = height q << [v, height] end end end unless heights.key?(source) residual.graph[:flow_value] = 0 return residual end n = graph.nodes.length m = residual.size / 2 r_nodes.each do |node, attrs| attrs[:height] = heights.key?(node) ? heights[node] : n attrs[:curr_edge] = CurrentEdge.new(r_adj[node]) end counts = Array.new(2 * n - 1, 0) counts.fill(0) r_nodes.each_value { |attrs| counts[attrs[:height]] += 1 } inf = graph.graph[:inf] cutoff = Float::INFINITY if cutoff.nil? flow_value = 0 path = [source] u = source d = two_phase ? n : [m ** 0.5, 2 * n ** (2. / 3)].min.floor done = r_nodes[source][:height] >= d until done height = r_nodes[u][:height] curr_edge = r_nodes[u][:curr_edge] loop do v, attr = curr_edge.get if height == r_nodes[v][:height] + 1 && attr[:flow] < attr[:capacity] path << v u = v break end begin curr_edge.move_to_next rescue StopIteration if counts[height].zero? residual.graph[:flow_value] = flow_value return residual end height = relabel(u, n, r_adj, r_nodes) if u == source && height >= d if !two_phase residual.graph[:flow_value] = flow_value return residual else done = true break end end counts[height] += 1 r_nodes[u][:height] = height unless u == source path.pop u = path[-1] break end end end next unless u == target flow_value += augment(path, inf, r_adj) if flow_value >= cutoff residual.graph[:flow_value] = flow_value return residual end end flow_value += edmondskarp_core(residual, source, target, cutoff - flow_value) residual.graph[:flow_value] = flow_value residual end |
.single_source_shortest_path(graph, source, cutoff = nil) ⇒ Array<Object, Array<Object, Array<Object>>>
Computes single source shortest path from a node to every other node
82 83 84 85 86 87 88 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 82 def self.single_source_shortest_path(graph, source, cutoff=nil) raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source) cutoff = Float::INFINITY if cutoff.nil? nextlevel = {source => 1} paths = {source => [source]} help_single_shortest_path(graph.adj, nextlevel, paths, cutoff) end |
.single_source_shortest_path_length(graph, source, cutoff = nil) ⇒ Array<Object, Numeric>
Computes shortest path values to all nodes from a given node
34 35 36 37 38 39 |
# File 'lib/networkx/shortest_path/unweighted.rb', line 34 def self.single_source_shortest_path_length(graph, source, cutoff=nil) raise ArgumentError, 'Source not found in the Graph!' unless graph.node?(source) cutoff = Float::INFINITY if cutoff.nil? nextlevel = {source => 1} help_single_shortest_path_length(graph.adj, nextlevel, cutoff).take(graph.nodes.length) end |
.singlesource_bellmanford(graph, source, target = nil, cutoff = nil) ⇒ Object
282 283 284 285 286 287 288 289 290 |
# File 'lib/networkx/shortest_path/weighted.rb', line 282 def self.singlesource_bellmanford(graph, source, target=nil, cutoff=nil) return [0, [source]] if source == target weight = get_weight(graph) paths = {source => [source]} dist = help_bellman_ford(graph, [source], weight, nil, paths, nil, cutoff, target) return [dist, paths] if target.nil? raise ArgumentError, 'Node not reachable!' unless dist.key?(target) [dist[target], paths[target]] end |
.singlesource_bellmanford_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Shortest path from source to all nodes using Bellman Ford algorithm
326 327 328 329 |
# File 'lib/networkx/shortest_path/weighted.rb', line 326 def self.singlesource_bellmanford_path(graph, source, cutoff=nil) _, path = singlesource_bellmanford(graph, source, cutoff) path end |
.singlesource_bellmanford_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }
Shortest path length from source to all nodes using Bellman Ford algorithm
338 339 340 341 |
# File 'lib/networkx/shortest_path/weighted.rb', line 338 def self.singlesource_bellmanford_path_length(graph, source, cutoff=nil) weight = get_weight(graph) help_bellman_ford(graph, [source], weight, nil, nil, nil, cutoff) end |
.singlesource_dijkstra(graph, source, target = nil, cutoff = nil) ⇒ Hash{ Object => Array<Object> }, Array<Object>
Computes shortest paths and path distances to all nodes/target from the given node
110 111 112 |
# File 'lib/networkx/shortest_path/weighted.rb', line 110 def self.singlesource_dijkstra(graph, source, target=nil, cutoff=nil) multisource_dijkstra(graph, [source], target, cutoff) end |
.singlesource_dijkstra_path(graph, source, cutoff = nil) ⇒ Hash{ Object => Array<Object> }
Computes shortest paths to all nodes from the given node
132 133 134 |
# File 'lib/networkx/shortest_path/weighted.rb', line 132 def self.singlesource_dijkstra_path(graph, source, cutoff=nil) multisource_dijkstra_path(graph, [source], cutoff) end |
.singlesource_dijkstra_path_length(graph, source, cutoff = nil) ⇒ Hash{ Object => Numeric }
Computes shortest path lengths to all nodes from the given node
121 122 123 |
# File 'lib/networkx/shortest_path/weighted.rb', line 121 def self.singlesource_dijkstra_path_length(graph, source, cutoff=nil) multisource_dijkstra_path_length(graph, [source], cutoff) end |
.strong_product(g_1, g_2) ⇒ Graph, ...
Returns the strong product of two graphs
161 162 163 164 165 166 167 168 169 |
# File 'lib/networkx/operators/product.rb', line 161 def self.strong_product(g_1, g_2) g = init_product_graph(g_1, g_2) g.add_nodes(node_product(g_1, g_2)) g.add_edges(nodes_cross_edges(g_1, g_2)) g.add_edges(edges_cross_nodes(g_1, g_2)) g.add_edges(directed_edges_cross_edges(g_1, g_2)) g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed? g end |
.symmetric_difference(g_1, g_2) ⇒ Graph, ...
Performs the symmetric difference of two graphs
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
# File 'lib/networkx/operators/binary.rb', line 130 def self.symmetric_difference(g_1, g_2) result = Marshal.load(Marshal.dump(g_1)) result.clear raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph? raise ArgumentError, 'Node sets must be equal!' unless (g_1.nodes.keys - g_2.nodes.keys).empty? g_1.nodes.each { |u, attrs| result.add_node(u, attrs) } g_1.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if g_1.multigraph? uv_attrs.each do |k, attrs| result.add_edge(u, v, attrs) unless g_2.edge?(u, v, k) end else result.add_edge(u, v, uv_attrs) unless g_2.edge?(u, v) end end end g_2.adj.each do |u, u_edges| u_edges.each do |v, uv_attrs| if g_2.multigraph? uv_attrs.each do |k, attrs| result.add_edge(u, v, attrs) unless g_1.edge?(u, v, k) end else result.add_edge(u, v, uv_attrs) unless g_1.edge?(u, v) end end end result end |
.tensor_product(g_1, g_2) ⇒ Graph, ...
Returns the tensor product of two graphs
119 120 121 122 123 124 125 |
# File 'lib/networkx/operators/product.rb', line 119 def self.tensor_product(g_1, g_2) g = init_product_graph(g_1, g_2) g.add_nodes(node_product(g_1, g_2)) g.add_edges(directed_edges_cross_edges(g_1, g_2)) g.add_edges(undirected_edges_cross_edges(g_1, g_2)) unless g.directed? g end |
.to_matrix(graph, val, multigraph_weight = 'sum') ⇒ Object
TODO: Reduce condition branches and method length
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
# File 'lib/networkx/to_matrix.rb', line 3 def self.to_matrix(graph, val, multigraph_weight='sum') is_undirected = !graph.directed? is_multigraph = graph.multigraph? nodelen = graph.nodes.length m = NMatrix.new(nodelen, val) index = {} inv_index = {} ind = 0 graph.nodes.each do |u, _| index[u] = ind inv_index[ind] = u ind += 1 end if is_multigraph graph.adj.each do |u, edge_hash| edge_hash.each do |v, keys| all_weights = [] keys.each do |_key, attrs| all_weights << attrs[:weight] end edge_attr = 0 case multigraph_weight when 'sum' edge_attr = all_weights.inject(0, :+) when 'max' edge_attr = all_weights.max when 'min' edge_attr = all_weights.min end m[index[u], index[v]] = edge_attr m[index[v], index[u]] = edge_attr || 1 if is_undirected end end else graph.adj.each do |u, edge_hash| edge_hash.each do |v, attrs| m[index[u], index[v]] = (attrs[:weight] || 1) m[index[v], index[u]] = (attrs[:weight] || 1) if is_undirected end end end [m, inv_index] end |
.topological_sort(graph) ⇒ Array<Object>
Returns the nodes arranged in the topologically sorted fashion
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# File 'lib/networkx/auxillary_functions/dag.rb', line 33 def self.topological_sort(graph) raise ArgumentError, 'Topological Sort not defined on undirected graphs!' unless graph.directed? nodes = [] indegree_map = Hash[graph.nodes.each_key.map { |u| [u, graph.in_degree(u)] if graph.in_degree(u) > 0 }.compact] zero_indegree = graph.nodes.each_key.map { |u| u if graph.in_degree(u).zero? }.compact until zero_indegree.empty? node = zero_indegree.shift raise ArgumentError, 'Graph changed during iteration!' unless graph.nodes.key?(node) graph.adj[node].each_key do |child| indegree_map[child] -= 1 if indegree_map[child].zero? zero_indegree << child indegree_map.delete(child) end end nodes << node end raise ArgumentError, 'Graph contains cycle or graph changed during iteration!' unless indegree_map.empty? nodes end |
.undirected_edges_cross_edges(g_1, g_2) ⇒ Object
Returns the product of undirected edges with edges
55 56 57 58 59 60 61 62 63 |
# File 'lib/networkx/operators/product.rb', line 55 def self.undirected_edges_cross_edges(g_1, g_2) result = [] edges_in_array(g_1).each do |u, v, c| edges_in_array(g_2).each do |x, y, d| result << [[v, x], [u, y], hash_product(c, d)] end end result end |
.union(g_1, g_2) ⇒ Graph, ...
Performs the union of two graphs
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 |
# File 'lib/networkx/operators/binary.rb', line 200 def self.union(g_1, g_2) raise ArgumentError, 'Arguments must be both Graphs or MultiGraphs!' unless g_1.multigraph? == g_2.multigraph? case g_1 when NetworkX::MultiGraph new_graph = NetworkX::MultiGraph.new when NetworkX::MultiDiGraph new_graph = NetworkX::MultiDiGraph.new when NetworkX::Graph new_graph = NetworkX::Graph.new when NetworkX::DiGraph new_graph = NetworkX::DiGraph.new end new_graph.graph.merge!(g_1.graph) new_graph.graph.merge!(g_2.graph) raise ArgumentError, 'Graphs must be disjoint!' unless (g_1.nodes.keys & g_2.nodes.keys).empty? g1_edges = get_edges(g_1) g2_edges = get_edges(g_2) new_graph.add_nodes(g_1.nodes.keys) new_graph.add_edges(g1_edges) new_graph.add_nodes(g_2.nodes.keys) new_graph.add_edges(g2_edges) new_graph end |
.union_all(graphs) ⇒ Graph, ...
Performs the union of many graphs
7 8 9 10 11 12 13 14 15 |
# File 'lib/networkx/operators/all.rb', line 7 def self.union_all(graphs) raise ArgumentError, 'Argument array is empty' if graphs.empty? result = graphs.shift graphs.each do |graph| result = NetworkX.union(result, graph) end result end |
.wiener_index(graph) ⇒ Numeric
Returns the wiener index of the graph
7 8 9 10 11 12 |
# File 'lib/networkx/auxillary_functions/wiener.rb', line 7 def self.wiener_index(graph) total = all_pairs_shortest_path_length(graph) wiener_ind = 0 Hash[total].each { |_, distances| Hash[distances].each { |_, val| wiener_ind += val } } graph.directed? ? wiener_ind : wiener_ind / 2 end |
Instance Method Details
#augment(path, inf, r_adj) ⇒ Object
Helper function for augmenting flow
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
# File 'lib/networkx/flow/shortestaugmentingpath.rb', line 114 def augment(path, inf, r_adj) flow = inf temp_path = path.clone u = temp_path.shift temp_path.each do |v| attr = r_adj[u][v] flow = [flow, attr[:capacity] - attr[:flow]].min u = v end raise ArgumentError, 'Infinite capacity path!' if flow * 2 > inf temp_path = path.clone u = temp_path.shift temp_path.each do |v| r_adj[u][v][:flow] += flow r_adj[v][u][:flow] -= flow u = v end flow end |