diff options
| author | JGab <jean.gabriel.young@gmail.com> | 2015-06-11 23:33:54 -0400 |
|---|---|---|
| committer | JGab <jean.gabriel.young@gmail.com> | 2015-06-11 23:33:54 -0400 |
| commit | f2235c4cd827154c5c8b468a06b7e02344cfdc75 (patch) | |
| tree | 19d2621588eda7acfee85f00722326ddad78e402 | |
| parent | ba7c5079701639d98a8032c4eaa4edf9138099c6 (diff) | |
| parent | 716863367f8528ecba09a5d0af004f5813def66b (diff) | |
| download | networkx-f2235c4cd827154c5c8b468a06b7e02344cfdc75.tar.gz | |
Merge remote-tracking branch 'upstream/master' into fix_approximation_import
47 files changed, 2740 insertions, 921 deletions
diff --git a/doc/source/reference/algorithms.approximation.rst b/doc/source/reference/algorithms.approximation.rst index d62ac7ee..1e5454db 100644 --- a/doc/source/reference/algorithms.approximation.rst +++ b/doc/source/reference/algorithms.approximation.rst @@ -5,6 +5,26 @@ Approximation .. automodule:: networkx.algorithms.approximation +Connectivity +------------ +.. automodule:: networkx.algorithms.approximation.connectivity +.. autosummary:: + :toctree: generated/ + + all_pairs_node_connectivity + local_node_connectivity + node_connectivity + + +K-components +------------ +.. automodule:: networkx.algorithms.approximation.kcomponents +.. autosummary:: + :toctree: generated/ + + k_components + + Clique ------ .. automodule:: networkx.algorithms.approximation.clique diff --git a/doc/source/reference/algorithms.connectivity.rst b/doc/source/reference/algorithms.connectivity.rst index afe73357..f3c1e736 100644 --- a/doc/source/reference/algorithms.connectivity.rst +++ b/doc/source/reference/algorithms.connectivity.rst @@ -5,6 +5,14 @@ Connectivity .. automodule:: networkx.algorithms.connectivity +K-node-components +----------------- +.. automodule:: networkx.algorithms.connectivity.kcomponents +.. autosummary:: + :toctree: generated/ + + k_components + K-node-cutsets -------------- .. automodule:: networkx.algorithms.connectivity.kcutsets @@ -13,7 +21,6 @@ K-node-cutsets all_node_cuts - Flow-based Connectivity ----------------------- .. automodule:: networkx.algorithms.connectivity.connectivity diff --git a/doc/source/reference/algorithms.minors.rst b/doc/source/reference/algorithms.minors.rst index bdea07a3..dbc86947 100644 --- a/doc/source/reference/algorithms.minors.rst +++ b/doc/source/reference/algorithms.minors.rst @@ -8,4 +8,5 @@ Minors contracted_edge contracted_nodes + identified_nodes quotient_graph diff --git a/doc/source/reference/api_2.0.rst b/doc/source/reference/api_1.10.rst index bdf5108c..82d5de2d 100644 --- a/doc/source/reference/api_2.0.rst +++ b/doc/source/reference/api_1.10.rst @@ -1,13 +1,28 @@ ********************************* -Version 2.0 notes and API changes +Version 1.10 notes and API changes ********************************* This page includes more detailed release information and API changes from -NetworkX 1.9 to NetworkX 2.0. +NetworkX 1.9 to NetworkX 1.10. Please send comments and questions to the networkx-discuss mailing list: <http://groups.google.com/group/networkx-discuss>. +API changes +----------- +* [`#1501 <https://github.com/networkx/networkx/pull/1501>`_] + ``connected_components``, ``weakly_connected_components``, and + ``strongly_connected_components`` return now a generator of sets of + nodes. Previously the generator was of lists of nodes. This PR also + refactored the ``connected_components`` and ``weakly_connected_components`` + implementations making them faster, especially for large graphs. + +* [`#1547 <https://github.com/networkx/networkx/issues/1547>`_] + The ``func_iter`` functions in Di/Multi/Graphs classes are slated for + removal in NetworkX 2.0 release. ``func`` will behave like ``func_iter`` + and return an iterator instead of list. These functions are deprecated in + NetworkX 1.10 release. + New functionalities ------------------- @@ -104,16 +119,19 @@ New functionalities ``algorithms.bipartite.generators``. The functions are not imported in the main namespace, so to use it, the bipartite package has to be imported. -* [`#1405 <https://github.com/networkx/networkx/pull/1405>`_] - Added fast approximation for node connectivity based on White and - Newman's approximation algorithm for finding node independent paths - between two nodes. - * [`#1391 <https://github.com/networkx/networkx/pull/1391>`_] Added Kanevsky's algorithm for finding all minimum-size separating node sets in an undirected graph. It is implemented as a generator of node cut sets. +* [`#1399 <https://github.com/networkx/networkx/pull/1399>`_] + Added power function for simple graphs + +* [`#1405 <https://github.com/networkx/networkx/pull/1405>`_] + Added fast approximation for node connectivity based on White and + Newman's approximation algorithm for finding node independent paths + between two nodes. + * [`#1413 <https://github.com/networkx/networkx/pull/1413>`_] Added transitive closure and antichains function for directed acyclic graphs in ``algorithms.dag``. The antichains function was contributed @@ -139,38 +157,46 @@ New functionalities * [`#1439 <https://github.com/networkx/networkx/pull/1439>`_] Added node and edge contraction functions to - :mod:`networkx.algorithms.minors`. + ``networkx.algorithms.minors``. * [`#1445 <https://github.com/networkx/networkx/pull/1448>`_] Added a new modularity matrix module to ``networkx.linalg``, and associated spectrum functions to the ``networkx.linalg.spectrum`` module. -* [`#1455 <https://github.com/networkx/networkx/pull/1455>`_] - Added the directed modularity matrix to the - ``networkx.linalg.modularity_matrix`` module. - * [`#1447 <https://github.com/networkx/networkx/pull/1447>`_] Added function to generate all simple paths starting with the shortest ones based on Yen's algorithm for finding k shortest paths at ``algorithms.simple_paths``. +* [`#1455 <https://github.com/networkx/networkx/pull/1455>`_] + Added the directed modularity matrix to the + ``networkx.linalg.modularity_matrix`` module. + * [`#1474 <https://github.com/networkx/networkx/pull/1474>`_] Adds ``triadic_census`` function; also creates a new module, - :mod:`networkx.algorithms.triads`. + ``networkx.algorithms.triads``. + +* [`#1476 <https://github.com/networkx/networkx/pull/1476>`_] + Adds functions for testing if a graph has weighted or negatively weighted + edges. Also adds a function for testing if a graph is empty. These are + ``is_weighted``, ``is_negatively_weighted``, and ``is_empty``. * [`#1481 <https://github.com/networkx/networkx/pull/1481>`_] Added Johnson's algorithm; one more algorithm for shortest paths. It solves all pairs shortest path problem. This is ``johnson`` at ``algorithms.shortest_paths`` -* [`#1476 <https://github.com/networkx/networkx/pull/1476>`_] - Adds functions for testing if a graph has weighted or negatively weighted - edges. Also adds a function for testing if a graph is empty. These are - ``is_weighted``, ``is_negatively_weighted``, and ``is_empty``. +* [`#1414 <https://github.com/networkx/networkx/pull/1414>`_] + Added Moody and White algorithm for identifying ``k_components`` in a + graph, which is based on Kanevsky's algorithm for finding all minimum-size + node cut-sets (implemented in ``all_node_cuts`` #1391). -* [`#1399 <https://github.com/networkx/networkx/pull/1399>`_] - Added power function for simple graphs +* [`#1415 <https://github.com/networkx/networkx/pull/1415>`_] + Added fast approximation for ``k_components`` to the + ``networkx.approximation`` package. This is based on White and Newman + approximation algorithm for finding node independent paths between two + nodes (see #1405). Removed functionalities ----------------------- diff --git a/doc/source/reference/api_changes.rst b/doc/source/reference/api_changes.rst index 6b2fe0ae..73bfb440 100644 --- a/doc/source/reference/api_changes.rst +++ b/doc/source/reference/api_changes.rst @@ -5,7 +5,7 @@ API changes .. toctree:: :maxdepth: 2 - api_2.0 + api_1.10 api_1.9 api_1.8 api_1.7 diff --git a/doc/source/reference/generators.rst b/doc/source/reference/generators.rst index 16c68245..1b432c3f 100644 --- a/doc/source/reference/generators.rst +++ b/doc/source/reference/generators.rst @@ -101,6 +101,7 @@ Random Graphs random_regular_graph barabasi_albert_graph powerlaw_cluster_graph + duplication_divergence_graph random_lobster random_shell_graph random_powerlaw_tree diff --git a/doc/source/tutorial/tutorial.rst b/doc/source/tutorial/tutorial.rst index 3b6826a0..351759a1 100644 --- a/doc/source/tutorial/tutorial.rst +++ b/doc/source/tutorial/tutorial.rst @@ -127,7 +127,7 @@ Removing nodes or edges has similar syntax to adding: [1, 2, 3, 'spam'] >>> G.remove_edge(1,3) -When creating a graph structure (by instantiating one of the graph +When creating a graph structure by instantiating one of the graph classes you can specify data in several formats. >>> H=nx.DiGraph(G) # create a DiGraph using the connections from G diff --git a/examples/subclass/antigraph.py b/examples/subclass/antigraph.py new file mode 100644 index 00000000..32776b77 --- /dev/null +++ b/examples/subclass/antigraph.py @@ -0,0 +1,207 @@ +""" Complement graph class for small footprint when working on dense graphs. + +This class allows you to add the edges that *do not exist* in the dense +graph. However, when applying algorithms to this complement graph data +structure, it behaves as if it were the dense version. So it can be used +directly in several NetworkX algorithms. + +This subclass has only been tested for k-core, connected_components, +and biconnected_components algorithms but might also work for other +algorithms. + +""" +# Copyright (C) 2015 by +# Jordi Torrents <jtorrents@milnou.net> +# All rights reserved. +# BSD license. +import networkx as nx +from networkx.exception import NetworkXError + + +__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>']) + +__all__ = ['AntiGraph'] + + +class AntiGraph(nx.Graph): + """ + Class for complement graphs. + + The main goal is to be able to work with big and dense graphs with + a low memory foodprint. + + In this class you add the edges that *do not exist* in the dense graph, + the report methods of the class return the neighbors, the edges and + the degree as if it was the dense graph. Thus it's possible to use + an instance of this class with some of NetworkX functions. + """ + + all_edge_dict = {'weight': 1} + def single_edge_dict(self): + return self.all_edge_dict + edge_attr_dict_factory = single_edge_dict + + def __getitem__(self, n): + """Return a dict of neighbors of node n in the dense graph. + + Parameters + ---------- + n : node + A node in the graph. + + Returns + ------- + adj_dict : dictionary + The adjacency dictionary for nodes connected to n. + + """ + return dict((node, self.all_edge_dict) for node in + set(self.adj) - set(self.adj[n]) - set([n])) + + + def neighbors(self, n): + """Return a list of the nodes connected to the node n in + the dense graph. + + Parameters + ---------- + n : node + A node in the graph + + Returns + ------- + nlist : list + A list of nodes that are adjacent to n. + + Raises + ------ + NetworkXError + If the node n is not in the graph. + + """ + try: + return list(set(self.adj) - set(self.adj[n]) - set([n])) + except KeyError: + raise NetworkXError("The node %s is not in the graph."%(n,)) + + def neighbors_iter(self, n): + """Return an iterator over all neighbors of node n in the + dense graph. + + """ + try: + return iter(set(self.adj) - set(self.adj[n]) - set([n])) + except KeyError: + raise NetworkXError("The node %s is not in the graph."%(n,)) + + def degree(self, nbunch=None, weight=None): + """Return the degree of a node or nodes in the dense graph. + """ + if nbunch in self: # return a single node + return next(self.degree_iter(nbunch,weight))[1] + else: # return a dict + return dict(self.degree_iter(nbunch,weight)) + + def degree_iter(self, nbunch=None, weight=None): + """Return an iterator for (node, degree) in the dense graph. + + The node degree is the number of edges adjacent to the node. + + Parameters + ---------- + nbunch : iterable container, optional (default=all nodes) + A container of nodes. The container will be iterated + through once. + + weight : string or None, optional (default=None) + The edge attribute that holds the numerical value used + as a weight. If None, then each edge has weight 1. + The degree is the sum of the edge weights adjacent to the node. + + Returns + ------- + nd_iter : an iterator + The iterator returns two-tuples of (node, degree). + + See Also + -------- + degree + + Examples + -------- + >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc + >>> G.add_path([0,1,2,3]) + >>> list(G.degree_iter(0)) # node 0 with degree 1 + [(0, 1)] + >>> list(G.degree_iter([0,1])) + [(0, 1), (1, 2)] + + """ + if nbunch is None: + nodes_nbrs = ((n, {v: self.all_edge_dict for v in + set(self.adj) - set(self.adj[n]) - set([n])}) + for n in self.nodes_iter()) + else: + nodes_nbrs= ((n, {v: self.all_edge_dict for v in + set(self.nodes()) - set(self.adj[n]) - set([n])}) + for n in self.nbunch_iter(nbunch)) + + if weight is None: + for n,nbrs in nodes_nbrs: + yield (n,len(nbrs)+(n in nbrs)) # return tuple (n,degree) + else: + # AntiGraph is a ThinGraph so all edges have weight 1 + for n,nbrs in nodes_nbrs: + yield (n, sum((nbrs[nbr].get(weight, 1) for nbr in nbrs)) + + (n in nbrs and nbrs[n].get(weight, 1))) + + def adjacency_iter(self): + """Return an iterator of (node, adjacency set) tuples for all nodes + in the dense graph. + + This is the fastest way to look at every edge. + For directed graphs, only outgoing adjacencies are included. + + Returns + ------- + adj_iter : iterator + An iterator of (node, adjacency set) for all nodes in + the graph. + + """ + for n in self.adj: + yield (n, set(self.adj) - set(self.adj[n]) - set([n])) + + +if __name__ == '__main__': + # Build several pairs of graphs, a regular graph + # and the AntiGraph of it's complement, which behaves + # as if it were the original graph. + Gnp = nx.gnp_random_graph(20,0.8) + Anp = AntiGraph(nx.complement(Gnp)) + Gd = nx.davis_southern_women_graph() + Ad = AntiGraph(nx.complement(Gd)) + Gk = nx.karate_club_graph() + Ak = AntiGraph(nx.complement(Gk)) + pairs = [(Gnp, Anp), (Gd, Ad), (Gk, Ak)] + # test connected components + for G, A in pairs: + gc = [set(c) for c in nx.connected_components(G)] + ac = [set(c) for c in nx.connected_components(A)] + for comp in ac: + assert comp in gc + # test biconnected components + for G, A in pairs: + gc = [set(c) for c in nx.biconnected_components(G)] + ac = [set(c) for c in nx.biconnected_components(A)] + for comp in ac: + assert comp in gc + # test degree + for G, A in pairs: + node = list(G.nodes())[0] + nodes = list(G.nodes())[1:4] + assert G.degree(node) == A.degree(node) + assert sum(G.degree().values()) == sum(A.degree().values()) + # AntiGraph is a ThinGraph, so all the weights are 1 + assert sum(A.degree().values()) == sum(A.degree(weight='weight').values()) + assert sum(G.degree(nodes).values()) == sum(A.degree(nodes).values()) diff --git a/networkx/algorithms/__init__.py b/networkx/algorithms/__init__.py index f7183abb..74109291 100644 --- a/networkx/algorithms/__init__.py +++ b/networkx/algorithms/__init__.py @@ -59,7 +59,7 @@ from networkx.algorithms.bipartite import (projected_graph, project, is_bipartit # connectivity from networkx.algorithms.connectivity import (minimum_edge_cut, minimum_node_cut, average_node_connectivity, edge_connectivity, node_connectivity, - stoer_wagner, all_pairs_node_connectivity, all_node_cuts) + stoer_wagner, all_pairs_node_connectivity, all_node_cuts, k_components) # isomorphism from networkx.algorithms.isomorphism import (is_isomorphic, could_be_isomorphic, fast_could_be_isomorphic, faster_could_be_isomorphic) diff --git a/networkx/algorithms/approximation/__init__.py b/networkx/algorithms/approximation/__init__.py index f59dd911..34ee31cc 100644 --- a/networkx/algorithms/approximation/__init__.py +++ b/networkx/algorithms/approximation/__init__.py @@ -7,6 +7,7 @@ from networkx.algorithms.approximation.clustering_coefficient import * from networkx.algorithms.approximation.clique import * from networkx.algorithms.approximation.connectivity import * from networkx.algorithms.approximation.dominating_set import * +from networkx.algorithms.approximation.kcomponents import * from networkx.algorithms.approximation.independent_set import * from networkx.algorithms.approximation.matching import * from networkx.algorithms.approximation.ramsey import * diff --git a/networkx/algorithms/approximation/dominating_set.py b/networkx/algorithms/approximation/dominating_set.py index 6a167e2f..57391973 100644 --- a/networkx/algorithms/approximation/dominating_set.py +++ b/networkx/algorithms/approximation/dominating_set.py @@ -1,91 +1,109 @@ # -*- coding: utf-8 -*- -""" -************************************** -Minimum Vertex and Edge Dominating Set -************************************** +# Copyright (C) 2011-2012 by +# Nicholas Mancuso <nick.mancuso@gmail.com> +# All rights reserved. +# BSD license. +"""Functions for finding node and edge dominating sets. +A *`dominating set`_* for an undirected graph *G* with vertex set *V* +and edge set *E* is a subset *D* of *V* such that every vertex not in +*D* is adjacent to at least one member of *D*. An *`edge dominating +set`_* is a subset *F* of *E* such that every edge not in *F* is +incident to an endpoint of at least one edge in *F*. -A dominating set for a graph G = (V, E) is a subset D of V such that every -vertex not in D is joined to at least one member of D by some edge. The -domination number gamma(G) is the number of vertices in a smallest dominating -set for G. Given a graph G = (V, E) find a minimum weight dominating set V'. +.. _dominating set:: https://en.wikipedia.org/wiki/Dominating_set +.. _edge dominating set:: https://en.wikipedia.org/wiki/Edge_dominating_set -http://en.wikipedia.org/wiki/Dominating_set +""" +from __future__ import division -An edge dominating set for a graph G = (V, E) is a subset D of E such that -every edge not in D is adjacent to at least one edge in D. +from ..matching import maximal_matching +from ...utils import not_implemented_for -http://en.wikipedia.org/wiki/Edge_dominating_set -""" -# Copyright (C) 2011-2012 by -# Nicholas Mancuso <nick.mancuso@gmail.com> -# All rights reserved. -# BSD license. -import networkx as nx __all__ = ["min_weighted_dominating_set", "min_edge_dominating_set"] + __author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)""" +# TODO Why doesn't this algorithm work for directed graphs? +@not_implemented_for('directed') def min_weighted_dominating_set(G, weight=None): - r"""Return minimum weight vertex dominating set. + """Returns a dominating set that approximates the minimum weight node + dominating set. Parameters ---------- G : NetworkX graph - Undirected graph + Undirected graph. - weight : None or string, optional (default = None) - If None, every edge has weight/distance/weight 1. If a string, use this - edge attribute as the edge weight. Any edge attribute not present - defaults to 1. + weight : string + The node attribute storing the weight of an edge. If provided, + the node attribute with this key must be a number for each + node. If not provided, each node is assumed to have weight one. Returns ------- min_weight_dominating_set : set - Returns a set of vertices whose weight sum is no more than log w(V) * OPT + A set of nodes, the sum of whose weights is no more than `(\log + w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of + each node in the graph and `w(V^*)` denotes the sum of the + weights of each node in the minimum weight dominating set. Notes ----- - This algorithm computes an approximate minimum weighted dominating set - for the graph G. The upper-bound on the size of the solution is - log w(V) * OPT. Runtime of the algorithm is `O(|E|)`. + This algorithm computes an approximate minimum weighted dominating + set for the graph ``G``. The returned solution has weight `(\log + w(V)) w(V^*)`, where `w(V)` denotes the sum of the weights of each + node in the graph and `w(V^*)` denotes the sum of the weights of + each node in the minimum weight dominating set for the graph. + + This implementation of the algorithm runs in `O(m)` time, where `m` + is the number of edges in the graph. References ---------- - .. [1] Vazirani, Vijay Approximation Algorithms (2001) + .. [1] Vazirani, Vijay V. + *Approximation Algorithms*. + Springer Science & Business Media, 2001. + """ - if not G: - raise ValueError("Expected non-empty NetworkX graph!") + # The unique dominating set for the null graph is the empty set. + if len(G) == 0: + return set() - # min cover = min dominating set - dom_set = set([]) - cost_func = dict((node, nd.get(weight, 1)) \ - for node, nd in G.nodes_iter(data=True)) + # This is the dominating set that will eventually be returned. + dom_set = set() - vertices = set(G) - sets = dict((node, set([node]) | set(G[node])) for node in G) + def _cost(node_and_neighborhood): + """Returns the cost-effectiveness of greedily choosing the given + node. - def _cost(subset): - """ Our cost effectiveness function for sets given its weight - """ - cost = sum(cost_func[node] for node in subset) - return cost / float(len(subset - dom_set)) + `node_and_neighborhood` is a two-tuple comprising a node and its + closed neighborhood. - while vertices: - # find the most cost effective set, and the vertex that for that set - dom_node, min_set = min(sets.items(), - key=lambda x: (x[0], _cost(x[1]))) - alpha = _cost(min_set) + """ + v, neighborhood = node_and_neighborhood + return G.node[v].get(weight, 1) / len(neighborhood - dom_set) - # reduce the cost for the rest - for node in min_set - dom_set: - cost_func[node] = alpha + # This is a set of all vertices not already covered by the + # dominating set. + vertices = set(G) + # This is a dictionary mapping each node to the closed neighborhood + # of that node. + neighborhoods = {v: {v} | set(G[v]) for v in G} - # add the node to the dominating set and reduce what we must cover + # Continue until all vertices are adjacent to some node in the + # dominating set. + while vertices: + # Find the most cost-effective node to add, along with its + # closed neighborhood. + dom_node, min_set = min(neighborhoods.items(), key=_cost) + # Add the node to the dominating set and reduce the remaining + # set of nodes to cover. dom_set.add(dom_node) - del sets[dom_node] - vertices = vertices - min_set + del neighborhoods[dom_node] + vertices -= min_set return dom_set @@ -111,4 +129,4 @@ def min_edge_dominating_set(G): """ if not G: raise ValueError("Expected non-empty NetworkX graph!") - return nx.maximal_matching(G) + return maximal_matching(G) diff --git a/networkx/algorithms/approximation/kcomponents.py b/networkx/algorithms/approximation/kcomponents.py new file mode 100644 index 00000000..4260f20b --- /dev/null +++ b/networkx/algorithms/approximation/kcomponents.py @@ -0,0 +1,350 @@ +""" Fast approximation for k-component structure +""" +# Copyright (C) 2015 by +# Jordi Torrents <jtorrents@milnou.net> +# All rights reserved. +# BSD license. +import itertools +import collections + +import networkx as nx +from networkx.exception import NetworkXError +from networkx.utils import not_implemented_for + +from networkx.algorithms.approximation import local_node_connectivity +from networkx.algorithms.connectivity import \ + local_node_connectivity as exact_local_node_connectivity +from networkx.algorithms.connectivity import build_auxiliary_node_connectivity +from networkx.algorithms.flow import build_residual_network + + +__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>']) + +__all__ = ['k_components'] + + +not_implemented_for('directed') +def k_components(G, min_density=0.95): + r"""Returns the approximate k-component structure of a graph G. + + A `k`-component is a maximal subgraph of a graph G that has, at least, + node connectivity `k`: we need to remove at least `k` nodes to break it + into more components. `k`-components have an inherent hierarchical + structure because they are nested in terms of connectivity: a connected + graph can contain several 2-components, each of which can contain + one or more 3-components, and so forth. + + This implementation is based on the fast heuristics to approximate + the `k`-component sturcture of a graph [1]_. Which, in turn, it is based on + a fast approximation algorithm for finding good lower bounds of the number + of node independent paths between two nodes [2]_. + + Parameters + ---------- + G : NetworkX graph + Undirected graph + + min_density : Float + Density relaxation treshold. Default value 0.95 + + Returns + ------- + k_components : dict + Dictionary with connectivity level `k` as key and a list of + sets of nodes that form a k-component of level `k` as values. + + + Examples + -------- + >>> # Petersen graph has 10 nodes and it is triconnected, thus all + >>> # nodes are in a single component on all three connectivity levels + >>> from networkx.algorithms import approximation as apxa + >>> G = nx.petersen_graph() + >>> k_components = apxa.k_components(G) + + Notes + ----- + The logic of the approximation algorithm for computing the `k`-component + structure [1]_ is based on repeatedly applying simple and fast algorithms + for `k`-cores and biconnected components in order to narrow down the + number of pairs of nodes over which we have to compute White and Newman's + approximation algorithm for finding node independent paths [2]_. More + formally, this algorithm is based on Whitney's theorem, which states + an inclusion relation among node connectivity, edge connectivity, and + minimum degree for any graph G. This theorem implies that every + `k`-component is nested inside a `k`-edge-component, which in turn, + is contained in a `k`-core. Thus, this algorithm computes node independent + paths among pairs of nodes in each biconnected part of each `k`-core, + and repeats this procedure for each `k` from 3 to the maximal core number + of a node in the input graph. + + Because, in practice, many nodes of the core of level `k` inside a + bicomponent actually are part of a component of level k, the auxiliary + graph needed for the algorithm is likely to be very dense. Thus, we use + a complement graph data structure (see `AntiGraph`) to save memory. + AntiGraph only stores information of the edges that are *not* present + in the actual auxiliary graph. When applying algorithms to this + complement graph data structure, it behaves as if it were the dense + version. + + See also + -------- + k_components + + References + ---------- + .. [1] Torrents, J. and F. Ferraro (2015) Structural Cohesion: + Visualization and Heuristics for Fast Computation. + http://arxiv.org/pdf/1503.04476v1 + + .. [2] White, Douglas R., and Mark Newman (2001) A Fast Algorithm for + Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 + http://eclectic.ss.uci.edu/~drwhite/working.pdf + + .. [3] Moody, J. and D. White (2003). Social cohesion and embeddedness: + A hierarchical conception of social groups. + American Sociological Review 68(1), 103--28. + http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf + + """ + # Dictionary with connectivity level (k) as keys and a list of + # sets of nodes that form a k-component as values + k_components = collections.defaultdict(list) + # make a few functions local for speed + node_connectivity = local_node_connectivity + k_core = nx.k_core + core_number = nx.core_number + biconnected_components = nx.biconnected_components + density = nx.density + combinations = itertools.combinations + # Exact solution for k = {1,2} + # There is a linear time algorithm for triconnectivity, if we had an + # implementation available we could start from k = 4. + for component in nx.connected_components(G): + # isolated nodes have connectivity 0 + comp = set(component) + if len(comp) > 1: + k_components[1].append(comp) + for bicomponent in nx.biconnected_components(G): + # avoid considering dyads as bicomponents + bicomp = set(bicomponent) + if len(bicomp) > 2: + k_components[2].append(bicomp) + # There is no k-component of k > maximum core number + # \kappa(G) <= \lambda(G) <= \delta(G) + g_cnumber = core_number(G) + max_core = max(g_cnumber.values()) + for k in range(3, max_core + 1): + C = k_core(G, k, core_number=g_cnumber) + for nodes in biconnected_components(C): + # Build a subgraph SG induced by the nodes that are part of + # each biconnected component of the k-core subgraph C. + if len(nodes) < k: + continue + SG = G.subgraph(nodes) + # Build auxiliary graph + H = _AntiGraph() + H.add_nodes_from(SG.nodes_iter()) + for u,v in combinations(SG, 2): + K = node_connectivity(SG, u, v, cutoff=k) + if k > K: + H.add_edge(u,v) + for h_nodes in biconnected_components(H): + if len(h_nodes) <= k: + continue + SH = H.subgraph(h_nodes) + for Gc in _cliques_heuristic(SG, SH, k, min_density): + for k_nodes in biconnected_components(Gc): + Gk = nx.k_core(SG.subgraph(k_nodes), k) + if len(Gk) <= k: + continue + k_components[k].append(set(Gk)) + return k_components + + +def _cliques_heuristic(G, H, k, min_density): + h_cnumber = nx.core_number(H) + for i, c_value in enumerate(sorted(set(h_cnumber.values()), reverse=True)): + cands = set(n for n, c in h_cnumber.items() if c == c_value) + # Skip checking for overlap for the highest core value + if i == 0: + overlap = False + else: + overlap = set.intersection(*[ + set(x for x in H[n] if x not in cands) + for n in cands]) + if overlap and len(overlap) < k: + SH = H.subgraph(cands | overlap) + else: + SH = H.subgraph(cands) + sh_cnumber = nx.core_number(SH) + SG = nx.k_core(G.subgraph(SH), k) + while not (_same(sh_cnumber) and nx.density(SH) >= min_density): + SH = H.subgraph(SG) + if len(SH) <= k: + break + sh_cnumber = nx.core_number(SH) + sh_deg = SH.degree() + min_deg = min(sh_deg.values()) + SH.remove_nodes_from(n for n, d in sh_deg.items() if d == min_deg) + SG = nx.k_core(G.subgraph(SH), k) + else: + yield SG + + +def _same(measure, tol=0): + vals = set(measure.values()) + if (max(vals) - min(vals)) <= tol: + return True + return False + + +class _AntiGraph(nx.Graph): + """ + Class for complement graphs. + + The main goal is to be able to work with big and dense graphs with + a low memory foodprint. + + In this class you add the edges that *do not exist* in the dense graph, + the report methods of the class return the neighbors, the edges and + the degree as if it was the dense graph. Thus it's possible to use + an instance of this class with some of NetworkX functions. In this + case we only use k-core, connected_components, and biconnected_components. + """ + + all_edge_dict = {'weight': 1} + def single_edge_dict(self): + return self.all_edge_dict + edge_attr_dict_factory = single_edge_dict + + def __getitem__(self, n): + """Return a dict of neighbors of node n in the dense graph. + + Parameters + ---------- + n : node + A node in the graph. + + Returns + ------- + adj_dict : dictionary + The adjacency dictionary for nodes connected to n. + + """ + all_edge_dict = self.all_edge_dict + return dict((node, all_edge_dict) for node in + set(self.adj) - set(self.adj[n]) - set([n])) + + def neighbors(self, n): + """Return a list of the nodes connected to the node n in + the dense graph. + + Parameters + ---------- + n : node + A node in the graph + + Returns + ------- + nlist : list + A list of nodes that are adjacent to n. + + Raises + ------ + NetworkXError + If the node n is not in the graph. + + """ + try: + return list(set(self.adj) - set(self.adj[n]) - set([n])) + except KeyError: + raise NetworkXError("The node %s is not in the graph."%(n,)) + + def neighbors_iter(self, n): + """Return an iterator over all neighbors of node n in the + dense graph. + + """ + try: + return iter(set(self.adj) - set(self.adj[n]) - set([n])) + except KeyError: + raise NetworkXError("The node %s is not in the graph."%(n,)) + + def degree(self, nbunch=None, weight=None): + """Return the degree of a node or nodes in the dense graph. + """ + if nbunch in self: # return a single node + return next(self.degree_iter(nbunch,weight))[1] + else: # return a dict + return dict(self.degree_iter(nbunch,weight)) + + def degree_iter(self, nbunch=None, weight=None): + """Return an iterator for (node, degree) in the dense graph. + + The node degree is the number of edges adjacent to the node. + + Parameters + ---------- + nbunch : iterable container, optional (default=all nodes) + A container of nodes. The container will be iterated + through once. + + weight : string or None, optional (default=None) + The edge attribute that holds the numerical value used + as a weight. If None, then each edge has weight 1. + The degree is the sum of the edge weights adjacent to the node. + + Returns + ------- + nd_iter : an iterator + The iterator returns two-tuples of (node, degree). + + See Also + -------- + degree + + Examples + -------- + >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc + >>> G.add_path([0,1,2,3]) + >>> list(G.degree_iter(0)) # node 0 with degree 1 + [(0, 1)] + >>> list(G.degree_iter([0,1])) + [(0, 1), (1, 2)] + + """ + if nbunch is None: + nodes_nbrs = ((n, {v: self.all_edge_dict for v in + set(self.adj) - set(self.adj[n]) - set([n])}) + for n in self.nodes_iter()) + else: + nodes_nbrs = ((n, {v: self.all_edge_dict for v in + set(self.nodes()) - set(self.adj[n]) - set([n])}) + for n in self.nbunch_iter(nbunch)) + + if weight is None: + for n,nbrs in nodes_nbrs: + yield (n,len(nbrs)+(n in nbrs)) # return tuple (n,degree) + else: + # AntiGraph is a ThinGraph so all edges have weight 1 + for n,nbrs in nodes_nbrs: + yield (n, sum((nbrs[nbr].get(weight, 1) for nbr in nbrs)) + + (n in nbrs and nbrs[n].get(weight, 1))) + + def adjacency_iter(self): + """Return an iterator of (node, adjacency set) tuples for all nodes + in the dense graph. + + This is the fastest way to look at every edge. + For directed graphs, only outgoing adjacencies are included. + + Returns + ------- + adj_iter : iterator + An iterator of (node, adjacency set) for all nodes in + the graph. + + """ + for n in self.adj: + yield (n, set(self.adj) - set(self.adj[n]) - set([n])) diff --git a/networkx/algorithms/approximation/tests/test_connectivity.py b/networkx/algorithms/approximation/tests/test_connectivity.py index aa491d40..991f5526 100644 --- a/networkx/algorithms/approximation/tests/test_connectivity.py +++ b/networkx/algorithms/approximation/tests/test_connectivity.py @@ -61,10 +61,12 @@ def test_octahedral(): assert_equal(4, approx.node_connectivity(G)) assert_equal(4, approx.node_connectivity(G, 0, 5)) -def test_icosahedral(): - G=nx.icosahedral_graph() - assert_equal(5, approx.node_connectivity(G)) - assert_equal(5, approx.node_connectivity(G, 0, 5)) +# Approximation can fail with icosahedral graph depending +# on iteration order. +#def test_icosahedral(): +# G=nx.icosahedral_graph() +# assert_equal(5, approx.node_connectivity(G)) +# assert_equal(5, approx.node_connectivity(G, 0, 5)) def test_only_source(): G = nx.complete_graph(5) diff --git a/networkx/algorithms/approximation/tests/test_dominating_set.py b/networkx/algorithms/approximation/tests/test_dominating_set.py index 0dbc79fd..bacf27bd 100644 --- a/networkx/algorithms/approximation/tests/test_dominating_set.py +++ b/networkx/algorithms/approximation/tests/test_dominating_set.py @@ -1,7 +1,9 @@ #!/usr/bin/env python -from nose.tools import * +from nose.tools import ok_ +from nose.tools import eq_ import networkx as nx -import networkx.algorithms.approximation as apxa +from networkx.algorithms.approximation import min_weighted_dominating_set +from networkx.algorithms.approximation import min_edge_dominating_set class TestMinWeightDominatingSet: @@ -18,14 +20,28 @@ class TestMinWeightDominatingSet: vertices = set([1, 2, 3, 4, 5, 6]) # due to ties, this might be hard to test tight bounds - dom_set = apxa.min_weighted_dominating_set(graph) + dom_set = min_weighted_dominating_set(graph) for vertex in vertices - dom_set: neighbors = set(graph.neighbors(vertex)) ok_(len(neighbors & dom_set) > 0, "Non dominating set found!") + def test_star_graph(self): + """Tests that an approximate dominating set for the star graph, + even when the center node does not have the smallest integer + label, gives just the center node. + + For more information, see #1527. + + """ + # Create a star graph in which the center node has the highest + # label instead of the lowest. + G = nx.star_graph(10) + G = nx.relabel_nodes(G, {0: 9, 9: 0}) + eq_(min_weighted_dominating_set(G), {9}) + def test_min_edge_dominating_set(self): graph = nx.path_graph(5) - dom_set = apxa.min_edge_dominating_set(graph) + dom_set = min_edge_dominating_set(graph) # this is a crappy way to test, but good enough for now. for edge in graph.edges_iter(): @@ -39,7 +55,7 @@ class TestMinWeightDominatingSet: ok_(found, "Non adjacent edge found!") graph = nx.complete_graph(10) - dom_set = apxa.min_edge_dominating_set(graph) + dom_set = min_edge_dominating_set(graph) # this is a crappy way to test, but good enough for now. for edge in graph.edges_iter(): diff --git a/networkx/algorithms/approximation/tests/test_kcomponents.py b/networkx/algorithms/approximation/tests/test_kcomponents.py new file mode 100644 index 00000000..67a85d92 --- /dev/null +++ b/networkx/algorithms/approximation/tests/test_kcomponents.py @@ -0,0 +1,269 @@ +# Test for approximation to k-components algorithm +from nose.tools import assert_equal, assert_true, assert_false, assert_raises, raises +import networkx as nx +from networkx.algorithms.approximation import k_components +from networkx.algorithms.approximation.kcomponents import _AntiGraph, _same + + +def build_k_number_dict(k_components): + k_num = {} + for k, comps in sorted(k_components.items()): + for comp in comps: + for node in comp: + k_num[node] = k + return k_num + +## +## Some nice synthetic graphs +## +def graph_example_1(): + G = nx.convert_node_labels_to_integers(nx.grid_graph([5,5]), + label_attribute='labels') + rlabels = nx.get_node_attributes(G, 'labels') + labels = dict((v, k) for k, v in rlabels.items()) + + for nodes in [(labels[(0,0)], labels[(1,0)]), + (labels[(0,4)], labels[(1,4)]), + (labels[(3,0)], labels[(4,0)]), + (labels[(3,4)], labels[(4,4)]) ]: + new_node = G.order()+1 + # Petersen graph is triconnected + P = nx.petersen_graph() + G = nx.disjoint_union(G,P) + # Add two edges between the grid and P + G.add_edge(new_node+1, nodes[0]) + G.add_edge(new_node, nodes[1]) + # K5 is 4-connected + K = nx.complete_graph(5) + G = nx.disjoint_union(G,K) + # Add three edges between P and K5 + G.add_edge(new_node+2,new_node+11) + G.add_edge(new_node+3,new_node+12) + G.add_edge(new_node+4,new_node+13) + # Add another K5 sharing a node + G = nx.disjoint_union(G,K) + nbrs = G[new_node+10] + G.remove_node(new_node+10) + for nbr in nbrs: + G.add_edge(new_node+17, nbr) + G.add_edge(new_node+16, new_node+5) + + G.name = 'Example graph for connectivity' + return G + +def torrents_and_ferraro_graph(): + G = nx.convert_node_labels_to_integers(nx.grid_graph([5,5]), + label_attribute='labels') + rlabels = nx.get_node_attributes(G, 'labels') + labels = dict((v, k) for k, v in rlabels.items()) + + for nodes in [ (labels[(0,4)], labels[(1,4)]), + (labels[(3,4)], labels[(4,4)]) ]: + new_node = G.order()+1 + # Petersen graph is triconnected + P = nx.petersen_graph() + G = nx.disjoint_union(G,P) + # Add two edges between the grid and P + G.add_edge(new_node+1, nodes[0]) + G.add_edge(new_node, nodes[1]) + # K5 is 4-connected + K = nx.complete_graph(5) + G = nx.disjoint_union(G,K) + # Add three edges between P and K5 + G.add_edge(new_node+2,new_node+11) + G.add_edge(new_node+3,new_node+12) + G.add_edge(new_node+4,new_node+13) + # Add another K5 sharing a node + G = nx.disjoint_union(G,K) + nbrs = G[new_node+10] + G.remove_node(new_node+10) + for nbr in nbrs: + G.add_edge(new_node+17, nbr) + # Commenting this makes the graph not biconnected !! + # This stupid mistake make one reviewer very angry :P + G.add_edge(new_node+16, new_node+8) + + for nodes in [(labels[(0,0)], labels[(1,0)]), + (labels[(3,0)], labels[(4,0)])]: + new_node = G.order()+1 + # Petersen graph is triconnected + P = nx.petersen_graph() + G = nx.disjoint_union(G,P) + # Add two edges between the grid and P + G.add_edge(new_node+1, nodes[0]) + G.add_edge(new_node, nodes[1]) + # K5 is 4-connected + K = nx.complete_graph(5) + G = nx.disjoint_union(G,K) + # Add three edges between P and K5 + G.add_edge(new_node+2,new_node+11) + G.add_edge(new_node+3,new_node+12) + G.add_edge(new_node+4,new_node+13) + # Add another K5 sharing two nodes + G = nx.disjoint_union(G,K) + nbrs = G[new_node+10] + G.remove_node(new_node+10) + for nbr in nbrs: + G.add_edge(new_node+17, nbr) + nbrs2 = G[new_node+9] + G.remove_node(new_node+9) + for nbr in nbrs2: + G.add_edge(new_node+18, nbr) + + G.name = 'Example graph for connectivity' + return G + +# Helper function +def _check_connectivity(G): + result = k_components(G) + for k, components in result.items(): + if k < 3: + continue + for component in components: + C = G.subgraph(component) + K = nx.node_connectivity(C) + assert_true(K >= k) + +def test_torrents_and_ferraro_graph(): + G = torrents_and_ferraro_graph() + _check_connectivity(G) + +def test_example_1(): + G = graph_example_1() + _check_connectivity(G) + +def test_random_gnp(): + G = nx.gnp_random_graph(50, 0.2) + _check_connectivity(G) + +def test_shell(): + constructor=[(20,80,0.8),(80,180,0.6)] + G = nx.random_shell_graph(constructor) + _check_connectivity(G) + +def test_configuration(): + deg_seq = nx.utils.create_degree_sequence(100,nx.utils.powerlaw_sequence) + G = nx.Graph(nx.configuration_model(deg_seq)) + G.remove_edges_from(G.selfloop_edges()) + _check_connectivity(G) + +def test_karate_0(): + G = nx.karate_club_graph() + _check_connectivity(G) + +def test_karate_1(): + karate_k_num = {0: 4, 1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 3, 7: 4, 8: 4, 9: 2, + 10: 3, 11: 1, 12: 2, 13: 4, 14: 2, 15: 2, 16: 2, 17: 2, 18: 2, + 19: 3, 20: 2, 21: 2, 22: 2, 23: 3, 24: 3, 25: 3, 26: 2, 27: 3, + 28: 3, 29: 3, 30: 4, 31: 3, 32: 4, 33: 4} + G = nx.karate_club_graph() + k_comps = k_components(G) + k_num = build_k_number_dict(k_comps) + assert_equal(karate_k_num, k_num) + +def test_example_1_detail_3_and_4(): + solution = { + 3: [set([40, 41, 42, 43, 39]), + set([32, 33, 34, 35, 36, 37, 38, 42, 25, 26, 27, 28, 29, 30, 31]), + set([58, 59, 60, 61, 62]), + set([44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 61]), + set([80, 81, 77, 78, 79]), + set([64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 80, 63]), + set([97, 98, 99, 100, 101]), + set([96, 100, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 94, 95]) + ], + 4: [set([40, 41, 42, 43, 39]), + set([42, 35, 36, 37, 38]), + set([58, 59, 60, 61, 62]), + set([56, 57, 61, 54, 55]), + set([80, 81, 77, 78, 79]), + set([80, 73, 74, 75, 76]), + set([97, 98, 99, 100, 101]), + set([96, 100, 92, 94, 95]) + ], + } + G = graph_example_1() + result = k_components(G) + for k, components in solution.items(): + for component in components: + assert_true(component in result[k]) + +@raises(nx.NetworkXNotImplemented) +def test_directed(): + G = nx.gnp_random_graph(10, 0.4, directed=True) + kc = k_components(G) + +def test_same(): + equal = {'A': 2, 'B': 2, 'C': 2} + slightly_different = {'A': 2, 'B': 1, 'C': 2} + different = {'A': 2, 'B': 8, 'C': 18} + assert_true(_same(equal)) + assert_false(_same(slightly_different)) + assert_true(_same(slightly_different, tol=1)) + assert_false(_same(different)) + assert_false(_same(different, tol=4)) + + +class TestAntiGraph: + def setUp(self): + self.Gnp = nx.gnp_random_graph(20,0.8) + self.Anp = _AntiGraph(nx.complement(self.Gnp)) + self.Gd = nx.davis_southern_women_graph() + self.Ad = _AntiGraph(nx.complement(self.Gd)) + self.Gk = nx.karate_club_graph() + self.Ak = _AntiGraph(nx.complement(self.Gk)) + self.GA = [(self.Gnp, self.Anp), + (self.Gd,self.Ad), + (self.Gk, self.Ak)] + + def test_size(self): + for G, A in self.GA: + n = G.order() + s = len(G.edges())+len(A.edges()) + assert_true(s == (n*(n-1))/2) + + def test_degree(self): + for G, A in self.GA: + assert_equal(G.degree(), A.degree()) + + def test_core_number(self): + for G, A in self.GA: + assert_equal(nx.core_number(G), nx.core_number(A)) + + def test_connected_components(self): + for G, A in self.GA: + gc = [set(c) for c in nx.connected_components(G)] + ac = [set(c) for c in nx.connected_components(A)] + for comp in ac: + assert_true(comp in gc) + + def test_adjacency_iter(self): + for G, A in self.GA: + a_adj = list(A.adjacency_iter()) + for n, nbrs in G.adjacency_iter(): + assert_true((n, set(nbrs)) in a_adj) + + def test_neighbors(self): + for G, A in self.GA: + node = list(G.nodes())[0] + assert_equal(set(G.neighbors(node)), set(A.neighbors(node))) + + def test_node_not_in_graph(self): + for G, A in self.GA: + node = 'non_existent_node' + assert_raises(nx.NetworkXError, A.neighbors, node) + assert_raises(nx.NetworkXError, A.neighbors_iter, node) + assert_raises(nx.NetworkXError, G.neighbors, node) + assert_raises(nx.NetworkXError, G.neighbors_iter, node) + + def test_degree(self): + for G, A in self.GA: + node = list(G.nodes())[0] + nodes = list(G.nodes())[1:4] + assert_equal(G.degree(node), A.degree(node)) + assert_equal(sum(G.degree().values()), sum(A.degree().values())) + # AntiGraph is a ThinGraph, so all the weights are 1 + assert_equal(sum(A.degree().values()), + sum(A.degree(weight='weight').values())) + assert_equal(sum(G.degree(nodes).values()), + sum(A.degree(nodes).values())) diff --git a/networkx/algorithms/block.py b/networkx/algorithms/block.py index cc2ff1d4..0c7d722b 100644 --- a/networkx/algorithms/block.py +++ b/networkx/algorithms/block.py @@ -80,7 +80,7 @@ def blockmodel(G,partitions,multigraph=False): # Add nodes and properties to blockmodel # The blockmodel nodes are node-induced subgraphs of G # Label them with integers starting at 0 - for i,p in zip(range(len(part)),part): + for i,p in enumerate(part): M.add_node(i) # The node-induced subgraph is stored as the node 'graph' attribute SG=G.subgraph(p) diff --git a/networkx/algorithms/centrality/eigenvector.py b/networkx/algorithms/centrality/eigenvector.py index 396d9e27..f1290c77 100644 --- a/networkx/algorithms/centrality/eigenvector.py +++ b/networkx/algorithms/centrality/eigenvector.py @@ -36,7 +36,7 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, G : graph A networkx graph - max_iter : interger, optional + max_iter : integer, optional Maximum number of iterations in power method. tol : float, optional diff --git a/networkx/algorithms/components/attracting.py b/networkx/algorithms/components/attracting.py index 6020927c..c5b21945 100644 --- a/networkx/algorithms/components/attracting.py +++ b/networkx/algorithms/components/attracting.py @@ -36,15 +36,15 @@ def attracting_components(G): Returns ------- - attractors : generator of list - The list of attracting components, sorted from largest attracting - component to smallest attracting component. + attractors : generator of sets + A generator of sets of nodes, one for each attracting component of G. See Also -------- number_attracting_components is_attracting_component attracting_component_subgraphs + """ scc = list(nx.strongly_connected_components(G)) cG = nx.condensation(G, scc) @@ -129,6 +129,7 @@ def attracting_component_subgraphs(G, copy=True): attracting_components number_attracting_components is_attracting_component + """ for ac in attracting_components(G): if copy: diff --git a/networkx/algorithms/components/biconnected.py b/networkx/algorithms/components/biconnected.py index 4db1a572..762e10b6 100644 --- a/networkx/algorithms/components/biconnected.py +++ b/networkx/algorithms/components/biconnected.py @@ -11,15 +11,19 @@ Biconnected components and articulation points. from itertools import chain import networkx as nx from networkx.utils.decorators import not_implemented_for + __author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>', 'Dan Schult <dschult@colgate.edu>', 'Aric Hagberg <aric.hagberg@gmail.com>']) -__all__ = ['biconnected_components', - 'biconnected_component_edges', - 'biconnected_component_subgraphs', - 'is_biconnected', - 'articulation_points', - ] + +__all__ = [ + 'biconnected_components', + 'biconnected_component_edges', + 'biconnected_component_subgraphs', + 'is_biconnected', + 'articulation_points', +] + @not_implemented_for('directed') def is_biconnected(G): @@ -48,18 +52,18 @@ def is_biconnected(G): Examples -------- - >>> G=nx.path_graph(4) + >>> G = nx.path_graph(4) >>> print(nx.is_biconnected(G)) False - >>> G.add_edge(0,3) + >>> G.add_edge(0, 3) >>> print(nx.is_biconnected(G)) True See Also -------- - biconnected_components, - articulation_points, - biconnected_component_edges, + biconnected_components + articulation_points + biconnected_component_edges biconnected_component_subgraphs Notes @@ -80,12 +84,14 @@ def is_biconnected(G): .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + """ bcc = list(biconnected_components(G)) if not bcc: # No bicomponents (it could be an empty graph) return False return len(bcc[0]) == len(G) + @not_implemented_for('directed') def biconnected_component_edges(G): """Return a generator of lists of edges, one list for each biconnected @@ -116,14 +122,18 @@ def biconnected_component_edges(G): Examples -------- - >>> G = nx.barbell_graph(4,2) + >>> G = nx.barbell_graph(4, 2) >>> print(nx.is_biconnected(G)) False - >>> components = nx.biconnected_component_edges(G) - >>> G.add_edge(2,8) + >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) + >>> len(bicomponents_edges) + 5 + >>> G.add_edge(2, 8) >>> print(nx.is_biconnected(G)) True - >>> components = nx.biconnected_component_edges(G) + >>> bicomponents_edges = list(nx.biconnected_component_edges(G)) + >>> len(bicomponents_edges) + 1 See Also -------- @@ -148,12 +158,14 @@ def biconnected_component_edges(G): References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). - "Efficient algorithms for graph manipulation". - Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + "Efficient algorithms for graph manipulation". + Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + """ - for comp in _biconnected_dfs(G,components=True): + for comp in _biconnected_dfs(G, components=True): yield comp + @not_implemented_for('directed') def biconnected_components(G): """Return a generator of sets of nodes, one set for each biconnected @@ -185,14 +197,30 @@ def biconnected_components(G): Examples -------- - >>> G = nx.barbell_graph(4,2) + >>> G = nx.lollipop_graph(5, 1) >>> print(nx.is_biconnected(G)) False - >>> components = nx.biconnected_components(G) - >>> G.add_edge(2,8) + >>> bicomponents = list(nx.biconnected_components(G)) + >>> len(bicomponents) + 2 + >>> G.add_edge(0, 5) >>> print(nx.is_biconnected(G)) True - >>> components = nx.biconnected_components(G) + >>> bicomponents = list(nx.biconnected_components(G)) + >>> len(bicomponents) + 1 + + You can generate a sorted list of biconnected components, largest + first, using sort. + + >>> G.remove_edge(0, 5) + >>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)] + [5, 2] + + If you only want the largest connected component, it's more + efficient to use max instead of sort. + + >>> Gc = max(nx.biconnected_components(G), key=len) See Also -------- @@ -217,10 +245,11 @@ def biconnected_components(G): References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). - "Efficient algorithms for graph manipulation". - Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + "Efficient algorithms for graph manipulation". + Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + """ - for comp in _biconnected_dfs(G,components=True): + for comp in _biconnected_dfs(G, components=True): yield set(chain.from_iterable(comp)) @not_implemented_for('directed') @@ -254,10 +283,32 @@ def biconnected_component_subgraphs(G, copy=True): Examples -------- - >>> G = nx.barbell_graph(4,2) + + >>> G = nx.lollipop_graph(5, 1) >>> print(nx.is_biconnected(G)) False - >>> subgraphs = list(nx.biconnected_component_subgraphs(G)) + >>> bicomponents = list(nx.biconnected_component_subgraphs(G)) + >>> len(bicomponents) + 2 + >>> G.add_edge(0, 5) + >>> print(nx.is_biconnected(G)) + True + >>> bicomponents = list(nx.biconnected_component_subgraphs(G)) + >>> len(bicomponents) + 1 + + You can generate a sorted list of biconnected components, largest + first, using sort. + + >>> G.remove_edge(0, 5) + >>> [len(c) for c in sorted(nx.biconnected_component_subgraphs(G), + ... key=len, reverse=True)] + [5, 2] + + If you only want the largest connected component, it's more + efficient to use max instead of sort. + + >>> Gc = max(nx.biconnected_component_subgraphs(G), key=len) See Also -------- @@ -284,8 +335,9 @@ def biconnected_component_subgraphs(G, copy=True): References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). - "Efficient algorithms for graph manipulation". - Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + "Efficient algorithms for graph manipulation". + Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + """ for comp_nodes in biconnected_components(G): if copy: @@ -293,6 +345,7 @@ def biconnected_component_subgraphs(G, copy=True): else: yield G.subgraph(comp_nodes) + @not_implemented_for('directed') def articulation_points(G): """Return a generator of articulation points, or cut vertices, of a graph. @@ -322,16 +375,17 @@ def articulation_points(G): Examples -------- - >>> G = nx.barbell_graph(4,2) + + >>> G = nx.barbell_graph(4, 2) >>> print(nx.is_biconnected(G)) False - >>> list(nx.articulation_points(G)) - [6, 5, 4, 3] - >>> G.add_edge(2,8) + >>> len(list(nx.articulation_points(G))) + 4 + >>> G.add_edge(2, 8) >>> print(nx.is_biconnected(G)) True - >>> list(nx.articulation_points(G)) - [] + >>> len(list(nx.articulation_points(G))) + 0 See Also -------- @@ -356,10 +410,12 @@ def articulation_points(G): References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). - "Efficient algorithms for graph manipulation". - Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + "Efficient algorithms for graph manipulation". + Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 + """ - return _biconnected_dfs(G,components=False) + return _biconnected_dfs(G, components=False) + @not_implemented_for('directed') def _biconnected_dfs(G, components=True): diff --git a/networkx/algorithms/components/connected.py b/networkx/algorithms/components/connected.py index 6152250a..45398538 100644 --- a/networkx/algorithms/components/connected.py +++ b/networkx/algorithms/components/connected.py @@ -2,7 +2,7 @@ """ Connected components. """ -# Copyright (C) 2004-2015 by +# Copyright (C) 2004-2013 by # Aric Hagberg <hagberg@lanl.gov> # Dan Schult <dschult@colgate.edu> # Pieter Swart <swart@lanl.gov> @@ -10,14 +10,18 @@ Connected components. # BSD license. import networkx as nx from networkx.utils.decorators import not_implemented_for -from networkx.algorithms.shortest_paths \ - import single_source_shortest_path_length as sp_length + __authors__ = "\n".join(['Eben Kenah', 'Aric Hagberg <aric.hagberg@gmail.com>' 'Christopher Ellison']) -__all__ = ['number_connected_components', 'connected_components', - 'connected_component_subgraphs','is_connected', - 'node_connected_component'] +__all__ = [ + 'number_connected_components', + 'connected_components', + 'connected_component_subgraphs', + 'is_connected', + 'node_connected_component', +] + @not_implemented_for('directed') def connected_components(G): @@ -30,8 +34,8 @@ def connected_components(G): Returns ------- - comp : generator of lists - A list of nodes for each component of G. + comp : generator of sets + A generator of sets of nodes, one for each component of G. Examples -------- @@ -39,8 +43,13 @@ def connected_components(G): >>> G = nx.path_graph(4) >>> G.add_path([10, 11, 12]) - >>> sorted(nx.connected_components(G), key = len, reverse=True) - [[0, 1, 2, 3], [10, 11, 12]] + >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)] + [4, 3] + + If you only want the largest connected component, it's more + efficient to use max instead of sort. + + >>> largest_cc = max(nx.connected_components(G), key=len) See Also -------- @@ -49,14 +58,16 @@ def connected_components(G): Notes ----- For undirected graphs only. + """ - seen={} + seen = set() for v in G: if v not in seen: - c = sp_length(G, v) - yield list(c) + c = set(_plain_bfs(G, v)) + yield c seen.update(c) + @not_implemented_for('directed') def connected_component_subgraphs(G, copy=True): """Generate connected components as subgraphs. @@ -80,6 +91,11 @@ def connected_component_subgraphs(G, copy=True): >>> G.add_edge(5,6) >>> graphs = list(nx.connected_component_subgraphs(G)) + If you only want the largest connected component, it's more + efficient to use max than sort. + + >>> Gc = max(nx.connected_component_subgraphs(G), key=len) + See Also -------- connected_components @@ -88,6 +104,7 @@ def connected_component_subgraphs(G, copy=True): ----- For undirected graphs only. Graph, node, and edge attributes are copied to the subgraphs by default. + """ for c in connected_components(G): if copy: @@ -95,6 +112,7 @@ def connected_component_subgraphs(G, copy=True): else: yield G.subgraph(c) + def number_connected_components(G): """Return the number of connected components. @@ -115,9 +133,11 @@ def number_connected_components(G): Notes ----- For undirected graphs only. + """ return len(list(connected_components(G))) + @not_implemented_for('directed') def is_connected(G): """Return True if the graph is connected, false otherwise. @@ -145,11 +165,13 @@ def is_connected(G): Notes ----- For undirected graphs only. + """ if len(G) == 0: raise nx.NetworkXPointlessConcept('Connectivity is undefined ', 'for the null graph.') - return len(sp_length(G, next(G.nodes_iter()))) == len(G) + return len(set(_plain_bfs(G, next(G.nodes_iter())))) == len(G) + @not_implemented_for('directed') def node_connected_component(G, n): @@ -165,8 +187,8 @@ def node_connected_component(G, n): Returns ------- - comp : lists - A list of nodes in component of G containing node n. + comp : set + A set of nodes in the component of G containing node n. See Also -------- @@ -175,5 +197,20 @@ def node_connected_component(G, n): Notes ----- For undirected graphs only. + """ - return list(sp_length(G, n)) + return set(_plain_bfs(G, n)) + + +def _plain_bfs(G, source): + """A fast BFS node generator""" + seen = set() + nextlevel = {source} + while nextlevel: + thislevel = nextlevel + nextlevel = set() + for v in thislevel: + if v not in seen: + yield v + seen.add(v) + nextlevel.update(G[v]) diff --git a/networkx/algorithms/components/strongly_connected.py b/networkx/algorithms/components/strongly_connected.py index 3e84ba7c..001ce044 100644 --- a/networkx/algorithms/components/strongly_connected.py +++ b/networkx/algorithms/components/strongly_connected.py @@ -9,6 +9,7 @@ # BSD license. import networkx as nx from networkx.utils.decorators import not_implemented_for + __authors__ = "\n".join(['Eben Kenah', 'Aric Hagberg (hagberg@lanl.gov)' 'Christopher Ellison', @@ -30,20 +31,38 @@ def strongly_connected_components(G): Parameters ---------- G : NetworkX Graph - An directed graph. + An directed graph. Returns ------- - comp : generator of lists - A list of nodes for each strongly connected component of G. + comp : generator of sets + A generator of sets of nodes, one for each strongly connected + component of G. Raises ------ - NetworkXNotImplemented: If G is undirected. + NetworkXNotImplemented: + If G is undirected. + + Examples + -------- + Generate a sorted list of strongly connected components, largest first. + + >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) + >>> G.add_cycle([10, 11, 12]) + >>> [len(c) for c in sorted(nx.strongly_connected_components(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> largest = max(nx.strongly_connected_components(G), key=len) See Also -------- - connected_components, weakly_connected_components + connected_components, + weakly_connected_components Notes ----- @@ -58,6 +77,7 @@ def strongly_connected_components(G): .. [2] On finding the strongly connected components in a directed graph. E. Nuutila and E. Soisalon-Soinen Information Processing Letters 49(1): 9-14, (1994).. + """ preorder = {} lowlink = {} @@ -90,11 +110,11 @@ def strongly_connected_components(G): queue.pop() if lowlink[v] == preorder[v]: scc_found[v] = True - scc = [v] + scc = {v} while scc_queue and preorder[scc_queue[-1]] > preorder[v]: k = scc_queue.pop() scc_found[k] = True - scc.append(k) + scc.add(k) yield scc else: scc_queue.append(v) @@ -107,37 +127,56 @@ def kosaraju_strongly_connected_components(G, source=None): Parameters ---------- G : NetworkX Graph - An directed graph. + An directed graph. Returns ------- - comp : generator of lists - A list of nodes for each component of G. + comp : generator of sets + A genrator of sets of nodes, one for each strongly connected + component of G. Raises ------ - NetworkXNotImplemented: If G is undirected. + NetworkXNotImplemented: + If G is undirected. + + Examples + -------- + Generate a sorted list of strongly connected components, largest first. + + >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) + >>> G.add_cycle([10, 11, 12]) + >>> [len(c) for c in sorted(nx.kosaraju_strongly_connected_components(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len) See Also -------- connected_components + weakly_connected_components Notes ----- Uses Kosaraju's algorithm. + """ with nx.utils.reversed(G): post = list(nx.dfs_postorder_nodes(G, source=source)) - seen = {} + seen = set() while post: r = post.pop() if r in seen: continue c = nx.dfs_preorder_nodes(G, r) - new = [v for v in c if v not in seen] - seen.update([(u, True) for u in new]) + new = {v for v in c if v not in seen} yield new + seen.update(new) @not_implemented_for('undirected') @@ -149,16 +188,33 @@ def strongly_connected_components_recursive(G): Parameters ---------- G : NetworkX Graph - An directed graph. + An directed graph. Returns ------- - comp : generator of lists - A list of nodes for each component of G. + comp : generator of sets + A generator of sets of nodes, one for each strongly connected + component of G. Raises ------ - NetworkXNotImplemented : If G is undirected + NetworkXNotImplemented: + If G is undirected + + Examples + -------- + Generate a sorted list of strongly connected components, largest first. + + >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) + >>> G.add_cycle([10, 11, 12]) + >>> [len(c) for c in sorted(nx.strongly_connected_components_recursive(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> largest = max(nx.strongly_connected_components_recursive(G), key=len) See Also -------- @@ -176,6 +232,7 @@ def strongly_connected_components_recursive(G): .. [2] On finding the strongly connected components in a directed graph. E. Nuutila and E. Soisalon-Soinen Information Processing Letters 49(1): 9-14, (1994).. + """ def visit(v, cnt): root[v] = cnt @@ -190,11 +247,11 @@ def strongly_connected_components_recursive(G): root[v] = min(root[v], root[w]) if root[v] == visited[v]: component[v] = root[v] - tmpc = [v] # hold nodes in this component + tmpc = {v} # hold nodes in this component while stack[-1] != v: w = stack.pop() component[w] = root[v] - tmpc.append(w) + tmpc.add(w) stack.remove(v) yield tmpc @@ -216,19 +273,37 @@ def strongly_connected_component_subgraphs(G, copy=True): Parameters ---------- G : NetworkX Graph - A graph. + A directed graph. + copy : boolean, optional - if copy is True, Graph, node, and edge attributes are copied to - the subgraphs. + if copy is True, Graph, node, and edge attributes are copied to + the subgraphs. Returns ------- - comp : generator of lists - A list of graphs, one for each strongly connected component of G. + comp : generator of graphs + A generator of graphs, one for each strongly connected component of G. + + Examples + -------- + Generate a sorted list of strongly connected components, largest first. + + >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) + >>> G.add_cycle([10, 11, 12]) + >>> [len(Gc) for Gc in sorted(nx.strongly_connected_component_subgraphs(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> Gc = max(nx.strongly_connected_component_subgraphs(G), key=len) See Also -------- connected_component_subgraphs + weakly_connected_component_subgraphs + """ for comp in strongly_connected_components(G): if copy: @@ -316,17 +391,19 @@ def condensation(G, scc=None): strongly connected components of G. C has a graph attribute named 'mapping' with a dictionary mapping the original nodes to the nodes in C to which they belong. Each node in C also has a node - attribute 'members' with the list of original nodes in G that + attribute 'members' with the set of original nodes in G that form the SCC that the node in C represents. Raises ------ - NetworkXNotImplemented: If G is not directed + NetworkXNotImplemented: + If G is not directed Notes ----- After contracting all strongly connected components to a single node, the resulting graph is a directed acyclic graph. + """ if scc is None: scc = nx.strongly_connected_components(G) diff --git a/networkx/algorithms/components/tests/test_attracting.py b/networkx/algorithms/components/tests/test_attracting.py index 1388f97d..92b4f9e2 100644 --- a/networkx/algorithms/components/tests/test_attracting.py +++ b/networkx/algorithms/components/tests/test_attracting.py @@ -7,65 +7,45 @@ from networkx import NetworkXNotImplemented class TestAttractingComponents(object): def setUp(self): self.G1 = nx.DiGraph() - self.G1.add_edges_from([(5,11),(11,2),(11,9),(11,10), - (7,11),(7,8),(8,9),(3,8),(3,10)]) + self.G1.add_edges_from([(5, 11), (11, 2), (11, 9), (11, 10), + (7, 11), (7, 8), (8, 9), (3, 8), (3, 10)]) self.G2 = nx.DiGraph() - self.G2.add_edges_from([(0,1),(0,2),(1,1),(1,2),(2,1)]) + self.G2.add_edges_from([(0, 1), (0, 2), (1, 1), (1, 2), (2, 1)]) self.G3 = nx.DiGraph() - self.G3.add_edges_from([(0,1),(1,2),(2,1),(0,3),(3,4),(4,3)]) + self.G3.add_edges_from([(0, 1), (1, 2), (2, 1), (0, 3), (3, 4), (4, 3)]) def test_attracting_components(self): ac = list(nx.attracting_components(self.G1)) - assert_true([2] in ac) - assert_true([9] in ac) - assert_true([10] in ac) + assert_true({2} in ac) + assert_true({9} in ac) + assert_true({10} in ac) ac = list(nx.attracting_components(self.G2)) ac = [tuple(sorted(x)) for x in ac] - assert_true(ac == [(1,2)]) + assert_true(ac == [(1, 2)]) ac = list(nx.attracting_components(self.G3)) ac = [tuple(sorted(x)) for x in ac] - assert_true((1,2) in ac) - assert_true((3,4) in ac) + assert_true((1, 2) in ac) + assert_true((3, 4) in ac) assert_equal(len(ac), 2) def test_number_attacting_components(self): - assert_equal(len(list(nx.attracting_components(self.G1))), 3) - assert_equal(len(list(nx.attracting_components(self.G2))), 1) - assert_equal(len(list(nx.attracting_components(self.G3))), 2) + assert_equal(nx.number_attracting_components(self.G1), 3) + assert_equal(nx.number_attracting_components(self.G2), 1) + assert_equal(nx.number_attracting_components(self.G3), 2) def test_is_attracting_component(self): assert_false(nx.is_attracting_component(self.G1)) assert_false(nx.is_attracting_component(self.G2)) assert_false(nx.is_attracting_component(self.G3)) - g2 = self.G3.subgraph([1,2]) + g2 = self.G3.subgraph([1, 2]) assert_true(nx.is_attracting_component(g2)) - def test_attracting_component_subgraphs(self): - subgraphs = list(nx.attracting_component_subgraphs(self.G1)) - for subgraph in subgraphs: - assert_equal(len(subgraph), 1) - - self.G2.add_edge(1,2,eattr='red') # test attrs copied to subgraphs - self.G2.node[2]['nattr']='blue' - self.G2.graph['gattr']='green' - subgraphs = list(nx.attracting_component_subgraphs(self.G2)) - assert_equal(len(subgraphs), 1) - SG2=subgraphs[0] - assert_true(1 in SG2) - assert_true(2 in SG2) - assert_equal(SG2[1][2]['eattr'],'red') - assert_equal(SG2.node[2]['nattr'],'blue') - assert_equal(SG2.graph['gattr'],'green') - SG2.add_edge(1,2,eattr='blue') - assert_equal(SG2[1][2]['eattr'],'blue') - assert_equal(self.G2[1][2]['eattr'],'red') - def test_connected_raise(self): G=nx.Graph() - assert_raises(NetworkXNotImplemented,nx.attracting_components,G) - assert_raises(NetworkXNotImplemented,nx.number_attracting_components,G) - assert_raises(NetworkXNotImplemented,nx.is_attracting_component,G) - assert_raises(NetworkXNotImplemented,nx.attracting_component_subgraphs,G) + assert_raises(NetworkXNotImplemented, nx.attracting_components, G) + assert_raises(NetworkXNotImplemented, nx.number_attracting_components, G) + assert_raises(NetworkXNotImplemented, nx.is_attracting_component, G) + assert_raises(NetworkXNotImplemented, nx.attracting_component_subgraphs, G) diff --git a/networkx/algorithms/components/tests/test_biconnected.py b/networkx/algorithms/components/tests/test_biconnected.py index b1b23ebe..74d120d1 100644 --- a/networkx/algorithms/components/tests/test_biconnected.py +++ b/networkx/algorithms/components/tests/test_biconnected.py @@ -4,131 +4,103 @@ import networkx as nx from networkx.algorithms.components import biconnected from networkx import NetworkXNotImplemented -def assert_components_equal(x,y): - sx = set((frozenset([frozenset(e) for e in c]) for c in x)) - sy = set((frozenset([frozenset(e) for e in c]) for c in y)) - assert_equal(sx,sy) +def assert_components_edges_equal(x, y): + sx = {frozenset([frozenset(e) for e in c]) for c in x} + sy = {frozenset([frozenset(e) for e in c]) for c in y} + assert_equal(sx, sy) + + +def assert_components_equal(x, y): + sx = {frozenset(c) for c in x} + sy = {frozenset(c) for c in y} + assert_equal(sx, sy) + def test_barbell(): - G=nx.barbell_graph(8,4) - G.add_path([7,20,21,22]) - G.add_cycle([22,23,24,25]) - pts=set(biconnected.articulation_points(G)) - assert_equal(pts,set([7,8,9,10,11,12,20,21,22])) - - answer = [set([12, 13, 14, 15, 16, 17, 18, 19]), - set([0, 1, 2, 3, 4, 5, 6, 7]), - set([22, 23, 24, 25]), - set([11, 12]), - set([10, 11]), - set([9, 10]), - set([8, 9]), - set([7, 8]), - set([21, 22]), - set([20, 21]), - set([7, 20])] - bcc=list(biconnected.biconnected_components(G)) - bcc.sort(key=len, reverse=True) - assert_equal(bcc,answer) + G = nx.barbell_graph(8, 4) + G.add_path([7, 20, 21, 22]) + G.add_cycle([22, 23, 24, 25]) + pts = set(nx.articulation_points(G)) + assert_equal(pts, {7, 8, 9, 10, 11, 12, 20, 21, 22}) + + answer = [ + {12, 13, 14, 15, 16, 17, 18, 19}, + {0, 1, 2, 3, 4, 5, 6, 7}, + {22, 23, 24, 25}, + {11, 12}, + {10, 11}, + {9, 10}, + {8, 9}, + {7, 8}, + {21, 22}, + {20, 21}, + {7, 20}, + ] + assert_components_equal(list(nx.biconnected_components(G)), answer) G.add_edge(2,17) - pts=set(biconnected.articulation_points(G)) - assert_equal(pts,set([7,20,21,22])) + pts = set(nx.articulation_points(G)) + assert_equal(pts, {7, 20, 21, 22}) def test_articulation_points_cycle(): G=nx.cycle_graph(3) - G.add_cycle([1,3,4]) - pts=set(biconnected.articulation_points(G)) - assert_equal(pts,set([1])) + G.add_cycle([1, 3, 4]) + pts=set(nx.articulation_points(G)) + assert_equal(pts, {1}) def test_is_biconnected(): G=nx.cycle_graph(3) - assert_true(biconnected.is_biconnected(G)) - G.add_cycle([1,3,4]) - assert_false(biconnected.is_biconnected(G)) + assert_true(nx.is_biconnected(G)) + G.add_cycle([1, 3, 4]) + assert_false(nx.is_biconnected(G)) def test_empty_is_biconnected(): G=nx.empty_graph(5) - assert_false(biconnected.is_biconnected(G)) - G.add_edge(0,1) - assert_false(biconnected.is_biconnected(G)) + assert_false(nx.is_biconnected(G)) + G.add_edge(0, 1) + assert_false(nx.is_biconnected(G)) def test_biconnected_components_cycle(): G=nx.cycle_graph(3) - G.add_cycle([1,3,4]) - pts = set(map(frozenset,biconnected.biconnected_components(G))) - assert_equal(pts,set([frozenset([0,1,2]),frozenset([1,3,4])])) + G.add_cycle([1, 3, 4]) + answer = [{0, 1, 2}, {1, 3, 4}] + assert_components_equal(list(nx.biconnected_components(G)), answer) def test_biconnected_component_subgraphs_cycle(): G=nx.cycle_graph(3) - G.add_cycle([1,3,4,5]) - G.add_edge(1,3,eattr='red') # test copying of edge data - G.node[1]['nattr']='blue' - G.graph['gattr']='green' - Gc = set(biconnected.biconnected_component_subgraphs(G)) - assert_equal(len(Gc),2) - g1,g2=Gc + G.add_cycle([1, 3, 4, 5]) + Gc = set(nx.biconnected_component_subgraphs(G)) + assert_equal(len(Gc), 2) + g1, g2=Gc if 0 in g1: - assert_true(nx.is_isomorphic(g1,nx.Graph([(0,1),(0,2),(1,2)]))) - assert_true(nx.is_isomorphic(g2,nx.Graph([(1,3),(1,5),(3,4),(4,5)]))) - assert_equal(g2[1][3]['eattr'],'red') - assert_equal(g2.node[1]['nattr'],'blue') - assert_equal(g2.graph['gattr'],'green') - g2[1][3]['eattr']='blue' - assert_equal(g2[1][3]['eattr'],'blue') - assert_equal(G[1][3]['eattr'],'red') + assert_true(nx.is_isomorphic(g1, nx.Graph([(0,1),(0,2),(1,2)]))) + assert_true(nx.is_isomorphic(g2, nx.Graph([(1,3),(1,5),(3,4),(4,5)]))) else: - assert_true(nx.is_isomorphic(g1,nx.Graph([(1,3),(1,5),(3,4),(4,5)]))) - assert_true(nx.is_isomorphic(g2,nx.Graph([(0,1),(0,2),(1,2)]))) - assert_equal(g1[1][3]['eattr'],'red') - assert_equal(g1.node[1]['nattr'],'blue') - assert_equal(g1.graph['gattr'],'green') - g1[1][3]['eattr']='blue' - assert_equal(g1[1][3]['eattr'],'blue') - assert_equal(G[1][3]['eattr'],'red') - + assert_true(nx.is_isomorphic(g1, nx.Graph([(1,3),(1,5),(3,4),(4,5)]))) + assert_true(nx.is_isomorphic(g2, nx.Graph([(0,1),(0,2),(1,2)]))) def test_biconnected_components1(): # graph example from # http://www.ibluemojo.com/school/articul_algorithm.html - edges=[(0,1), - (0,5), - (0,6), - (0,14), - (1,5), - (1,6), - (1,14), - (2,4), - (2,10), - (3,4), - (3,15), - (4,6), - (4,7), - (4,10), - (5,14), - (6,14), - (7,9), - (8,9), - (8,12), - (8,13), - (10,15), - (11,12), - (11,13), - (12,13)] + edges=[ + (0, 1), (0, 5), (0, 6), (0, 14), (1, 5), (1, 6), (1, 14), (2, 4), + (2, 10), (3, 4), (3, 15), (4, 6), (4, 7), (4, 10), (5, 14), (6, 14), + (7, 9), (8, 9), (8, 12), (8, 13), (10, 15), (11, 12), (11, 13), (12, 13) + ] G=nx.Graph(edges) - pts = set(biconnected.articulation_points(G)) - assert_equal(pts,set([4,6,7,8,9])) - comps = list(biconnected.biconnected_component_edges(G)) + pts = set(nx.articulation_points(G)) + assert_equal(pts, {4, 6, 7, 8, 9}) + comps = list(nx.biconnected_component_edges(G)) answer = [ - [(3,4),(15,3),(10,15),(10,4),(2,10),(4,2)], - [(13,12),(13,8),(11,13),(12,11),(8,12)], - [(9,8)], - [(7,9)], - [(4,7)], - [(6,4)], - [(14,0),(5,1),(5,0),(14,5),(14,1),(6,14),(6,0),(1,6),(0,1)], - ] - assert_components_equal(comps,answer) + [(3, 4), (15, 3), (10, 15), (10, 4), (2, 10), (4, 2)], + [(13, 12), (13, 8), (11, 13), (12, 11), (8, 12)], + [(9, 8)], + [(7, 9)], + [(4, 7)], + [(6, 4)], + [(14, 0), (5, 1), (5, 0), (14, 5), (14, 1), (6, 14), (6, 0), (1, 6), (0, 1)], + ] + assert_components_edges_equal(comps, answer) def test_biconnected_components2(): G=nx.Graph() @@ -137,64 +109,65 @@ def test_biconnected_components2(): G.add_cycle('FIJHG') G.add_cycle('GIJ') G.add_edge('E','G') - comps = list(biconnected.biconnected_component_edges(G)) + comps = list(nx.biconnected_component_edges(G)) answer = [ - [tuple('GF'),tuple('FI'),tuple('IG'),tuple('IJ'),tuple('JG'),tuple('JH'),tuple('HG')], + [tuple('GF'), tuple('FI'), tuple('IG'), tuple('IJ'), + tuple('JG'), tuple('JH'), tuple('HG')], [tuple('EG')], - [tuple('CD'),tuple('DE'),tuple('CE')], - [tuple('AB'),tuple('BC'),tuple('AC')] + [tuple('CD'), tuple('DE'), tuple('CE')], + [tuple('AB'), tuple('BC'), tuple('AC')] ] - assert_components_equal(comps,answer) + assert_components_edges_equal(comps, answer) def test_biconnected_davis(): D = nx.davis_southern_women_graph() - bcc = list(biconnected.biconnected_components(D))[0] + bcc = list(nx.biconnected_components(D))[0] assert_true(set(D) == bcc) # All nodes in a giant bicomponent # So no articulation points - assert_equal(list(biconnected.articulation_points(D)),[]) + assert_equal(len(list(nx.articulation_points(D))), 0) def test_biconnected_karate(): K = nx.karate_club_graph() - answer = [set([0, 1, 2, 3, 7, 8, 9, 12, 13, 14, 15, 17, 18, 19, - 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]), - set([0, 4, 5, 6, 10, 16]), - set([0, 11])] - bcc = list(biconnected.biconnected_components(K)) - bcc.sort(key=len, reverse=True) - assert_true(list(biconnected.biconnected_components(K)) == answer) - assert_equal(list(biconnected.articulation_points(K)),[0]) + answer = [{0, 1, 2, 3, 7, 8, 9, 12, 13, 14, 15, 17, 18, 19, + 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}, + {0, 4, 5, 6, 10, 16}, + {0, 11}] + bcc = list(nx.biconnected_components(K)) + assert_components_equal(bcc, answer) + assert_equal(set(nx.articulation_points(K)), {0}) def test_biconnected_eppstein(): # tests from http://www.ics.uci.edu/~eppstein/PADS/Biconnectivity.py G1 = nx.Graph({ - 0: [1,2,5], - 1: [0,5], - 2: [0,3,4], - 3: [2,4,5,6], - 4: [2,3,5,6], - 5: [0,1,3,4], - 6: [3,4]}) + 0: [1, 2, 5], + 1: [0, 5], + 2: [0, 3, 4], + 3: [2, 4, 5, 6], + 4: [2, 3, 5, 6], + 5: [0, 1, 3, 4], + 6: [3, 4], + }) G2 = nx.Graph({ - 0: [2,5], - 1: [3,8], - 2: [0,3,5], - 3: [1,2,6,8], + 0: [2, 5], + 1: [3, 8], + 2: [0, 3, 5], + 3: [1, 2, 6, 8], 4: [7], - 5: [0,2], - 6: [3,8], + 5: [0, 2], + 6: [3, 8], 7: [4], - 8: [1,3,6]}) - assert_true(biconnected.is_biconnected(G1)) - assert_false(biconnected.is_biconnected(G2)) - answer_G2 = [set([1, 3, 6, 8]), set([0, 2, 5]), set([2, 3]), set([4, 7])] - bcc = list(biconnected.biconnected_components(G2)) - bcc.sort(key=len, reverse=True) - assert_equal(bcc, answer_G2) + 8: [1, 3, 6], + }) + assert_true(nx.is_biconnected(G1)) + assert_false(nx.is_biconnected(G2)) + answer_G2 = [{1, 3, 6, 8}, {0, 2, 5}, {2, 3}, {4, 7}] + bcc = list(nx.biconnected_components(G2)) + assert_components_equal(bcc, answer_G2) def test_connected_raise(): DG = nx.DiGraph() - assert_raises(NetworkXNotImplemented,nx.biconnected_components,DG) - assert_raises(NetworkXNotImplemented,nx.biconnected_component_subgraphs,DG) - assert_raises(NetworkXNotImplemented,nx.biconnected_component_edges,DG) - assert_raises(NetworkXNotImplemented,nx.articulation_points,DG) - assert_raises(NetworkXNotImplemented,nx.is_biconnected,DG) + assert_raises(NetworkXNotImplemented, nx.biconnected_components, DG) + assert_raises(NetworkXNotImplemented, nx.biconnected_component_subgraphs, DG) + assert_raises(NetworkXNotImplemented, nx.biconnected_component_edges, DG) + assert_raises(NetworkXNotImplemented, nx.articulation_points, DG) + assert_raises(NetworkXNotImplemented, nx.is_biconnected, DG) diff --git a/networkx/algorithms/components/tests/test_connected.py b/networkx/algorithms/components/tests/test_connected.py index 72897f76..0cf4379e 100644 --- a/networkx/algorithms/components/tests/test_connected.py +++ b/networkx/algorithms/components/tests/test_connected.py @@ -7,66 +7,90 @@ from networkx import NetworkXError,NetworkXNotImplemented class TestConnected: def setUp(self): - G1=cnlti(nx.grid_2d_graph(2,2),first_label=0,ordering="sorted") - G2=cnlti(nx.lollipop_graph(3,3),first_label=4,ordering="sorted") - G3=cnlti(nx.house_graph(),first_label=10,ordering="sorted") - self.G=nx.union(G1,G2) - self.G=nx.union(self.G,G3) - self.DG=nx.DiGraph([(1,2),(1,3),(2,3)]) - self.grid=cnlti(nx.grid_2d_graph(4,4),first_label=1) + G1 = cnlti(nx.grid_2d_graph(2, 2), first_label=0, ordering="sorted") + G2 = cnlti(nx.lollipop_graph(3, 3), first_label=4, ordering="sorted") + G3 = cnlti(nx.house_graph(), first_label=10, ordering="sorted") + self.G = nx.union(G1, G2) + self.G = nx.union(self.G, G3) + self.DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)]) + self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1) + + self.gc = [] + G = nx.DiGraph() + G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5), + (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)]) + C = [[3, 4, 5, 7], [1, 2, 8], [6]] + self.gc.append((G, C)) + + G = nx.DiGraph() + G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)]) + C = [[2, 3, 4],[1]] + self.gc.append((G, C)) + + G = nx.DiGraph() + G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)]) + C = [[1, 2, 3]] + self.gc.append((G,C)) + + # Eppstein's tests + G = nx.DiGraph({0:[1], 1:[2, 3], 2:[4, 5], 3:[4, 5], 4:[6], 5:[], 6:[]}) + C = [[0], [1], [2],[ 3], [4], [5], [6]] + self.gc.append((G,C)) + + G = nx.DiGraph({0:[1], 1:[2, 3, 4], 2:[0, 3], 3:[4], 4:[3]}) + C = [[0, 1, 2], [3, 4]] + self.gc.append((G, C)) + def test_connected_components(self): - cc=nx.connected_components - G=self.G - C=[[0, 1, 2, 3], [4, 5, 6, 7, 8, 9], [10, 11, 12, 13, 14]] - assert_equal(sorted([sorted(g) for g in cc(G)]),sorted(C)) + cc = nx.connected_components + G = self.G + C = { + frozenset([0, 1, 2, 3]), + frozenset([4, 5, 6, 7, 8, 9]), + frozenset([10, 11, 12, 13, 14]) + } + assert_equal({frozenset(g) for g in cc(G)}, C) def test_number_connected_components(self): - ncc=nx.number_connected_components - assert_equal(ncc(self.G),3) + ncc = nx.number_connected_components + assert_equal(ncc(self.G), 3) def test_number_connected_components2(self): - ncc=nx.number_connected_components - assert_equal(ncc(self.grid),1) + ncc = nx.number_connected_components + assert_equal(ncc(self.grid), 1) def test_connected_components2(self): - cc=nx.connected_components - G=self.grid - C=[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]] - assert_equal(sorted([sorted(g) for g in cc(G)]),sorted(C)) + cc = nx.connected_components + G = self.grid + C = {frozenset([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])} + assert_equal({frozenset(g) for g in cc(G)}, C) def test_node_connected_components(self): - ncc=nx.node_connected_component - G=self.grid - C=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] - assert_equal(sorted(ncc(G,1)),sorted(C)) + ncc = nx.node_connected_component + G = self.grid + C = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} + assert_equal(ncc(G, 1), C) def test_connected_component_subgraphs(self): - G=self.grid - G.add_edge(1,2,eattr='red') # test attributes copied to subgraphs - G.node[1]['nattr']='blue' - G.graph['gattr']='green' - ccs=list(nx.connected_component_subgraphs(G)) - assert_equal(len(ccs),1) - sg=ccs[0] - assert_equal(sorted(sg.nodes()),list(range(1,17))) - assert_equal(sg[1][2]['eattr'],'red') - assert_equal(sg.node[1]['nattr'],'blue') - assert_equal(sg.graph['gattr'],'green') - sg[1][2]['eattr']='blue' - assert_equal(G[1][2]['eattr'],'red') - assert_equal(sg[1][2]['eattr'],'blue') - + wcc = nx.weakly_connected_component_subgraphs + cc = nx.connected_component_subgraphs + for G, C in self.gc: + U = G.to_undirected() + w = {frozenset(g) for g in wcc(G)} + c = {frozenset(g) for g in cc(U)} + assert_equal(w, c) def test_is_connected(self): assert_true(nx.is_connected(self.grid)) - G=nx.Graph() - G.add_nodes_from([1,2]) + G = nx.Graph() + G.add_nodes_from([1, 2]) assert_false(nx.is_connected(G)) def test_connected_raise(self): - assert_raises(NetworkXNotImplemented,nx.connected_components,self.DG) - assert_raises(NetworkXNotImplemented,nx.number_connected_components,self.DG) - assert_raises(NetworkXNotImplemented,nx.connected_component_subgraphs,self.DG) - assert_raises(NetworkXNotImplemented,nx.node_connected_component,self.DG,1) - assert_raises(NetworkXNotImplemented,nx.is_connected,self.DG) + assert_raises(NetworkXNotImplemented, nx.connected_components, self.DG) + assert_raises(NetworkXNotImplemented, nx.number_connected_components, self.DG) + assert_raises(NetworkXNotImplemented, nx.connected_component_subgraphs, self.DG) + assert_raises(NetworkXNotImplemented, nx.node_connected_component, self.DG,1) + assert_raises(NetworkXNotImplemented, nx.is_connected, self.DG) + assert_raises(nx.NetworkXPointlessConcept, nx.is_connected, nx.Graph()) diff --git a/networkx/algorithms/components/tests/test_strongly_connected.py b/networkx/algorithms/components/tests/test_strongly_connected.py index c1a9d119..5460d624 100644 --- a/networkx/algorithms/components/tests/test_strongly_connected.py +++ b/networkx/algorithms/components/tests/test_strongly_connected.py @@ -6,143 +6,140 @@ from networkx import NetworkXNotImplemented class TestStronglyConnected: def setUp(self): - self.gc=[] - G=nx.DiGraph() - G.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7), - (4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)]) - C=[[3, 4, 5, 7], [1, 2, 8], [6]] - self.gc.append((G,C)) - - G= nx.DiGraph() - G.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)]) - C = [[2, 3, 4],[1]] - self.gc.append((G,C)) - + self.gc = [] G = nx.DiGraph() - G.add_edges_from([(1,2),(2,3),(3,2),(2,1)]) - C = [[1, 2, 3]] - self.gc.append((G,C)) + G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5), + (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)]) + C = {frozenset([3, 4, 5, 7]), frozenset([1, 2, 8]), frozenset([6])} + self.gc.append((G, C)) - # Eppstein's tests - G = nx.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]}) - C = [[0],[1],[2],[3],[4],[5],[6]] - self.gc.append((G,C)) + G = nx.DiGraph() + G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)]) + C = {frozenset([2, 3, 4]), frozenset([1])} + self.gc.append((G, C)) - G = nx.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]}) - C = [[0,1,2],[3,4]] - self.gc.append((G,C)) + G = nx.DiGraph() + G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)]) + C = {frozenset([1, 2, 3])} + self.gc.append((G, C)) + # Eppstein's tests + G = nx.DiGraph({0: [1], 1:[2, 3], 2:[4, 5], 3:[4, 5], 4:[6], 5:[], 6:[]}) + C = { + frozenset([0]), + frozenset([1]), + frozenset([2]), + frozenset([3]), + frozenset([4]), + frozenset([5]), + frozenset([6]), + } + self.gc.append((G, C)) + + G = nx.DiGraph({0:[1], 1:[2, 3, 4], 2:[0, 3], 3:[4], 4:[3]}) + C = {frozenset([0, 1, 2]), frozenset([3, 4])} + self.gc.append((G, C)) def test_tarjan(self): - scc=nx.strongly_connected_components - for G,C in self.gc: - assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) - + scc = nx.strongly_connected_components + for G, C in self.gc: + assert_equal({frozenset(g) for g in scc(G)}, C) def test_tarjan_recursive(self): scc=nx.strongly_connected_components_recursive - for G,C in self.gc: - assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) - + for G, C in self.gc: + assert_equal({frozenset(g) for g in scc(G)}, C) def test_kosaraju(self): - scc=nx.kosaraju_strongly_connected_components - for G,C in self.gc: - assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) + scc = nx.kosaraju_strongly_connected_components + for G, C in self.gc: + assert_equal({frozenset(g) for g in scc(G)}, C) def test_number_strongly_connected_components(self): - ncc=nx.number_strongly_connected_components - for G,C in self.gc: - assert_equal(ncc(G),len(C)) + ncc = nx.number_strongly_connected_components + for G, C in self.gc: + assert_equal(ncc(G), len(C)) def test_is_strongly_connected(self): - for G,C in self.gc: - if len(C)==1: + for G, C in self.gc: + if len(C) == 1: assert_true(nx.is_strongly_connected(G)) else: assert_false(nx.is_strongly_connected(G)) - def test_strongly_connected_component_subgraphs(self): - scc=nx.strongly_connected_component_subgraphs - for G,C in self.gc: - assert_equal(sorted([sorted(g.nodes()) for g in scc(G)]),sorted(C)) - G,C=self.gc[0] - G.add_edge(1,2,eattr='red') - G.node[1]['nattr']='blue' - G.graph['gattr']='green' - sgs=sorted(list(scc(G)), key=len, reverse=False)[1] - assert_equal(sgs[1][2]['eattr'],'red') - assert_equal(sgs.node[1]['nattr'],'blue') - assert_equal(sgs.graph['gattr'],'green') - sgs[1][2]['eattr']='blue' - assert_equal(G[1][2]['eattr'],'red') - assert_equal(sgs[1][2]['eattr'],'blue') + scc = nx.strongly_connected_component_subgraphs + for G, C in self.gc: + assert_equal({frozenset(g) for g in scc(G)}, C) def test_contract_scc1(self): G = nx.DiGraph() - G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5), - (5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9), - (9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)]) + G.add_edges_from([ + (1, 2), (2, 3), (2, 11), (2, 12), (3, 4), (4, 3), (4, 5), (5, 6), + (6, 5), (6, 7), (7, 8), (7, 9), (7, 10), (8, 9), (9, 7), (10, 6), + (11, 2), (11, 4), (11, 6), (12, 6), (12, 11), + ]) scc = list(nx.strongly_connected_components(G)) cG = nx.condensation(G, scc) # DAG assert_true(nx.is_directed_acyclic_graph(cG)) - # # nodes - assert_equal(sorted(cG.nodes()),[0,1,2,3]) - # # edges + # nodes + assert_equal(sorted(cG.nodes()), [0, 1, 2, 3]) + # edges mapping={} - for i,component in enumerate(scc): + for i, component in enumerate(scc): for n in component: mapping[n] = i - edge=(mapping[2],mapping[3]) + edge = (mapping[2], mapping[3]) assert_true(cG.has_edge(*edge)) - edge=(mapping[2],mapping[5]) + edge = (mapping[2], mapping[5]) assert_true(cG.has_edge(*edge)) - edge=(mapping[3],mapping[5]) + edge = (mapping[3], mapping[5]) assert_true(cG.has_edge(*edge)) def test_contract_scc_isolate(self): # Bug found and fixed in [1687]. G = nx.DiGraph() - G.add_edge(1,2) - G.add_edge(2,1) + G.add_edge(1, 2) + G.add_edge(2, 1) scc = list(nx.strongly_connected_components(G)) cG = nx.condensation(G, scc) - assert_equal(cG.nodes(),[0]) - assert_equal(cG.edges(),[]) + assert_equal(list(cG.nodes()), [0]) + assert_equal(list(cG.edges()), []) def test_contract_scc_edge(self): G = nx.DiGraph() - G.add_edge(1,2) - G.add_edge(2,1) - G.add_edge(2,3) - G.add_edge(3,4) - G.add_edge(4,3) + G.add_edge(1, 2) + G.add_edge(2, 1) + G.add_edge(2, 3) + G.add_edge(3, 4) + G.add_edge(4, 3) scc = list(nx.strongly_connected_components(G)) cG = nx.condensation(G, scc) - assert_equal(cG.nodes(),[0,1]) + assert_equal(cG.nodes(), [0, 1]) if 1 in scc[0]: - edge = (0,1) + edge = (0, 1) else: - edge = (1,0) - assert_equal(cG.edges(),[edge]) + edge = (1, 0) + assert_equal(list(cG.edges()), [edge]) def test_condensation_mapping_and_members(self): G, C = self.gc[1] + C = sorted(C, key=len, reverse=True) cG = nx.condensation(G) mapping = cG.graph['mapping'] assert_true(all(n in G for n in mapping)) assert_true(all(0 == cN for n, cN in mapping.items() if n in C[0])) assert_true(all(1 == cN for n, cN in mapping.items() if n in C[1])) for n, d in cG.nodes(data=True): - assert_equal(C[n], cG.node[n]['members']) + assert_equal(set(C[n]), cG.node[n]['members']) def test_connected_raise(self): G=nx.Graph() - assert_raises(NetworkXNotImplemented,nx.strongly_connected_components,G) - assert_raises(NetworkXNotImplemented,nx.kosaraju_strongly_connected_components,G) - assert_raises(NetworkXNotImplemented,nx.strongly_connected_components_recursive,G) - assert_raises(NetworkXNotImplemented,nx.strongly_connected_component_subgraphs,G) - assert_raises(NetworkXNotImplemented,nx.is_strongly_connected,G) - assert_raises(NetworkXNotImplemented,nx.condensation,G) + assert_raises(NetworkXNotImplemented, nx.strongly_connected_components, G) + assert_raises(NetworkXNotImplemented, nx.kosaraju_strongly_connected_components, G) + assert_raises(NetworkXNotImplemented, nx.strongly_connected_components_recursive, G) + assert_raises(NetworkXNotImplemented, nx.strongly_connected_component_subgraphs, G) + assert_raises(NetworkXNotImplemented, nx.is_strongly_connected, G) + assert_raises(nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph()) + assert_raises(NetworkXNotImplemented, nx.condensation, G) diff --git a/networkx/algorithms/components/tests/test_subgraph_copies.py b/networkx/algorithms/components/tests/test_subgraph_copies.py new file mode 100644 index 00000000..b09e245b --- /dev/null +++ b/networkx/algorithms/components/tests/test_subgraph_copies.py @@ -0,0 +1,84 @@ +""" Tests for subgraphs attributes +""" +from copy import deepcopy +from nose.tools import assert_equal +import networkx as nx + +class TestSubgraphAttributesDicts: + + def setUp(self): + self.undirected = [ + nx.connected_component_subgraphs, + nx.biconnected_component_subgraphs, + ] + self.directed = [ + nx.weakly_connected_component_subgraphs, + nx.strongly_connected_component_subgraphs, + nx.attracting_component_subgraphs, + ] + self.subgraph_funcs = self.undirected + self.directed + + self.D = nx.DiGraph() + self.D.add_edge(1, 2, eattr='red') + self.D.add_edge(2, 1, eattr='red') + self.D.node[1]['nattr'] = 'blue' + self.D.graph['gattr'] = 'green' + + self.G = nx.Graph() + self.G.add_edge(1, 2, eattr='red') + self.G.node[1]['nattr'] = 'blue' + self.G.graph['gattr'] = 'green' + + def test_subgraphs_default_copy_behavior(self): + # Test the default behavior of subgraph functions + # For the moment (1.10) the default is to copy + for subgraph_func in self.subgraph_funcs: + G = deepcopy(self.G if subgraph_func in self.undirected else self.D) + SG = list(subgraph_func(G))[0] + assert_equal(SG[1][2]['eattr'], 'red') + assert_equal(SG.node[1]['nattr'], 'blue') + assert_equal(SG.graph['gattr'], 'green') + SG[1][2]['eattr'] = 'foo' + assert_equal(G[1][2]['eattr'], 'red') + assert_equal(SG[1][2]['eattr'], 'foo') + SG.node[1]['nattr'] = 'bar' + assert_equal(G.node[1]['nattr'], 'blue') + assert_equal(SG.node[1]['nattr'], 'bar') + SG.graph['gattr'] = 'baz' + assert_equal(G.graph['gattr'], 'green') + assert_equal(SG.graph['gattr'], 'baz') + + def test_subgraphs_copy(self): + for subgraph_func in self.subgraph_funcs: + test_graph = self.G if subgraph_func in self.undirected else self.D + G = deepcopy(test_graph) + SG = list(subgraph_func(G, copy=True))[0] + assert_equal(SG[1][2]['eattr'], 'red') + assert_equal(SG.node[1]['nattr'], 'blue') + assert_equal(SG.graph['gattr'], 'green') + SG[1][2]['eattr'] = 'foo' + assert_equal(G[1][2]['eattr'], 'red') + assert_equal(SG[1][2]['eattr'], 'foo') + SG.node[1]['nattr'] = 'bar' + assert_equal(G.node[1]['nattr'], 'blue') + assert_equal(SG.node[1]['nattr'], 'bar') + SG.graph['gattr'] = 'baz' + assert_equal(G.graph['gattr'], 'green') + assert_equal(SG.graph['gattr'], 'baz') + + def test_subgraphs_no_copy(self): + for subgraph_func in self.subgraph_funcs: + G = deepcopy(self.G if subgraph_func in self.undirected else self.D) + SG = list(subgraph_func(G, copy=False))[0] + assert_equal(SG[1][2]['eattr'], 'red') + assert_equal(SG.node[1]['nattr'], 'blue') + assert_equal(SG.graph['gattr'], 'green') + SG[1][2]['eattr'] = 'foo' + assert_equal(G[1][2]['eattr'], 'foo') + assert_equal(SG[1][2]['eattr'], 'foo') + SG.node[1]['nattr'] = 'bar' + assert_equal(G.node[1]['nattr'], 'bar') + assert_equal(SG.node[1]['nattr'], 'bar') + SG.graph['gattr'] = 'baz' + assert_equal(G.graph['gattr'], 'baz') + assert_equal(SG.graph['gattr'], 'baz') diff --git a/networkx/algorithms/components/tests/test_weakly_connected.py b/networkx/algorithms/components/tests/test_weakly_connected.py index 1ab29d0f..ead69897 100644 --- a/networkx/algorithms/components/tests/test_weakly_connected.py +++ b/networkx/algorithms/components/tests/test_weakly_connected.py @@ -6,82 +6,64 @@ from networkx import NetworkXNotImplemented class TestWeaklyConnected: def setUp(self): - self.gc=[] - G=nx.DiGraph() - G.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7), - (4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)]) - C=[[3, 4, 5, 7], [1, 2, 8], [6]] - self.gc.append((G,C)) + self.gc = [] + G = nx.DiGraph() + G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5), + (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)]) + C = [[3, 4, 5, 7], [1, 2, 8], [6]] + self.gc.append((G, C)) - G= nx.DiGraph() - G.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)]) + G = nx.DiGraph() + G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)]) C = [[2, 3, 4],[1]] - self.gc.append((G,C)) + self.gc.append((G, C)) G = nx.DiGraph() - G.add_edges_from([(1,2),(2,3),(3,2),(2,1)]) + G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)]) C = [[1, 2, 3]] self.gc.append((G,C)) # Eppstein's tests - G = nx.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]}) - C = [[0],[1],[2],[3],[4],[5],[6]] + G = nx.DiGraph({0:[1], 1:[2, 3], 2:[4, 5], 3:[4, 5], 4:[6], 5:[], 6:[]}) + C = [[0], [1], [2],[ 3], [4], [5], [6]] self.gc.append((G,C)) - G = nx.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]}) - C = [[0,1,2],[3,4]] - self.gc.append((G,C)) + G = nx.DiGraph({0:[1], 1:[2, 3, 4], 2:[0, 3], 3:[4], 4:[3]}) + C = [[0, 1, 2], [3, 4]] + self.gc.append((G, C)) def test_weakly_connected_components(self): - wcc=nx.weakly_connected_components - cc=nx.connected_components - for G,C in self.gc: - U=G.to_undirected() - w=sorted([sorted(g) for g in wcc(G)]) - c=sorted([sorted(g) for g in cc(U)]) - assert_equal(w,c) + for G, C in self.gc: + U = G.to_undirected() + w = {frozenset(g) for g in nx.weakly_connected_components(G)} + c = {frozenset(g) for g in nx.connected_components(U)} + assert_equal(w, c) def test_number_weakly_connected_components(self): - wcc=nx.number_weakly_connected_components - cc=nx.number_connected_components - for G,C in self.gc: - U=G.to_undirected() - w=wcc(G) - c=cc(U) - assert_equal(w,c) + for G, C in self.gc: + U = G.to_undirected() + w = nx.number_weakly_connected_components(G) + c = nx.number_connected_components(U) + assert_equal(w, c) def test_weakly_connected_component_subgraphs(self): - wcc=nx.weakly_connected_component_subgraphs - cc=nx.connected_component_subgraphs - for G,C in self.gc: - U=G.to_undirected() - w=sorted([sorted(g.nodes()) for g in wcc(G)]) - c=sorted([sorted(g.nodes()) for g in cc(U)]) - assert_equal(w,c) - G,C=self.gc[0] - G.add_edge(1,2,eattr='red') - G.node[1]['nattr']='blue' - G.graph['gattr']='green' - sgs=list(wcc(G))[0] - assert_equal(sgs[1][2]['eattr'],'red') - assert_equal(sgs.node[1]['nattr'],'blue') - assert_equal(sgs.graph['gattr'],'green') - sgs[1][2]['eattr']='blue' - assert_equal(G[1][2]['eattr'],'red') - assert_equal(sgs[1][2]['eattr'],'blue') + wcc = nx.weakly_connected_component_subgraphs + cc = nx.connected_component_subgraphs + for G, C in self.gc: + U = G.to_undirected() + w = {frozenset(g) for g in wcc(G)} + c = {frozenset(g) for g in cc(U)} + assert_equal(w, c) def test_is_weakly_connected(self): - wcc=nx.is_weakly_connected - cc=nx.is_connected - for G,C in self.gc: - U=G.to_undirected() - assert_equal(wcc(G),cc(U)) - + for G, C in self.gc: + U = G.to_undirected() + assert_equal(nx.is_weakly_connected(G), nx.is_connected(U)) def test_connected_raise(self): G=nx.Graph() - assert_raises(NetworkXNotImplemented,nx.weakly_connected_components,G) - assert_raises(NetworkXNotImplemented,nx.number_weakly_connected_components,G) - assert_raises(NetworkXNotImplemented,nx.weakly_connected_component_subgraphs,G) - assert_raises(NetworkXNotImplemented,nx.is_weakly_connected,G) + assert_raises(NetworkXNotImplemented,nx.weakly_connected_components, G) + assert_raises(NetworkXNotImplemented,nx.number_weakly_connected_components, G) + assert_raises(NetworkXNotImplemented,nx.weakly_connected_component_subgraphs, G) + assert_raises(NetworkXNotImplemented,nx.is_weakly_connected, G) diff --git a/networkx/algorithms/components/weakly_connected.py b/networkx/algorithms/components/weakly_connected.py index b85cc752..4ceb943d 100644 --- a/networkx/algorithms/components/weakly_connected.py +++ b/networkx/algorithms/components/weakly_connected.py @@ -10,44 +10,133 @@ import networkx as nx from networkx.utils.decorators import not_implemented_for + __authors__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)' 'Christopher Ellison']) -__all__ = ['number_weakly_connected_components', - 'weakly_connected_components', - 'weakly_connected_component_subgraphs', - 'is_weakly_connected' - ] + +__all__ = [ + 'number_weakly_connected_components', + 'weakly_connected_components', + 'weakly_connected_component_subgraphs', + 'is_weakly_connected', +] + @not_implemented_for('undirected') def weakly_connected_components(G): """Generate weakly connected components of G. + + Parameters + ---------- + G : NetworkX graph + A directed graph + + Returns + ------- + comp : generator of sets + A generator of sets of nodes, one for each weakly connected + component of G. + + Examples + -------- + Generate a sorted list of weakly connected components, largest first. + + >>> G = nx.path_graph(4, create_using=nx.DiGraph()) + >>> G.add_path([10, 11, 12]) + >>> [len(c) for c in sorted(nx.weakly_connected_components(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> largest_cc = max(nx.weakly_connected_components(G), key=len) + + See Also + -------- + strongly_connected_components + + Notes + ----- + For directed graphs only. + """ - seen={} + seen = set() for v in G: if v not in seen: - c=_single_source_shortest_unipath_length(G,v) - yield list(c.keys()) + c = set(_plain_bfs(G, v)) + yield c seen.update(c) + @not_implemented_for('undirected') def number_weakly_connected_components(G): - """Return the number of connected components in G. + """Return the number of weakly connected components in G. + + Parameters + ---------- + G : NetworkX graph + A directed graph. + + Returns + ------- + n : integer + Number of weakly connected components + + See Also + -------- + connected_components + + Notes + ----- For directed graphs only. + """ return len(list(weakly_connected_components(G))) + @not_implemented_for('undirected') def weakly_connected_component_subgraphs(G, copy=True): """Generate weakly connected components as subgraphs. Parameters ---------- - G : NetworkX Graph - A directed graph. + G : NetworkX graph + A directed graph. + + copy: bool (default=True) + If True make a copy of the graph attributes + + Returns + ------- + comp : generator + A generator of graphs, one for each weakly connected component of G. + + Examples + -------- + Generate a sorted list of weakly connected components, largest first. + + >>> G = nx.path_graph(4, create_using=nx.DiGraph()) + >>> G.add_path([10, 11, 12]) + >>> [len(c) for c in sorted(nx.weakly_connected_component_subgraphs(G), + ... key=len, reverse=True)] + [4, 3] + + If you only want the largest component, it's more efficient to + use max instead of sort. + + >>> Gc = max(nx.weakly_connected_component_subgraphs(G), key=len) + + See Also + -------- + strongly_connected_components + connected_components + + Notes + ----- + For directed graphs only. + Graph, node, and edge attributes are copied to the subgraphs by default. - copy : bool - If copy is True, graph, node, and edge attributes are copied to the - subgraphs. """ for comp in weakly_connected_components(G): if copy: @@ -55,6 +144,7 @@ def weakly_connected_component_subgraphs(G, copy=True): else: yield G.subgraph(comp) + @not_implemented_for('undirected') def is_weakly_connected(G): """Test directed graph for weak connectivity. @@ -65,12 +155,12 @@ def is_weakly_connected(G): Parameters ---------- G : NetworkX Graph - A directed graph. + A directed graph. Returns ------- connected : bool - True if the graph is weakly connected, False otherwise. + True if the graph is weakly connected, False otherwise. See Also -------- @@ -81,50 +171,34 @@ def is_weakly_connected(G): Notes ----- For directed graphs only. + """ - if len(G)==0: + if len(G) == 0: raise nx.NetworkXPointlessConcept( """Connectivity is undefined for the null graph.""") - return len(list(weakly_connected_components(G))[0])==len(G) + return len(list(weakly_connected_components(G))[0]) == len(G) + -def _single_source_shortest_unipath_length(G,source,cutoff=None): - """Compute the shortest path lengths from source to all reachable nodes. +def _plain_bfs(G, source): + """A fast BFS node generator The direction of the edge between nodes is ignored. For directed graphs only. - Parameters - ---------- - G : NetworkX graph - - source : node - Starting node for path - - cutoff : integer, optional - Depth to stop the search. Only paths of length <= cutoff are returned. - - Returns - ------- - lengths : dictionary - Dictionary of shortest path lengths keyed by target. """ - # namespace speedups Gsucc = G.succ Gpred = G.pred - seen={} # level (number of hops) when seen in BFS - level=0 # the current level - nextlevel = set([source]) # set of nodes to check at next level + seen = set() + nextlevel = {source} while nextlevel: - thislevel=nextlevel # advance to next level - nextlevel = set() # and start a new list (fringe) + thislevel = nextlevel + nextlevel = set() for v in thislevel: if v not in seen: - seen[v]=level # set the level of vertex v - nextlevel.update(Gsucc[v]) # add successors of v - nextlevel.update(Gpred[v]) # add predecessors of v - if (cutoff is not None and cutoff <= level): break - level=level+1 - return seen # return all path lengths as dictionary + yield v + seen.add(v) + nextlevel.update(Gsucc[v]) + nextlevel.update(Gpred[v]) diff --git a/networkx/algorithms/connectivity/__init__.py b/networkx/algorithms/connectivity/__init__.py index 3d60a4d4..75e878bc 100644 --- a/networkx/algorithms/connectivity/__init__.py +++ b/networkx/algorithms/connectivity/__init__.py @@ -2,12 +2,14 @@ """ from .connectivity import * from .cuts import * +from .kcomponents import * from .kcutsets import * from .stoerwagner import * from .utils import * __all__ = sum([connectivity.__all__, cuts.__all__, + kcomponents.__all__, kcutsets.__all__, stoerwagner.__all__, utils.__all__, diff --git a/networkx/algorithms/connectivity/kcomponents.py b/networkx/algorithms/connectivity/kcomponents.py new file mode 100644 index 00000000..5400cdd2 --- /dev/null +++ b/networkx/algorithms/connectivity/kcomponents.py @@ -0,0 +1,222 @@ +# -*- coding: utf-8 -*- +""" +Moody and White algorithm for k-components +""" +from collections import defaultdict +from itertools import combinations +from operator import itemgetter + +import networkx as nx +from networkx.utils import not_implemented_for +# Define the default maximum flow function. +from networkx.algorithms.flow import edmonds_karp +default_flow_func = edmonds_karp + +__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>']) + +__all__ = ['k_components'] + + +@not_implemented_for('directed') +def k_components(G, flow_func=None): + r"""Returns the k-component structure of a graph G. + + A `k`-component is a maximal subgraph of a graph G that has, at least, + node connectivity `k`: we need to remove at least `k` nodes to break it + into more components. `k`-components have an inherent hierarchical + structure because they are nested in terms of connectivity: a connected + graph can contain several 2-components, each of which can contain + one or more 3-components, and so forth. + + Parameters + ---------- + G : NetworkX graph + + flow_func : function + Function to perform the underlying flow computations. Default value + :meth:`edmonds_karp`. This function performs better in sparse graphs with + right tailed degree distributions. :meth:`shortest_augmenting_path` will + perform better in denser graphs. + + Returns + ------- + k_components : dict + Dictionary with all connectivity levels `k` in the input Graph as keys + and a list of sets of nodes that form a k-component of level `k` as + values. + + Raises + ------ + NetworkXNotImplemented: + If the input graph is directed. + + Examples + -------- + >>> # Petersen graph has 10 nodes and it is triconnected, thus all + >>> # nodes are in a single component on all three connectivity levels + >>> G = nx.petersen_graph() + >>> k_components = nx.k_components(G) + + Notes + ----- + Moody and White [1]_ (appendix A) provide an algorithm for identifying + k-components in a graph, which is based on Kanevsky's algorithm [2]_ + for finding all minimum-size node cut-sets of a graph (implemented in + :meth:`all_node_cuts` function): + + 1. Compute node connectivity, k, of the input graph G. + + 2. Identify all k-cutsets at the current level of connectivity using + Kanevsky's algorithm. + + 3. Generate new graph components based on the removal of + these cutsets. Nodes in a cutset belong to both sides + of the induced cut. + + 4. If the graph is neither complete nor trivial, return to 1; + else end. + + This implementation also uses some heuristics (see [3]_ for details) + to speed up the computation. + + See also + -------- + node_connectivity + all_node_cuts + + References + ---------- + .. [1] Moody, J. and D. White (2003). Social cohesion and embeddedness: + A hierarchical conception of social groups. + American Sociological Review 68(1), 103--28. + http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf + + .. [2] Kanevsky, A. (1993). Finding all minimum-size separating vertex + sets in a graph. Networks 23(6), 533--541. + http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract + + .. [3] Torrents, J. and F. Ferraro (2015). Structural Cohesion: + Visualization and Heuristics for Fast Computation. + http://arxiv.org/pdf/1503.04476v1 + + """ + # Dictionary with connectivity level (k) as keys and a list of + # sets of nodes that form a k-component as values. Note that + # k-compoents can overlap (but only k - 1 nodes). + k_components = defaultdict(list) + # Define default flow function + if flow_func is None: + flow_func = default_flow_func + # Bicomponents as a base to check for higher order k-components + for component in nx.connected_components(G): + # isolated nodes have connectivity 0 + comp = set(component) + if len(comp) > 1: + k_components[1].append(comp) + bicomponents = list(nx.biconnected_component_subgraphs(G)) + for bicomponent in bicomponents: + bicomp = set(bicomponent) + # avoid considering dyads as bicomponents + if len(bicomp) > 2: + k_components[2].append(bicomp) + for B in bicomponents: + if len(B) <= 2: + continue + k = nx.node_connectivity(B, flow_func=flow_func) + if k > 2: + k_components[k].append(set(B.nodes_iter())) + # Perform cuts in a DFS like order. + cuts = list(nx.all_node_cuts(B, k=k, flow_func=flow_func)) + stack = [(k, _generate_partition(B, cuts, k))] + while stack: + (parent_k, partition) = stack[-1] + try: + nodes = next(partition) + C = B.subgraph(nodes) + this_k = nx.node_connectivity(C, flow_func=flow_func) + if this_k > parent_k and this_k > 2: + k_components[this_k].append(set(C.nodes_iter())) + cuts = list(nx.all_node_cuts(C, k=this_k, flow_func=flow_func)) + if cuts: + stack.append((this_k, _generate_partition(C, cuts, this_k))) + except StopIteration: + stack.pop() + + # This is necessary because k-components may only be reported at their + # maximum k level. But we want to return a dictionary in which keys are + # connectivity levels and values list of sets of components, without + # skipping any connectivity level. Also, it's possible that subsets of + # an already detected k-component appear at a level k. Checking for this + # in the while loop above penalizes the common case. Thus we also have to + # _consolidate all connectivity levels in _reconstruct_k_components. + return _reconstruct_k_components(k_components) + + +def _consolidate(sets, k): + """Merge sets that share k or more elements. + + See: http://rosettacode.org/wiki/Set_consolidation + + The iterative python implementation posted there is + faster than this because of the overhead of building a + Graph and calling nx.connected_components, but it's not + clear for us if we can use it in NetworkX because there + is no licence for the code. + + """ + G = nx.Graph() + nodes = {i: s for i, s in enumerate(sets)} + G.add_nodes_from(nodes) + G.add_edges_from((u, v) for u, v in combinations(nodes, 2) + if len(nodes[u] & nodes[v]) >= k) + for component in nx.connected_components(G): + yield set.union(*[nodes[n] for n in component]) + + +def _generate_partition(G, cuts, k): + def has_nbrs_in_partition(G, node, partition): + for n in G[node]: + if n in partition: + return True + return False + components = [] + nodes = ({n for n, d in G.degree().items() if d > k} - + {n for cut in cuts for n in cut}) + H = G.subgraph(nodes) + for cc in nx.connected_components(H): + component = set(cc) + for cut in cuts: + for node in cut: + if has_nbrs_in_partition(G, node, cc): + component.add(node) + if len(component) < G.order(): + components.append(component) + for component in _consolidate(components, k+1): + yield component + + +def _reconstruct_k_components(k_comps): + result = dict() + max_k = max(k_comps) + for k in reversed(range(1, max_k+1)): + if k == max_k: + result[k] = list(_consolidate(k_comps[k], k)) + elif k not in k_comps: + result[k] = list(_consolidate(result[k+1], k)) + else: + nodes_at_k = set.union(*k_comps[k]) + to_add = [c for c in result[k+1] if any(n not in nodes_at_k for n in c)] + if to_add: + result[k] = list(_consolidate(k_comps[k] + to_add, k)) + else: + result[k] = list(_consolidate(k_comps[k], k)) + return result + + +def build_k_number_dict(kcomps): + result = {} + for k, comps in sorted(kcomps.items(), key=itemgetter(0)): + for comp in comps: + for node in comp: + result[node] = k + return result diff --git a/networkx/algorithms/connectivity/tests/test_kcomponents.py b/networkx/algorithms/connectivity/tests/test_kcomponents.py new file mode 100644 index 00000000..34716f8b --- /dev/null +++ b/networkx/algorithms/connectivity/tests/test_kcomponents.py @@ -0,0 +1,256 @@ +# Test for Moody and White k-components algorithm +from nose.tools import assert_equal, assert_true, raises +import networkx as nx +from networkx.algorithms.connectivity.kcomponents import ( + build_k_number_dict, + _consolidate, +) + +## +## A nice synthetic graph +## +def torrents_and_ferraro_graph(): + # Graph from http://arxiv.org/pdf/1503.04476v1 p.26 + G = nx.convert_node_labels_to_integers( + nx.grid_graph([5, 5]), + label_attribute='labels', + ) + rlabels = nx.get_node_attributes(G, 'labels') + labels = {v: k for k, v in rlabels.items()} + + for nodes in [(labels[(0,4)], labels[(1,4)]), + (labels[(3,4)], labels[(4,4)])]: + new_node = G.order() + 1 + # Petersen graph is triconnected + P = nx.petersen_graph() + G = nx.disjoint_union(G, P) + # Add two edges between the grid and P + G.add_edge(new_node+1, nodes[0]) + G.add_edge(new_node, nodes[1]) + # K5 is 4-connected + K = nx.complete_graph(5) + G = nx.disjoint_union(G, K) + # Add three edges between P and K5 + G.add_edge(new_node+2, new_node+11) + G.add_edge(new_node+3, new_node+12) + G.add_edge(new_node+4, new_node+13) + # Add another K5 sharing a node + G = nx.disjoint_union(G, K) + nbrs = G[new_node+10] + G.remove_node(new_node+10) + for nbr in nbrs: + G.add_edge(new_node+17, nbr) + # This edge makes the graph biconnected; it's + # needed because K5s share only one node. + G.add_edge(new_node+16, new_node+8) + + for nodes in [(labels[(0, 0)], labels[(1, 0)]), + (labels[(3, 0)], labels[(4, 0)])]: + new_node = G.order() + 1 + # Petersen graph is triconnected + P = nx.petersen_graph() + G = nx.disjoint_union(G, P) + # Add two edges between the grid and P + G.add_edge(new_node+1, nodes[0]) + G.add_edge(new_node, nodes[1]) + # K5 is 4-connected + K = nx.complete_graph(5) + G = nx.disjoint_union(G, K) + # Add three edges between P and K5 + G.add_edge(new_node+2, new_node+11) + G.add_edge(new_node+3, new_node+12) + G.add_edge(new_node+4, new_node+13) + # Add another K5 sharing two nodes + G = nx.disjoint_union(G,K) + nbrs = G[new_node+10] + G.remove_node(new_node+10) + for nbr in nbrs: + G.add_edge(new_node+17, nbr) + nbrs2 = G[new_node+9] + G.remove_node(new_node+9) + for nbr in nbrs2: + G.add_edge(new_node+18, nbr) + + G.name = 'Example graph for connectivity' + return G + +@raises(nx.NetworkXNotImplemented) +def test_directed(): + G = nx.gnp_random_graph(10, 0.2, directed=True) + nx.k_components(G) + +# Helper function +def _check_connectivity(G): + result = nx.k_components(G) + for k, components in result.items(): + if k < 3: + continue + for component in components: + C = G.subgraph(component) + assert_true(nx.node_connectivity(C) >= k) + +def test_torrents_and_ferraro_graph(): + G = torrents_and_ferraro_graph() + _check_connectivity(G) + +def test_random_gnp(): + G = nx.gnp_random_graph(50, 0.2) + _check_connectivity(G) + +def test_shell(): + constructor=[(20, 80, 0.8), (80, 180, 0.6)] + G = nx.random_shell_graph(constructor) + _check_connectivity(G) + +def test_configuration(): + deg_seq = nx.utils.create_degree_sequence(100, nx.utils.powerlaw_sequence) + G = nx.Graph(nx.configuration_model(deg_seq)) + G.remove_edges_from(G.selfloop_edges()) + _check_connectivity(G) + +def test_karate(): + G = nx.karate_club_graph() + _check_connectivity(G) + +def test_karate_component_number(): + karate_k_num = { + 0: 4, 1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 3, 7: 4, 8: 4, 9: 2, + 10: 3, 11: 1, 12: 2, 13: 4, 14: 2, 15: 2, 16: 2, 17: 2, + 18: 2, 19: 3, 20: 2, 21: 2, 22: 2, 23: 3, 24: 3, 25: 3, + 26: 2, 27: 3, 28: 3, 29: 3, 30: 4, 31: 3, 32: 4, 33: 4 + } + G = nx.karate_club_graph() + k_components = nx.k_components(G) + k_num = build_k_number_dict(k_components) + assert_equal(karate_k_num, k_num) + + +def test_torrents_and_ferraro_detail_3_and_4(): + solution = { + 3: [{25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 42}, + {44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 61}, + {63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 79, 80}, + {81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 93, 94, 95, 99, 100}, + {39, 40, 41, 42, 43}, + {58, 59, 60, 61, 62}, + {76, 77, 78, 79, 80}, + {96, 97, 98, 99, 100}, + ], + 4: [{35, 36, 37, 38, 42}, + {39, 40, 41, 42, 43}, + {54, 55, 56, 57, 61}, + {58, 59, 60, 61, 62}, + {73, 74, 75, 79, 80}, + {76, 77, 78, 79, 80}, + {93, 94, 95, 99, 100}, + {96, 97, 98, 99, 100}, + ], + } + G = torrents_and_ferraro_graph() + result = nx.k_components(G) + for k, components in result.items(): + if k < 3: + continue + assert_true(len(components) == len(solution[k])) + for component in components: + assert_true(component in solution[k]) + +def test_davis_southern_women(): + G = nx.davis_southern_women_graph() + _check_connectivity(G) + +def test_davis_southern_women_detail_3_and_4(): + solution = { + 3: [{ + 'Nora Fayette', + 'E10', + 'Myra Liddel', + 'E12', + 'E14', + 'Frances Anderson', + 'Evelyn Jefferson', + 'Ruth DeSand', + 'Helen Lloyd', + 'Eleanor Nye', + 'E9', + 'E8', + 'E5', + 'E4', + 'E7', + 'E6', + 'E1', + 'Verne Sanderson', + 'E3', + 'E2', + 'Theresa Anderson', + 'Pearl Oglethorpe', + 'Katherina Rogers', + 'Brenda Rogers', + 'E13', + 'Charlotte McDowd', + 'Sylvia Avondale', + 'Laura Mandeville', + }, + ], + 4: [{ + 'Nora Fayette', + 'E10', + 'Verne Sanderson', + 'E12', + 'Frances Anderson', + 'Evelyn Jefferson', + 'Ruth DeSand', + 'Helen Lloyd', + 'Eleanor Nye', + 'E9', + 'E8', + 'E5', + 'E4', + 'E7', + 'E6', + 'Myra Liddel', + 'E3', + 'Theresa Anderson', + 'Katherina Rogers', + 'Brenda Rogers', + 'Charlotte McDowd', + 'Sylvia Avondale', + 'Laura Mandeville', + }, + ], + } + G = nx.davis_southern_women_graph() + result = nx.k_components(G) + for k, components in result.items(): + if k < 3: + continue + assert_true(len(components) == len(solution[k])) + for component in components: + assert_true(component in solution[k]) + + +def test_set_consolidation_rosettacode(): + # Tests from http://rosettacode.org/wiki/Set_consolidation + def list_of_sets_equal(result, solution): + assert_equal( + {frozenset(s) for s in result}, + {frozenset(s) for s in solution} + ) + question = [{'A', 'B'}, {'C', 'D'}] + solution = [{'A', 'B'}, {'C', 'D'}] + list_of_sets_equal(_consolidate(question, 1), solution) + question = [{'A', 'B'}, {'B', 'C'}] + solution = [{'A', 'B', 'C'}] + list_of_sets_equal(_consolidate(question, 1), solution) + question = [{'A', 'B'}, {'C', 'D'}, {'D', 'B'}] + solution = [{'A', 'C', 'B', 'D'}] + list_of_sets_equal(_consolidate(question, 1), solution) + question = [{'H', 'I', 'K'}, {'A', 'B'}, {'C', 'D'}, {'D', 'B'}, {'F', 'G', 'H'}] + solution = [{'A', 'C', 'B', 'D'}, {'G', 'F', 'I', 'H', 'K'}] + list_of_sets_equal(_consolidate(question, 1), solution) + question = [{'A','H'}, {'H','I','K'}, {'A','B'}, {'C','D'}, {'D','B'}, {'F','G','H'}] + solution = [{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}] + list_of_sets_equal(_consolidate(question, 1), solution) + question = [{'H','I','K'}, {'A','B'}, {'C','D'}, {'D','B'}, {'F','G','H'}, {'A','H'}] + solution = [{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}] + list_of_sets_equal(_consolidate(question, 1), solution) diff --git a/networkx/algorithms/cycles.py b/networkx/algorithms/cycles.py index ca5c90d7..dd0b8d5a 100644 --- a/networkx/algorithms/cycles.py +++ b/networkx/algorithms/cycles.py @@ -127,8 +127,17 @@ def simple_cycles(G): Examples -------- >>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]) - >>> list(nx.simple_cycles(G)) - [[2], [2, 1], [2, 0], [2, 0, 1], [0]] + >>> len(list(nx.simple_cycles(G))) + 5 + + To filter the cycles so that they don't include certain nodes or edges, + copy your graph and eliminate those nodes or edges before calling:: + + >>> copyG = G.copy() + >>> copyG.remove_nodes_from([1]) + >>> copyG.remove_edges_from([(0, 1)]) + >>> len(list(nx.simple_cycles(copyG))) + 3 Notes ----- @@ -137,15 +146,6 @@ def simple_cycles(G): The time complexity is `O((n+e)(c+1))` for `n` nodes, `e` edges and `c` elementary circuits. - To filter the cycles so that they don't include certain nodes or edges, - copy your graph and eliminate those nodes or edges before calling:: - - >>> copyG = G.copy() - >>> copyG.remove_nodes_from([1]) - >>> copyG.remove_edges_from([(0,1)]) - >>> list(nx.simple_cycles(copyG)) - [[2], [2, 0], [0]] - References ---------- .. [1] Finding all the elementary circuits of a directed graph. @@ -160,6 +160,7 @@ def simple_cycles(G): See Also -------- cycle_basis + """ def _unblock(thisnode,blocked,B): stack=set([thisnode]) diff --git a/networkx/algorithms/flow/preflowpush.py b/networkx/algorithms/flow/preflowpush.py index f9136c29..3db0ae09 100644 --- a/networkx/algorithms/flow/preflowpush.py +++ b/networkx/algorithms/flow/preflowpush.py @@ -102,7 +102,7 @@ def preflow_push_impl(G, s, t, capacity, residual, global_relabel_freq, push(s, u, flow) # Partition nodes into levels. - levels = [Level() for i in range(2 * n - 1)] + levels = [Level() for i in range(2 * n)] for u in R: if u != s and u != t: level = levels[R_node[u]['height']] diff --git a/networkx/algorithms/flow/tests/test_maxflow.py b/networkx/algorithms/flow/tests/test_maxflow.py index 2db7b6bb..681e9e47 100644 --- a/networkx/algorithms/flow/tests/test_maxflow.py +++ b/networkx/algorithms/flow/tests/test_maxflow.py @@ -434,6 +434,14 @@ def test_preflow_push_global_relabel_freq(): assert_raises(nx.NetworkXError, preflow_push, G, 1, 2, global_relabel_freq=-1) +def test_preflow_push_makes_enough_space(): + #From ticket #1542 + G = nx.DiGraph() + G.add_path([0, 1, 3], capacity=1) + G.add_path([1, 2, 3], capacity=1) + R = preflow_push(G, 0, 3, value_only=False) + assert_equal(R.graph['flow_value'], 1) + def test_shortest_augmenting_path_two_phase(): k = 5 p = 1000 diff --git a/networkx/algorithms/matching.py b/networkx/algorithms/matching.py index fcd5729c..dbf861a8 100644 --- a/networkx/algorithms/matching.py +++ b/networkx/algorithms/matching.py @@ -93,6 +93,9 @@ def max_weight_matching(G, maxcardinality=False): paths and the "primal-dual" method for finding a matching of maximum weight, both methods invented by Jack Edmonds [1]_. + Bipartite graphs can also be matched using the functions present in + :mod:`networkx.algorithms.bipartite.matching`. + References ---------- .. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs", diff --git a/networkx/algorithms/minors.py b/networkx/algorithms/minors.py index 56d3141c..f91c0be4 100644 --- a/networkx/algorithms/minors.py +++ b/networkx/algorithms/minors.py @@ -12,7 +12,8 @@ from itertools import combinations from itertools import permutations from itertools import product -__all__ = ['contracted_edge', 'contracted_nodes', 'quotient_graph'] +__all__ = ['contracted_edge', 'contracted_nodes', + 'identified_nodes', 'quotient_graph'] def peek(iterable): @@ -219,6 +220,9 @@ def contracted_nodes(G, u, v, self_loops=True): contracted_edge quotient_graph + Notes + ----- + This function is also available as ``identified_nodes``. """ H = G.copy() if H.is_directed(): @@ -239,6 +243,8 @@ def contracted_nodes(G, u, v, self_loops=True): H.node[u]['contraction'] = {v: v_data} return H +identified_nodes = contracted_nodes + def contracted_edge(G, edge, self_loops=True): """Returns the graph that results from contracting the specified edge. diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py index 5849ab47..db6799a5 100644 --- a/networkx/algorithms/shortest_paths/tests/test_weighted.py +++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py @@ -339,14 +339,6 @@ class TestJohnsonAlgorithm: '0': ['0'], '3': ['0', '1', '2', '3'], '2': ['0', '1', '2']}, '3': {'3': ['3']}, '2': {'3': ['2', '3'], '2': ['2']}}) - paths = nx.johnson(G, new_weight='new_weight') - assert_equal(paths, {'1': {'1': ['1'], '3': ['1', '2', '3'], - '2': ['1', '2']}, '0': {'1': ['0', '1'], - '0': ['0'], '3': ['0', '1', '2', '3'], - '2': ['0', '1', '2']}, '3': {'3': ['3']}, - '2': {'3': ['2', '3'], '2': ['2']}}) - for u, v, w in G.edges(data=True): - assert_true('new_weight' in w) @raises(nx.NetworkXError) def test_unweighted_graph(self): diff --git a/networkx/algorithms/shortest_paths/unweighted.py b/networkx/algorithms/shortest_paths/unweighted.py index f179edb8..dc558569 100644 --- a/networkx/algorithms/shortest_paths/unweighted.py +++ b/networkx/algorithms/shortest_paths/unweighted.py @@ -66,15 +66,16 @@ def single_source_shortest_path_length(G,source,cutoff=None): return seen # return all path lengths as dictionary -def all_pairs_shortest_path_length(G,cutoff=None): - """ Compute the shortest path lengths between all nodes in G. +def all_pairs_shortest_path_length(G, cutoff=None): + """Computes the shortest path lengths between all nodes in ``G``. Parameters ---------- G : NetworkX graph cutoff : integer, optional - depth to stop the search. Only paths of length <= cutoff are returned. + Depth at which to stop the search. Only paths of length at most + ``cutoff`` are returned. Returns ------- @@ -87,20 +88,17 @@ def all_pairs_shortest_path_length(G,cutoff=None): Examples -------- - >>> G=nx.path_graph(5) - >>> length=nx.all_pairs_shortest_path_length(G) + >>> G = nx.path_graph(5) + >>> length = nx.all_pairs_shortest_path_length(G) >>> print(length[1][4]) 3 >>> length[1] {0: 1, 1: 0, 2: 1, 3: 2, 4: 3} """ - paths={} - for n in G: - paths[n]=single_source_shortest_path_length(G,n,cutoff=cutoff) - return paths - - + length = single_source_shortest_path_length + # TODO This can be trivially parallelized. + return {n: length(G, n, cutoff=cutoff) for n in G} def bidirectional_shortest_path(G,source,target): @@ -258,15 +256,16 @@ def single_source_shortest_path(G,source,cutoff=None): return paths -def all_pairs_shortest_path(G,cutoff=None): - """ Compute shortest paths between all nodes. +def all_pairs_shortest_path(G, cutoff=None): + """Compute shortest paths between all nodes. Parameters ---------- G : NetworkX graph cutoff : integer, optional - Depth to stop the search. Only paths of length <= cutoff are returned. + Depth at which to stop the search. Only paths of length at most + ``cutoff`` are returned. Returns ------- @@ -275,8 +274,8 @@ def all_pairs_shortest_path(G,cutoff=None): Examples -------- - >>> G=nx.path_graph(5) - >>> path=nx.all_pairs_shortest_path(G) + >>> G = nx.path_graph(5) + >>> path = nx.all_pairs_shortest_path(G) >>> print(path[0][4]) [0, 1, 2, 3, 4] @@ -285,12 +284,8 @@ def all_pairs_shortest_path(G,cutoff=None): floyd_warshall() """ - paths={} - for n in G: - paths[n]=single_source_shortest_path(G,n,cutoff=cutoff) - return paths - - + # TODO This can be trivially parallelized. + return {n: single_source_shortest_path(G, n, cutoff=cutoff) for n in G} def predecessor(G,source,target=None,cutoff=None,return_seen=None): @@ -357,4 +352,3 @@ def predecessor(G,source,target=None,cutoff=None,return_seen=None): return (pred,seen) else: return pred - diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py index b46bff61..135f2525 100644 --- a/networkx/algorithms/shortest_paths/weighted.py +++ b/networkx/algorithms/shortest_paths/weighted.py @@ -29,7 +29,6 @@ __all__ = ['dijkstra_path', from collections import deque from heapq import heappush, heappop from itertools import count -import uuid import networkx as nx from networkx.utils import generate_unique_node @@ -220,42 +219,13 @@ def single_source_dijkstra_path_length(G, source, cutoff=None, single_source_dijkstra() """ - push = heappush - pop = heappop - dist = {} # dictionary of final distances - seen = {source: 0} - c = count() - fringe = [] # use heapq with (distance,label) tuples - push(fringe, (0, next(c), source)) - while fringe: - (d, _, v) = pop(fringe) - if v in dist: - continue # already searched this node. - dist[v] = d - # for ignore,w,edgedata in G.edges_iter(v,data=True): - # is about 30% slower than the following - if G.is_multigraph(): - edata = [] - for w, keydata in G[v].items(): - minweight = min((dd.get(weight, 1) - for k, dd in keydata.items())) - edata.append((w, {weight: minweight})) - else: - edata = iter(G[v].items()) - - for w, edgedata in edata: - vw_dist = dist[v] + edgedata.get(weight, 1) - if cutoff is not None: - if vw_dist > cutoff: - continue - if w in dist: - if vw_dist < dist[w]: - raise ValueError('Contradictory paths found:', - 'negative weights?') - elif w not in seen or vw_dist < seen[w]: - seen[w] = vw_dist - push(fringe, (vw_dist, next(c), w)) - return dist + if G.is_multigraph(): + get_weight = lambda u, v, data: min( + eattr.get(weight, 1) for eattr in data.values()) + else: + get_weight = lambda u, v, data: data.get(weight, 1) + + return _dijkstra(G, source, get_weight, cutoff=cutoff) def single_source_dijkstra(G, source, target=None, cutoff=None, weight='weight'): @@ -314,10 +284,63 @@ def single_source_dijkstra(G, source, target=None, cutoff=None, weight='weight') """ if source == target: return ({source: 0}, {source: [source]}) + + if G.is_multigraph(): + get_weight = lambda u, v, data: min( + eattr.get(weight, 1) for eattr in data.values()) + else: + get_weight = lambda u, v, data: data.get(weight, 1) + + paths = {source: [source]} # dictionary of paths + return _dijkstra(G, source, get_weight, paths=paths, cutoff=cutoff, + target=target) + + +def _dijkstra(G, source, get_weight, pred=None, paths=None, cutoff=None, + target=None): + """Implementation of Dijkstra's algorithm + + Parameters + ---------- + G : NetworkX graph + + source : node label + Starting node for path + + get_weight: function + Function for getting edge weight + + pred: list, optional(default=None) + List of predecessors of a node + + paths: dict, optional (default=None) + Path from the source to a target node. + + target : node label, optional + Ending node for path + + cutoff : integer or float, optional + Depth to stop the search. Only paths of length <= cutoff are returned. + + Returns + ------- + distance,path : dictionaries + Returns a tuple of two dictionaries keyed by node. + The first dictionary stores distance from the source. + The second stores the path from the source to that node. + + pred,distance : dictionaries + Returns two dictionaries representing a list of predecessors + of a node and the distance to each node. + + distance : dictionary + Dictionary of shortest lengths keyed by target. + """ + G_succ = G.succ if G.is_directed() else G.adj + push = heappush pop = heappop dist = {} # dictionary of final distances - paths = {source: [source]} # dictionary of paths seen = {source: 0} c = count() fringe = [] # use heapq with (distance,label) tuples @@ -329,31 +352,35 @@ def single_source_dijkstra(G, source, target=None, cutoff=None, weight='weight') dist[v] = d if v == target: break - # for ignore,w,edgedata in G.edges_iter(v,data=True): - # is about 30% slower than the following - if G.is_multigraph(): - edata = [] - for w, keydata in G[v].items(): - minweight = min((dd.get(weight, 1) - for k, dd in keydata.items())) - edata.append((w, {weight: minweight})) - else: - edata = iter(G[v].items()) - - for w, edgedata in edata: - vw_dist = dist[v] + edgedata.get(weight, 1) + + for u, e in G_succ[v].items(): + cost = get_weight(v, u, e) + if cost is None: + continue + vu_dist = dist[v] + get_weight(v, u, e) if cutoff is not None: - if vw_dist > cutoff: + if vu_dist > cutoff: continue - if w in dist: - if vw_dist < dist[w]: + if u in dist: + if vu_dist < dist[u]: raise ValueError('Contradictory paths found:', 'negative weights?') - elif w not in seen or vw_dist < seen[w]: - seen[w] = vw_dist - push(fringe, (vw_dist, next(c), w)) - paths[w] = paths[v] + [w] - return (dist, paths) + elif u not in seen or vu_dist < seen[u]: + seen[u] = vu_dist + push(fringe, (vu_dist, next(c), u)) + if paths is not None: + paths[u] = paths[v] + [u] + if pred is not None: + pred[u] = [v] + elif vu_dist == seen[u]: + if pred is not None: + pred[u].append(v) + + if paths is not None: + return (dist, paths) + if pred is not None: + return (pred, dist) + return dist def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight='weight'): @@ -387,43 +414,14 @@ def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight='weight'): The list of predecessors contains more than one element only when there are more than one shortest paths to the key node. """ - push = heappush - pop = heappop - dist = {} # dictionary of final distances + if G.is_multigraph(): + get_weight = lambda u, v, data: min( + eattr.get(weight, 1) for eattr in data.values()) + else: + get_weight = lambda u, v, data: data.get(weight, 1) + pred = {source: []} # dictionary of predecessors - seen = {source: 0} - c = count() - fringe = [] # use heapq with (distance,label) tuples - push(fringe, (0, next(c), source)) - while fringe: - (d, _, v) = pop(fringe) - if v in dist: - continue # already searched this node. - dist[v] = d - if G.is_multigraph(): - edata = [] - for w, keydata in G[v].items(): - minweight = min((dd.get(weight, 1) - for k, dd in keydata.items())) - edata.append((w, {weight: minweight})) - else: - edata = iter(G[v].items()) - for w, edgedata in edata: - vw_dist = dist[v] + edgedata.get(weight, 1) - if cutoff is not None: - if vw_dist > cutoff: - continue - if w in dist: - if vw_dist < dist[w]: - raise ValueError('Contradictory paths found:', - 'negative weights?') - elif w not in seen or vw_dist < seen[w]: - seen[w] = vw_dist - push(fringe, (vw_dist, next(c), w)) - pred[w] = [v] - elif vw_dist == seen[w]: - pred[w].append(v) - return (pred, dist) + return _dijkstra(G, source, get_weight, pred=pred, cutoff=cutoff) def all_pairs_dijkstra_path_length(G, cutoff=None, weight='weight'): @@ -460,11 +458,9 @@ def all_pairs_dijkstra_path_length(G, cutoff=None, weight='weight'): The dictionary returned only has keys for reachable node pairs. """ - paths = {} - for n in G: - paths[n] = single_source_dijkstra_path_length(G, n, cutoff=cutoff, - weight=weight) - return paths + length = single_source_dijkstra_path_length + # TODO This can be trivially parallelized. + return {n: length(G, n, cutoff=cutoff, weight=weight) for n in G} def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'): @@ -502,11 +498,9 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'): floyd_warshall() """ - paths = {} - for n in G: - paths[n] = single_source_dijkstra_path(G, n, cutoff=cutoff, - weight=weight) - return paths + path = single_source_dijkstra_path + # TODO This can be trivially parallelized. + return {n: path(G, n, cutoff=cutoff, weight=weight) for n in G} def bellman_ford(G, source, weight='weight'): @@ -584,6 +578,41 @@ def bellman_ford(G, source, weight='weight'): if len(G) == 1: return pred, dist + return _bellman_ford_relaxation(G, pred, dist, [source], weight) + + +def _bellman_ford_relaxation(G, pred, dist, source, weight): + """Relaxation loop for Bellman–Ford algorithm + + Parameters + ---------- + G : NetworkX graph + + pred: dict + Keyed by node to predecessor in the path + + dist: dict + Keyed by node to the distance from the source + + source: list + List of source nodes + + weight: string + Edge data key corresponding to the edge weight + + Returns + ------- + Returns two dictionaries keyed by node to predecessor in the + path and to the distance from the source respectively. + + Raises + ------ + NetworkXUnbounded + If the (di)graph contains a negative cost (di)cycle, the + algorithm raises an exception to indicate the presence of the + negative cost (di)cycle. Note: any negative weight edge in an + undirected graph is a negative cost cycle + """ if G.is_multigraph(): def get_weight(edge_dict): return min(eattr.get(weight, 1) for eattr in edge_dict.values()) @@ -591,18 +620,13 @@ def bellman_ford(G, source, weight='weight'): def get_weight(edge_dict): return edge_dict.get(weight, 1) - if G.is_directed(): - G_succ = G.succ - else: - G_succ = G.adj - + G_succ = G.succ if G.is_directed() else G.adj inf = float('inf') n = len(G) count = {} - q = deque([source]) - in_q = set([source]) - + q = deque(source) + in_q = set(source) while q: u = q.popleft() in_q.remove(u) @@ -988,7 +1012,7 @@ def bidirectional_dijkstra(G, source, target, weight='weight'): raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) -def johnson(G, weight='weight', new_weight=None): +def johnson(G, weight='weight'): """Compute shortest paths between all nodes in a weighted graph using Johnson's algorithm. @@ -999,9 +1023,6 @@ def johnson(G, weight='weight', new_weight=None): weight: string, optional (default='weight') Edge data key corresponding to the edge weight. - new_weight: string, optional (default=None) - Edge data key corresponding to the new edge weight after graph transformation. - Returns ------- distance : dictionary @@ -1044,26 +1065,20 @@ def johnson(G, weight='weight', new_weight=None): if not nx.is_weighted(G, weight=weight): raise nx.NetworkXError('Graph is not weighted.') - new_node = nx.utils.generate_unique_node() - G.add_weighted_edges_from((new_node, node, 0) for node in G.nodes()) + dist = {v: 0 for v in G} + pred = {v: None for v in G} # Calculate distance of shortest paths - dist = nx.bellman_ford(G, source=new_node, weight=weight)[1] - - delete = False - if new_weight is None: - delete = True - new_weight = uuid.uuid1() - - for u, v, w in G.edges(data=True): - w[new_weight] = w[weight] + dist[u] - dist[v] + dist_bellman = _bellman_ford_relaxation(G, pred, dist, G.nodes(), + weight)[1] - G.remove_node(new_node) - all_pairs_path = nx.all_pairs_dijkstra_path(G, weight=new_weight) - - if delete: - for u, v, w in G.edges(data=True): - if new_weight in w: - w.pop(new_weight) + if G.is_multigraph(): + get_weight = lambda u, v, data: ( + min(eattr.get(weight, 1) for eattr in data.values()) + + dist_bellman[u] - dist_bellman[v]) + else: + get_weight = lambda u, v, data: (data.get(weight, 1) + + dist_bellman[u] - dist_bellman[v]) - return all_pairs_path + all_pairs = {v: _dijkstra(G, v, get_weight, paths={v: [v]})[1] for v in G} + return all_pairs diff --git a/networkx/algorithms/traversal/tests/test_bfs.py b/networkx/algorithms/traversal/tests/test_bfs.py index bae2fac6..586d6e80 100644 --- a/networkx/algorithms/traversal/tests/test_bfs.py +++ b/networkx/algorithms/traversal/tests/test_bfs.py @@ -2,35 +2,42 @@ from nose.tools import * import networkx as nx + class TestBFS: def setUp(self): # simple graph - G=nx.Graph() - G.add_edges_from([(0,1),(1,2),(1,3),(2,4),(3,4)]) - self.G=G + G = nx.Graph() + G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)]) + self.G = G def test_successor(self): - assert_equal(nx.bfs_successors(self.G,source=0), - {0: [1], 1: [2,3], 2:[4]}) + assert_equal(nx.bfs_successors(self.G, source=0), + {0: [1], 1: [2, 3], 2: [4]}) def test_predecessor(self): - assert_equal(nx.bfs_predecessors(self.G,source=0), + assert_equal(nx.bfs_predecessors(self.G, source=0), {1: 0, 2: 1, 3: 1, 4: 2}) def test_bfs_tree(self): - T=nx.bfs_tree(self.G,source=0) - assert_equal(sorted(T.nodes()),sorted(self.G.nodes())) - assert_equal(sorted(T.edges()),[(0, 1), (1, 2), (1, 3), (2, 4)]) + T = nx.bfs_tree(self.G, source=0) + assert_equal(sorted(T.nodes()), sorted(self.G.nodes())) + assert_equal(sorted(T.edges()), [(0, 1), (1, 2), (1, 3), (2, 4)]) def test_bfs_edges(self): - edges=nx.bfs_edges(self.G,source=0) - assert_equal(list(edges),[(0, 1), (1, 2), (1, 3), (2, 4)]) + edges = nx.bfs_edges(self.G, source=0) + assert_equal(list(edges), [(0, 1), (1, 2), (1, 3), (2, 4)]) + + def test_bfs_edges_reverse(self): + D = nx.DiGraph() + D.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)]) + edges = nx.bfs_edges(D, source=4, reverse=True) + assert_equal(list(edges), [(4, 2), (4, 3), (2, 1), (1, 0)]) def test_bfs_tree_isolates(self): G = nx.Graph() G.add_node(1) G.add_node(2) - T=nx.bfs_tree(G,source=1) - assert_equal(sorted(T.nodes()),[1]) - assert_equal(sorted(T.edges()),[]) + T = nx.bfs_tree(G, source=1) + assert_equal(sorted(T.nodes()), [1]) + assert_equal(sorted(T.edges()), []) diff --git a/networkx/generators/random_graphs.py b/networkx/generators/random_graphs.py index fa9220f4..deeeb9ac 100644 --- a/networkx/generators/random_graphs.py +++ b/networkx/generators/random_graphs.py @@ -45,7 +45,8 @@ __all__ = ['fast_gnp_random_graph', def fast_gnp_random_graph(n, p, seed=None, directed=False): - """Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph). + """Returns a `G_{n,p}` random graph, also known as an Erdős-Rényi graph or + a binomial graph. Parameters ---------- @@ -56,18 +57,17 @@ def fast_gnp_random_graph(n, p, seed=None, directed=False): seed : int, optional Seed for random number generator (default=None). directed : bool, optional (default=False) - If True return a directed graph + If ``True``, this function returns a directed graph. Notes ----- - The G_{n,p} graph algorithm chooses each of the [n(n-1)]/2 - (undirected) or n(n-1) (directed) possible edges with probability p. - - This algorithm is O(n+m) where m is the expected number of - edges m=p*n*(n-1)/2. + The `G_{n,p}` graph algorithm chooses each of the `[n (n - 1)] / 2` + (undirected) or `n (n - 1)` (directed) possible edges with probability `p`. - It should be faster than gnp_random_graph when p is small and - the expected number of edges is small (sparse graph). + This algorithm runs in `O(n + m)` time, where `m` is the expected number of + edges, which equals `p n (n - 1) / 2`. This should be faster than + :func:`gnp_random_graph` when `p` is small and the expected number of edges + is small (that is, the graph is sparse). See Also -------- @@ -122,11 +122,14 @@ def fast_gnp_random_graph(n, p, seed=None, directed=False): def gnp_random_graph(n, p, seed=None, directed=False): - """Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph). + """Returns a `G_{n,p}` random graph, also known as an Erdős-Rényi graph or + a binomial graph. - Chooses each of the possible edges with probability p. + The `G_{n,p}` model chooses each of the possible edges with probability + ``p``. - This is also called binomial_graph and erdos_renyi_graph. + The functions :func:`binomial_graph` and :func:`erdos_renyi_graph` are + aliases of this function. Parameters ---------- @@ -137,7 +140,7 @@ def gnp_random_graph(n, p, seed=None, directed=False): seed : int, optional Seed for random number generator (default=None). directed : bool, optional (default=False) - If True return a directed graph + If ``True``, this function returns a directed graph. See Also -------- @@ -145,8 +148,8 @@ def gnp_random_graph(n, p, seed=None, directed=False): Notes ----- - This is an O(n^2) algorithm. For sparse graphs (small p) see - fast_gnp_random_graph for a faster algorithm. + This algorithm runs in `O(n^2)` time. For sparse graphs (that is, for + small values of `p`), :func:`fast_gnp_random_graph` is a faster algorithm. References ---------- @@ -183,11 +186,13 @@ binomial_graph=gnp_random_graph erdos_renyi_graph=gnp_random_graph def dense_gnm_random_graph(n, m, seed=None): - """Return the random graph G_{n,m}. + """Returns a `G_{n,m}` random graph. + + In the `G_{n,m}` model, a graph is chosen uniformly at random from the set + of all graphs with `n` nodes and `m` edges. - Gives a graph picked randomly out of the set of all graphs - with n nodes and m edges. - This algorithm should be faster than gnm_random_graph for dense graphs. + This algorithm should be faster than :func:`gnm_random_graph` for dense + graphs. Parameters ---------- @@ -242,10 +247,13 @@ def dense_gnm_random_graph(n, m, seed=None): v=u+1 def gnm_random_graph(n, m, seed=None, directed=False): - """Return the random graph G_{n,m}. + """Returns a `G_{n,m}` random graph. - Produces a graph picked randomly out of the set of all graphs - with n nodes and m edges. + In the `G_{n,m}` model, a graph is chosen uniformly at random from the set + of all graphs with `n` nodes and `m` edges. + + This algorithm should be faster than :func:`dense_gnm_random_graph` for + sparse graphs. Parameters ---------- @@ -257,6 +265,11 @@ def gnm_random_graph(n, m, seed=None, directed=False): Seed for random number generator (default=None). directed : bool, optional (default=False) If True return a directed graph + + See also + -------- + dense_gnm_random_graph + """ if directed: G=nx.DiGraph() @@ -291,27 +304,29 @@ def gnm_random_graph(n, m, seed=None, directed=False): def newman_watts_strogatz_graph(n, k, p, seed=None): - """Return a Newman-Watts-Strogatz small world graph. + """Return a Newman–Watts–Strogatz small-world graph. Parameters ---------- n : int - The number of nodes + The number of nodes. k : int - Each node is connected to k nearest neighbors in ring topology + Each node is joined with its ``k`` nearest neighbors in a ring + topology. p : float - The probability of adding a new edge for each edge + The probability of adding a new edge for each edge. seed : int, optional - seed for random number generator (default=None) + The seed for the random number generator (the default is ``None``). Notes ----- - First create a ring over n nodes. Then each node in the ring is - connected with its k nearest neighbors (k-1 neighbors if k is odd). - Then shortcuts are created by adding new edges as follows: - for each edge u-v in the underlying "n-ring with k nearest neighbors" - with probability p add a new edge u-w with randomly-chosen existing - node w. In contrast with watts_strogatz_graph(), no edges are removed. + First create a ring over ``n`` nodes. Then each node in the ring is + connected with its ``k`` nearest neighbors (or ``k - 1`` neighbors if ``k`` + is odd). Then shortcuts are created by adding new edges as follows: for + each edge ``(u, v)`` in the underlying "``n``-ring with ``k`` nearest + neighbors" with probability ``p`` add a new edge ``(u, w)`` with + randomly-chosen existing node ``w``. In contrast with + :func:`watts_strogatz_graph`, no edges are removed. See Also -------- @@ -355,15 +370,15 @@ def newman_watts_strogatz_graph(n, k, p, seed=None): def watts_strogatz_graph(n, k, p, seed=None): - """Return a Watts-Strogatz small-world graph. - + """Return a Watts–Strogatz small-world graph. Parameters ---------- n : int The number of nodes k : int - Each node is connected to k nearest neighbors in ring topology + Each node is joined with its ``k`` nearest neighbors in a ring + topology. p : float The probability of rewiring each edge seed : int, optional @@ -376,16 +391,16 @@ def watts_strogatz_graph(n, k, p, seed=None): Notes ----- - First create a ring over n nodes. Then each node in the ring is - connected with its k nearest neighbors (k-1 neighbors if k is odd). - Then shortcuts are created by replacing some edges as follows: - for each edge u-v in the underlying "n-ring with k nearest neighbors" - with probability p replace it with a new edge u-w with uniformly - random choice of existing node w. + First create a ring over ``n`` nodes. Then each node in the ring is joined + to its ``k`` nearest neighbors (or ``k - 1`` neighbors if ``k`` is odd). + Then shortcuts are created by replacing some edges as follows: for each + edge ``(u, v)`` in the underlying "``n``-ring with ``k`` nearest neighbors" + with probability ``p`` replace it with a new edge ``(u, w)`` with uniformly + random choice of existing node ``w``. - In contrast with newman_watts_strogatz_graph(), the random - rewiring does not increase the number of edges. The rewired graph - is not guaranteed to be connected as in connected_watts_strogatz_graph(). + In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring + does not increase the number of edges. The rewired graph is not guaranteed + to be connected as in :func:`connected_watts_strogatz_graph`. References ---------- @@ -425,18 +440,19 @@ def watts_strogatz_graph(n, k, p, seed=None): return G def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None): - """Return a connected Watts-Strogatz small-world graph. + """Returns a connected Watts–Strogatz small-world graph. - Attempt to generate a connected realization by repeated - generation of Watts-Strogatz small-world graphs. - An exception is raised if the maximum number of tries is exceeded. + Attempts to generate a connected graph by repeated generation of + Watts–Strogatz small-world graphs. An exception is raised if the maximum + number of tries is exceeded. Parameters ---------- n : int The number of nodes k : int - Each node is connected to k nearest neighbors in ring topology + Each node is joined with its ``k`` nearest neighbors in a ring + topology. p : float The probability of rewiring each edge tries : int @@ -461,26 +477,32 @@ def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None): def random_regular_graph(d, n, seed=None): - """Return a random regular graph of n nodes each with degree d. + """Returns a random ``d``-regular graph on ``n`` nodes. - The resulting graph G has no self-loops or parallel edges. + The resulting graph has no self-loops or parallel edges. Parameters ---------- d : int - Degree + The degree of each node. n : integer - Number of nodes. The value of n*d must be even. + The number of nodes. The value of ``n * d`` must be even. seed : hashable object The seed for random number generator. Notes ----- - The nodes are numbered form 0 to n-1. + The nodes are numbered from ``0`` to ``n - 1``. Kim and Vu's paper [2]_ shows that this algorithm samples in an asymptotically uniform way from the space of random graphs when - d = O(n**(1/3-epsilon)). + `d = O(n^{1 / 3 - \epsilon})`. + + Raises + ------ + + NetworkXError + If ``n * d`` is odd or ``d`` is greater than or equal to ``n``. References ---------- @@ -578,11 +600,11 @@ def _random_subset(seq,m): return targets def barabasi_albert_graph(n, m, seed=None): - """Return random graph using Barabási-Albert preferential attachment model. + """Returns a random graph according to the Barabási–Albert preferential + attachment model. - A graph of n nodes is grown by attaching new nodes each with m - edges that are preferentially attached to existing nodes with high - degree. + A graph of ``n`` nodes is grown by attaching new nodes each with ``m`` + edges that are preferentially attached to existing nodes with high degree. Parameters ---------- @@ -597,9 +619,10 @@ def barabasi_albert_graph(n, m, seed=None): ------- G : Graph - Notes - ----- - The initialization is a graph with with m nodes and no edges. + Raises + ------ + NetworkXError + If ``m`` does not satisfy ``1 <= m < n``. References ---------- @@ -608,8 +631,8 @@ def barabasi_albert_graph(n, m, seed=None): """ if m < 1 or m >=n: - raise nx.NetworkXError(\ - "Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n)) + raise nx.NetworkXError("Barabási–Albert network must have m >= 1" + " and m < n, m = %d, n = %d" % (m, n)) if seed is not None: random.seed(seed) @@ -652,21 +675,27 @@ def powerlaw_cluster_graph(n, m, p, seed=None): Notes ----- - The average clustering has a hard time getting above - a certain cutoff that depends on m. This cutoff is often quite low. - Note that the transitivity (fraction of triangles to possible - triangles) seems to go down with network size. + The average clustering has a hard time getting above a certain + cutoff that depends on ``m``. This cutoff is often quite low. The + transitivity (fraction of triangles to possible triangles) seems to + decrease with network size. - It is essentially the Barabási-Albert (B-A) growth model with an + It is essentially the Barabási–Albert (BA) growth model with an extra step that each random edge is followed by a chance of making an edge to one of its neighbors too (and thus a triangle). - This algorithm improves on B-A in the sense that it enables a + This algorithm improves on BA in the sense that it enables a higher average clustering to be attained if desired. It seems possible to have a disconnected graph with this algorithm - since the initial m nodes may not be all linked to a new node - on the first iteration like the B-A model. + since the initial ``m`` nodes may not be all linked to a new node + on the first iteration like the BA model. + + Raises + ------ + NetworkXError + If ``m`` does not satisfy ``1 <= m <= n`` or ``p`` does not + satisfy ``0 <= p <= 1``. References ---------- @@ -719,10 +748,11 @@ def powerlaw_cluster_graph(n, m, p, seed=None): return G def duplication_divergence_graph(n, p, seed=None): - """Return a undirected graph using the Duplication-Divergence model + """Returns an undirected graph using the duplication-divergence model. - A graph of n nodes is created by duplicating the initial nodes and - retain edges of the original nodes with a retention probability p. + A graph of ``n`` nodes is created by duplicating the initial nodes + and retaining edges incident to the original nodes with a retention + probability ``p``. Parameters ---------- @@ -786,24 +816,22 @@ def duplication_divergence_graph(n, p, seed=None): return G def random_lobster(n, p1, p2, seed=None): - """Return a random lobster. + """Returns a random lobster graph. A lobster is a tree that reduces to a caterpillar when pruning all - leaf nodes. - - A caterpillar is a tree that reduces to a path graph when pruning - all leaf nodes (p2=0). - - Parameters - ---------- - n : int - The expected number of nodes in the backbone - p1 : float - Probability of adding an edge to the backbone - p2 : float - Probability of adding an edge one level beyond backbone - seed : int, optional - Seed for random number generator (default=None). + leaf nodes. A caterpillar is a tree that reduces to a path graph + when pruning all leaf nodes; setting ``p2`` to zero produces a caterillar. + + Parameters + ---------- + n : int + The expected number of nodes in the backbone + p1 : float + Probability of adding an edge to the backbone + p2 : float + Probability of adding an edge one level beyond backbone + seed : int, optional + Seed for random number generator (default=None). """ # a necessary ingredient in any self-respecting graph library if seed is not None: @@ -823,26 +851,25 @@ def random_lobster(n, p1, p2, seed=None): return L # voila, un lobster! def random_shell_graph(constructor, seed=None): - """Return a random shell graph for the constructor given. + """Returns a random shell graph for the constructor given. Parameters ---------- - constructor: a list of three-tuples - (n,m,d) for each shell starting at the center shell. - n : int - The number of nodes in the shell - m : int - The number or edges in the shell - d : float - The ratio of inter-shell (next) edges to intra-shell edges. - d=0 means no intra shell edges, d=1 for the last shell + constructor : list of three-tuples + Represents the parameters for a shell, starting at the center + shell. Each element of the list must be of the form ``(n, m, + d)``, where ``n`` is the number of nodes in the shell, ``m`` is + the number of edges in the shell, and ``d`` is the ratio of + inter-shell (next) edges to intra-shell edges. If ``d`` is zero, + there will be no intra-shell edges, and if ``d`` is one there + will be all possible intra-shell edges. seed : int, optional Seed for random number generator (default=None). Examples -------- - >>> constructor=[(10,20,0.8),(20,40,0.8)] - >>> G=nx.random_shell_graph(constructor) + >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)] + >>> G = nx.random_shell_graph(constructor) """ G=empty_graph(0) @@ -883,24 +910,31 @@ def random_shell_graph(constructor, seed=None): def random_powerlaw_tree(n, gamma=3, seed=None, tries=100): - """Return a tree with a powerlaw degree distribution. + """Returns a tree with a power law degree distribution. Parameters ---------- - n : int, - The number of nodes + n : int + The number of nodes. gamma : float - Exponent of the power-law + Exponent of the power law. seed : int, optional Seed for random number generator (default=None). tries : int - Number of attempts to adjust sequence to make a tree + Number of attempts to adjust the sequence to make it a tree. + + Raises + ------ + NetworkXError + If no valid sequence is found within the maximum number of + attempts. Notes ----- - A trial powerlaw degree sequence is chosen and then elements are - swapped with new elements from a powerlaw distribution until - the sequence makes a tree (#edges=#nodes-1). + A trial power law degree sequence is chosen and then elements are + swapped with new elements from a powerlaw distribution until the + sequence makes a tree (by checking, for example, that the number of + edges is one smaller than the number of nodes). """ from networkx.generators.degree_seq import degree_sequence_tree @@ -918,25 +952,31 @@ def random_powerlaw_tree(n, gamma=3, seed=None, tries=100): def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100): - """ Return a degree sequence for a tree with a powerlaw distribution. + """Returns a degree sequence for a tree with a power law distribution. Parameters ---------- n : int, - The number of nodes + The number of nodes. gamma : float - Exponent of the power-law + Exponent of the power law. seed : int, optional Seed for random number generator (default=None). tries : int - Number of attempts to adjust sequence to make a tree + Number of attempts to adjust the sequence to make it a tree. + + Raises + ------ + NetworkXError + If no valid sequence is found within the maximum number of + attempts. Notes ----- - A trial powerlaw degree sequence is chosen and then elements are - swapped with new elements from a powerlaw distribution until - the sequence makes a tree (#edges=#nodes-1). - + A trial power law degree sequence is chosen and then elements are + swapped with new elements from a power law distribution until + the sequence makes a tree (by checking, for example, that the number of + edges is one smaller than the number of nodes). """ if seed is not None: diff --git a/networkx/readwrite/gml.py b/networkx/readwrite/gml.py index e15ec4a6..95a86cd9 100644 --- a/networkx/readwrite/gml.py +++ b/networkx/readwrite/gml.py @@ -683,9 +683,9 @@ def write_gml(G, path, stringizer=None): .bz2 will be compressed. stringizer : callable, optional - A stringizer which converts non-int/float/dict values into strings. If - it cannot convert a value into a string, it should raise a - ``ValueError`` raised to indicate that. Default value: ``None``. + A stringizer which converts non-int/non-float/non-dict values into + strings. If it cannot convert a value into a string, it should raise a + ``ValueError`` to indicate that. Default value: ``None``. Raises ------ diff --git a/networkx/readwrite/nx_shp.py b/networkx/readwrite/nx_shp.py index 6bb04dbb..bb60fe0d 100644 --- a/networkx/readwrite/nx_shp.py +++ b/networkx/readwrite/nx_shp.py @@ -23,7 +23,7 @@ __author__ = """Ben Reilly (benwreilly@gmail.com)""" __all__ = ['read_shp', 'write_shp'] -def read_shp(path): +def read_shp(path, simplify=True): """Generates a networkx.DiGraph from shapefiles. Point geometries are translated into nodes, lines into edges. Coordinate tuples are used as keys. Attributes are preserved, line geometries are simplified into start @@ -38,6 +38,12 @@ def read_shp(path): path : file or string File, directory, or filename to read. + simplify: bool + If ``True``, simplify line geometries to start and end coordinates. + If ``False``, and line feature geometry has multiple segments, the + non-geometric attributes for that feature will be repeated for each + edge comprising that feature. + Returns ------- G : NetworkX graph @@ -70,11 +76,25 @@ def read_shp(path): if g.GetGeometryType() == 1: # point net.add_node((g.GetPoint_2D(0)), attributes) if g.GetGeometryType() == 2: # linestring - attributes["Wkb"] = g.ExportToWkb() - attributes["Wkt"] = g.ExportToWkt() - attributes["Json"] = g.ExportToJson() last = g.GetPointCount() - 1 - net.add_edge(g.GetPoint_2D(0), g.GetPoint_2D(last), attributes) + if simplify: + attributes["Wkb"] = g.ExportToWkb() + attributes["Wkt"] = g.ExportToWkt() + attributes["Json"] = g.ExportToJson() + net.add_edge(g.GetPoint_2D(0), g.GetPoint_2D(last), attributes) + else: + # separate out each segment as individual edge + for i in range(last): + pt1 = g.GetPoint_2D(i) + pt2 = g.GetPoint_2D(i + 1) + segment = ogr.Geometry(ogr.wkbLineString) + segment.AddPoint_2D(pt1[0], pt1[1]) + segment.AddPoint_2D(pt2[0], pt2[1]) + attributes["Wkb"] = segment.ExportToWkb() + attributes["Wkt"] = segment.ExportToWkt() + attributes["Json"] = segment.ExportToJson() + net.add_edge(pt1, pt2, attributes) + return net diff --git a/networkx/readwrite/tests/test_shp.py b/networkx/readwrite/tests/test_shp.py index b349bee0..5c02e724 100644 --- a/networkx/readwrite/tests/test_shp.py +++ b/networkx/readwrite/tests/test_shp.py @@ -42,11 +42,17 @@ class TestShp(object): shp = drv.CreateDataSource(shppath) lyr = createlayer(shp) - self.names = ['a', 'b', 'c'] # edgenames - self.paths = ( [(1.0, 1.0), (2.0, 2.0)], - [(2.0, 2.0), (3.0, 3.0)], - [(0.9, 0.9), (4.0, 2.0)] - ) + self.names = ['a', 'b', 'c', 'c'] # edgenames + self.paths = ([(1.0, 1.0), (2.0, 2.0)], + [(2.0, 2.0), (3.0, 3.0)], + [(0.9, 0.9), (4.0, 0.9), (4.0, 2.0)]) + + self.simplified_names = ['a', 'b', 'c'] # edgenames + self.simplified_paths = ([(1.0, 1.0), (2.0, 2.0)], + [(2.0, 2.0), (3.0, 3.0)], + [(0.9, 0.9), (4.0, 2.0)]) + + for path, name in zip(self.paths, self.names): feat = ogr.Feature(lyr.GetLayerDefn()) g = ogr.Geometry(ogr.wkbLineString) @@ -60,14 +66,25 @@ class TestShp(object): self.drv = drv def testload(self): - expected = nx.DiGraph() - for p in self.paths: - expected.add_path(p) + + def compare_graph_paths_names(g, paths, names): + expected = nx.DiGraph() + for p in paths: + expected.add_path(p) + assert_equal(sorted(expected.node), sorted(g.node)) + assert_equal(sorted(expected.edges()), sorted(g.edges())) + g_names = [g.get_edge_data(s, e)['Name'] for s, e in g.edges()] + assert_equal(names, sorted(g_names)) + + # simplified G = nx.read_shp(self.shppath) - assert_equal(sorted(expected.node), sorted(G.node)) - assert_equal(sorted(expected.edges()), sorted(G.edges())) - names = [G.get_edge_data(s, e)['Name'] for s, e in G.edges()] - assert_equal(self.names, sorted(names)) + compare_graph_paths_names(G, self.simplified_paths, \ + self.simplified_names) + + # unsimplified + G = nx.read_shp(self.shppath, simplify=False) + compare_graph_paths_names(G, self.paths, self.names) + def checkgeom(self, lyr, expected): feature = lyr.GetNextFeature() @@ -78,35 +95,61 @@ class TestShp(object): assert_equal(sorted(expected), sorted(actualwkt)) def test_geometryexport(self): + expectedpoints_simple = ( + "POINT (1 1)", + "POINT (2 2)", + "POINT (3 3)", + "POINT (0.9 0.9)", + "POINT (4 2)" + ) + expectedlines_simple = ( + "LINESTRING (1 1,2 2)", + "LINESTRING (2 2,3 3)", + "LINESTRING (0.9 0.9,4.0 0.9,4 2)" + ) expectedpoints = ( "POINT (1 1)", "POINT (2 2)", "POINT (3 3)", "POINT (0.9 0.9)", + "POINT (4.0 0.9)", "POINT (4 2)" ) expectedlines = ( "LINESTRING (1 1,2 2)", "LINESTRING (2 2,3 3)", - "LINESTRING (0.9 0.9,4 2)" + "LINESTRING (0.9 0.9,4.0 0.9)", + "LINESTRING (4.0 0.9,4 2)" ) + + tpath = os.path.join(tempfile.gettempdir(), 'shpdir') G = nx.read_shp(self.shppath) nx.write_shp(G, tpath) shpdir = ogr.Open(tpath) + self.checkgeom(shpdir.GetLayerByName("nodes"), expectedpoints_simple) + self.checkgeom(shpdir.GetLayerByName("edges"), expectedlines_simple) + + # Test unsimplified + # Nodes should have additional point, + # edges should be 'flattened' + G = nx.read_shp(self.shppath, simplify=False) + nx.write_shp(G, tpath) + shpdir = ogr.Open(tpath) self.checkgeom(shpdir.GetLayerByName("nodes"), expectedpoints) self.checkgeom(shpdir.GetLayerByName("edges"), expectedlines) + def test_attributeexport(self): def testattributes(lyr, graph): feature = lyr.GetNextFeature() while feature: coords = [] ref = feature.GetGeometryRef() - for i in range(ref.GetPointCount()): - coords.append(ref.GetPoint_2D(i)) + last = ref.GetPointCount() - 1 + edge_nodes = (ref.GetPoint_2D(0), ref.GetPoint_2D(last)) name = feature.GetFieldAsString('Name') - assert_equal(graph.get_edge_data(*coords)['Name'], name) + assert_equal(graph.get_edge_data(*edge_nodes)['Name'], name) feature = lyr.GetNextFeature() tpath = os.path.join(tempfile.gettempdir(), 'shpdir') diff --git a/networkx/relabel.py b/networkx/relabel.py index ee0334e6..d00ba3a7 100644 --- a/networkx/relabel.py +++ b/networkx/relabel.py @@ -107,6 +107,8 @@ def _relabel_inplace(G, mapping): new = mapping[old] except KeyError: continue + if new == old: + continue try: G.add_node(new, attr_dict=G.node[old]) except KeyError: diff --git a/networkx/tests/test_relabel.py b/networkx/tests/test_relabel.py index 546571dd..87242a1b 100644 --- a/networkx/tests/test_relabel.py +++ b/networkx/tests/test_relabel.py @@ -137,6 +137,13 @@ class TestRelabel(): assert_equal(sorted(G.edges()), [('aardvark', 'bear'), ('aardvark', 'bear')]) + def test_relabel_isolated_nodes_to_same(self): + G=Graph() + G.add_nodes_from(range(4)) + mapping={1:1} + H=relabel_nodes(G, mapping, copy=False) + assert_equal(sorted(H.nodes()), list(range(4))) + @raises(KeyError) def test_relabel_nodes_missing(self): G=Graph([('A','B'),('A','C'),('B','C'),('C','D')]) diff --git a/networkx/utils/rcm.py b/networkx/utils/rcm.py index feedaa98..14f486fa 100644 --- a/networkx/utils/rcm.py +++ b/networkx/utils/rcm.py @@ -44,8 +44,7 @@ def cuthill_mckee_ordering(G, heuristic=None): Smallest degree node as heuristic function: >>> def smallest_degree(G): - ... node, deg = min(G.degree().items(), key=lambda x: x[1]) - ... return node + ... return min(G, key=G.degree) >>> rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree)) @@ -104,8 +103,7 @@ def reverse_cuthill_mckee_ordering(G, heuristic=None): Smallest degree node as heuristic function: >>> def smallest_degree(G): - ... node, deg = min(G.degree().items(), key=lambda x: x[1]) - ... return node + ... return min(G, key=G.degree) >>> rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree)) |