diff options
Diffstat (limited to 'networkx')
| -rw-r--r-- | networkx/algorithms/__init__.py | 4 | ||||
| -rw-r--r-- | networkx/algorithms/traversal/breadth_first_search.py | 17 | ||||
| -rw-r--r-- | networkx/algorithms/tree/__init__.py | 4 | ||||
| -rw-r--r-- | networkx/algorithms/tree/coding.py | 402 | ||||
| -rw-r--r-- | networkx/algorithms/tree/operations.py | 110 | ||||
| -rw-r--r-- | networkx/algorithms/tree/tests/test_coding.py | 127 | ||||
| -rw-r--r-- | networkx/algorithms/tree/tests/test_operations.py | 46 | ||||
| -rw-r--r-- | networkx/generators/__init__.py | 1 | ||||
| -rw-r--r-- | networkx/generators/tests/test_tree.py | 18 | ||||
| -rw-r--r-- | networkx/generators/tree.py | 76 |
10 files changed, 800 insertions, 5 deletions
diff --git a/networkx/algorithms/__init__.py b/networkx/algorithms/__init__.py index 2405d624..85cdedb4 100644 --- a/networkx/algorithms/__init__.py +++ b/networkx/algorithms/__init__.py @@ -74,8 +74,10 @@ from networkx.algorithms.flow import (maximum_flow, maximum_flow_value, min_cost_flow_cost, max_flow_min_cost, min_cost_flow, cost_of_flow) from .tree.recognition import * -from .tree.mst import * from .tree.branchings import ( maximum_branching, minimum_branching, maximum_spanning_arborescence, minimum_spanning_arborescence ) +from .tree.coding import * +from .tree.operations import * +from .tree.mst import * diff --git a/networkx/algorithms/traversal/breadth_first_search.py b/networkx/algorithms/traversal/breadth_first_search.py index 6166ce0b..c8be79a9 100644 --- a/networkx/algorithms/traversal/breadth_first_search.py +++ b/networkx/algorithms/traversal/breadth_first_search.py @@ -32,9 +32,20 @@ def bfs_edges(G, source, reverse=False): Examples -------- - >>> G = nx.path_graph(3) - >>> print(list(nx.bfs_edges(G,0))) - [(0, 1), (1, 2)] + To get the edges in a breadth-first search:: + + >>> G = nx.path_graph(3) + >>> list(nx.bfs_edges(G, 0)) + [(0, 1), (1, 2)] + + To get the nodes in a breadth-first search order:: + + >>> G = nx.path_graph(3) + >>> root = 2 + >>> edges = nx.bfs_edges(G, root) + >>> nodes = [root] + [v for u, v in edges] + >>> nodes + [2, 1, 0] Notes ----- diff --git a/networkx/algorithms/tree/__init__.py b/networkx/algorithms/tree/__init__.py index d8ac1b88..0bb8fd44 100644 --- a/networkx/algorithms/tree/__init__.py +++ b/networkx/algorithms/tree/__init__.py @@ -1,3 +1,5 @@ -from .recognition import * from .branchings import * +from .coding import * from .mst import * +from .recognition import * +from .operations import * diff --git a/networkx/algorithms/tree/coding.py b/networkx/algorithms/tree/coding.py new file mode 100644 index 00000000..dfb29175 --- /dev/null +++ b/networkx/algorithms/tree/coding.py @@ -0,0 +1,402 @@ +# -*- encoding: utf-8 -*- +# +# coding.py - functions for encoding and decoding trees as sequences +# +# Copyright 2015, 2016 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Functions for encoding and decoding trees. + +Since a tree is a highly restricted form of graph, it can be represented +concisely in several ways. This module includes functions for encoding +and decoding trees in the form of nested tuples and Prüfer +sequences. The former requires a rooted tree, whereas the latter can be +applied to unrooted trees. Furthermore, there is a bijection from Prüfer +sequences to labeled trees. + +""" +from collections import Counter +from itertools import chain + +import networkx as nx +from networkx.utils import not_implemented_for + +__all__ = ['from_nested_tuple', 'from_prufer_sequence', 'NotATree', + 'to_nested_tuple', 'to_prufer_sequence'] + + +class NotATree(nx.NetworkXException): + """Raised when a function expects a tree (that is, a connected + undirected graph with no cycles) but gets a non-tree graph as input + instead. + + """ + + +@not_implemented_for('directed') +def to_nested_tuple(T, root, canonical_form=False): + """Returns a nested tuple representation of the given tree. + + The nested tuple representation of a tree is defined + recursively. The tree with one node and no edges is represented by + the empty tuple, ``()``. A tree with ``k`` subtrees is represented + by a tuple of length ``k`` in which each element is the nested tuple + representation of a subtree. + + Parameters + ---------- + T : NetworkX graph + An undirected graph object representing a tree. + + root : node + The node in ``T`` to interpret as the root of the tree. + + canonical_form : bool + If ``True``, each tuple is sorted so that the function returns + a canonical form for rooted trees. This means "lighter" subtrees + will appear as nested tuples before "heavier" subtrees. In this + way, each isomorphic rooted tree has the same nested tuple + representation. + + Returns + ------- + tuple + A nested tuple representation of the tree. + + Notes + ----- + This function is *not* the inverse of :func:`from_nested_tuple`; the + only guarantee is that the rooted trees are isomorphic. + + See also + -------- + from_nested_tuple + to_prufer_sequence + + Examples + -------- + The tree need not be a balanced binary tree:: + + >>> T = nx.Graph() + >>> T.add_edges_from([(0, 1), (0, 2), (0, 3)]) + >>> T.add_edges_from([(1, 4), (1, 5)]) + >>> T.add_edges_from([(3, 6), (3, 7)]) + >>> root = 0 + >>> nx.to_nested_tuple(T, root) + (((), ()), (), ((), ())) + + Continuing the above example, if ``canonical_form`` is ``True``, the + nested tuples will be sorted:: + + >>> nx.to_nested_tuple(T, root, canonical_form=True) + ((), ((), ()), ((), ())) + + Even the path graph can be interpreted as a tree:: + + >>> T = nx.path_graph(4) + >>> root = 0 + >>> nx.to_nested_tuple(T, root) + ((((),),),) + + """ + + def _make_tuple(T, root, _parent): + """Recursively compute the nested tuple representation of the + given rooted tree. + + ``_parent`` is the parent node of ``root`` in the supertree in + which ``T`` is a subtree, or ``None`` if ``root`` is the root of + the supertree. This argument is used to determine which + neighbors of ``root`` are children and which is the parent. + + """ + # Get the neighbors of `root` that are not the parent node. We + # are guaranteed that `root` is always in `T` by construction. + children = set(T[root]) - {_parent} + if len(children) == 0: + return () + nested = (_make_tuple(T, v, root) for v in children) + if canonical_form: + nested = sorted(nested) + return tuple(nested) + + # Do some sanity checks on the input. + if not nx.is_tree(T): + raise nx.NotATree('provided graph is not a tree') + if root not in T: + raise nx.NodeNotFound('Graph {} contains no node {}'.format(T, root)) + + return _make_tuple(T, root, None) + + +def from_nested_tuple(sequence, sensible_relabeling=False): + """Returns the rooted tree corresponding to the given nested tuple. + + The nested tuple representation of a tree is defined + recursively. The tree with one node and no edges is represented by + the empty tuple, ``()``. A tree with ``k`` subtrees is represented + by a tuple of length ``k`` in which each element is the nested tuple + representation of a subtree. + + Parameters + ---------- + sequence : tuple + A nested tuple representing a rooted tree. + + sensible_relabeling : bool + Whether to relabel the nodes of the tree so that nodes are + labeled in increasing order according to their breadth-first + search order from the root node. + + Returns + ------- + NetworkX graph + The tree corresponding to the given nested tuple, whose root + node is node 0. If ``sensible_labeling`` is ``True``, nodes will + be labeled in breadth-first search order starting from the root + node. + + Notes + ----- + This function is *not* the inverse of :func:`to_nested_tuple`; the + only guarantee is that the rooted trees are isomorphic. + + See also + -------- + to_nested_tuple + from_prufer_sequence + + Examples + -------- + Sensible relabeling ensures that the nodes are labeled from the root + starting at 0:: + + >>> balanced = (((), ()), ((), ())) + >>> T = nx.from_nested_tuple(balanced, sensible_relabeling=True) + >>> list(T.edges()) + [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] + + """ + + def _make_tree(sequence): + """Recursively creates a tree from the given sequence of nested + tuples. + + This function employs the :func:`~networkx.tree.join` function + to recursively join subtrees into a larger tree. + + """ + # The empty sequence represents the empty tree, which is the + # (unique) graph with a single node. We mark the single node + # with an attribute that indicates that it is the root of the + # graph. + if len(sequence) == 0: + return nx.empty_graph(1) + # For a nonempty sequence, get the subtrees for each child + # sequence and join all the subtrees at their roots. After + # joining the subtrees, the root is node 0. + return nx.tree.join([(_make_tree(child), 0) for child in sequence]) + + # Make the tree and remove the `is_root` node attribute added by the + # helper function. + T = _make_tree(sequence) + if sensible_relabeling: + # Relabel the nodes according to their breadth-first search + # order, starting from the root node (that is, the node 0). + bfs_nodes = chain([0], (v for u, v in nx.bfs_edges(T, 0))) + labels = {v: i for i, v in enumerate(bfs_nodes)} + # We would like to use `copy=False`, but `relabel_nodes` doesn't + # allow a relabel mapping that can't be topologically sorted. + T = nx.relabel_nodes(T, labels) + return T + + +@not_implemented_for('directed') +def to_prufer_sequence(T): + r"""Returns the Prüfer sequence of the given tree. + + A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and + *n* - 1, inclusive. The tree corresponding to a given Prüfer + sequence can be recovered by repeatedly joining a node in the + sequence with a node with the smallest potential degree according to + the sequence. + + Parameters + ---------- + T : NetworkX graph + An undirected graph object representing a tree. + + Returns + ------- + list + The Prüfer sequence of the given tree. + + Raises + ------ + NetworkXPointlessConcept + If the number of nodes in `T` is less than two. + + NotATree + If `T` is not a tree. + + KeyError + If the set of nodes in `T` is not {0, …, *n* - 1}. + + Notes + ----- + There is a bijection from labeled trees to Prüfer sequences. This + function is the inverse of the :func:`from_prufer_sequence` + function. + + Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead + of from 0 to *n* - 1. This function requires nodes to be labeled in + the latter form. You can use :func:`~networkx.relabel_nodes` to + relabel the nodes of your tree to the appropriate format. + + This implementation is from [1]_ and has a running time of + :math:`O(n \log n)`. + + See also + -------- + to_nested_tuple + from_prufer_sequence + + References + ---------- + .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu. + "An optimal algorithm for Prufer codes." + *Journal of Software Engineering and Applications* 2.02 (2009): 111. + <http://dx.doi.org/10.4236/jsea.2009.22016> + + Examples + -------- + There is a bijection between Prüfer sequences and labeled trees, so + this function is the inverse of the :func:`from_prufer_sequence` + function:: + + >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] + >>> tree = nx.Graph(edges) + >>> sequence = nx.to_prufer_sequence(tree) + >>> sequence + [3, 3, 3, 4] + >>> tree2 = nx.from_prufer_sequence(sequence) + >>> list(tree2.edges()) == edges + True + + """ + # Perform some sanity checks on the input. + n = len(T) + if n < 2: + msg = 'Prüfer sequence undefined for trees with fewer than two nodes' + raise nx.NetworkXPointlessConcept(msg) + if not nx.is_tree(T): + raise nx.NotATree('provided graph is not a tree') + if set(T) != set(range(n)): + raise KeyError('tree must have node labels {0, ..., n - 1}') + + degree = dict(T.degree()) + + def parents(u): + return next(v for v in T[u] if degree[v] > 1) + + index = u = min(k for k in range(n) if degree[k] == 1) + result = [] + for i in range(n - 2): + v = parents(u) + result.append(v) + degree[v] -= 1 + if v < index and degree[v] == 1: + u = v + else: + index = u = min(k for k in range(index + 1, n) if degree[k] == 1) + return result + + +def from_prufer_sequence(sequence): + r"""Returns the tree corresponding to the given Prüfer sequence. + + A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and + *n* - 1, inclusive. The tree corresponding to a given Prüfer + sequence can be recovered by repeatedly joining a node in the + sequence with a node with the smallest potential degree according to + the sequence. + + Parameters + ---------- + sequence : list + A Prüfer sequence, which is a list of *n* - 2 integers between + zero and *n* - 1, inclusive. + + Returns + ------- + NetworkX graph + The tree corresponding to the given Prüfer sequence. + + Notes + ----- + There is a bijection from labeled trees to Prüfer sequences. This + function is the inverse of the :func:`from_prufer_sequence` function. + + Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead + of from 0 to *n* - 1. This function requires nodes to be labeled in + the latter form. You can use :func:`networkx.relabel_nodes` to + relabel the nodes of your tree to the appropriate format. + + This implementation is from [1]_ and has a running time of + :math:`O(n \log n)`. + + References + ---------- + .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu. + "An optimal algorithm for Prufer codes." + *Journal of Software Engineering and Applications* 2.02 (2009): 111. + <http://dx.doi.org/10.4236/jsea.2009.22016> + + See also + -------- + from_nested_tuple + to_prufer_sequence + + Examples + -------- + There is a bijection between Prüfer sequences and labeled trees, so + this function is the inverse of the :func:`to_prufer_sequence` + function:: + + >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] + >>> tree = nx.Graph(edges) + >>> sequence = nx.to_prufer_sequence(tree) + >>> sequence + [3, 3, 3, 4] + >>> tree2 = nx.from_prufer_sequence(sequence) + >>> list(tree2.edges()) == edges + True + + """ + n = len(sequence) + 2 + # `degree` stores the remaining degree (plus one) for each node. The + # degree of a node in the decoded tree is one more than the number + # of times it appears in the code. + degree = Counter(chain(sequence, range(n))) + T = nx.empty_graph(n) + # `not_orphaned` is the set of nodes that have a parent in the + # tree. After the loop, there should be exactly two nodes that are + # not in this set. + not_orphaned = set() + index = u = min(k for k in range(n) if degree[k] == 1) + for v in sequence: + T.add_edge(u, v) + not_orphaned.add(u) + degree[v] -= 1 + if v < index and degree[v] == 1: + u = v + else: + index = u = min(k for k in range(index + 1, n) if degree[k] == 1) + # At this point, there must be exactly two orphaned nodes; join them. + orphans = set(T) - not_orphaned + u, v = orphans + T.add_edge(u, v) + return T diff --git a/networkx/algorithms/tree/operations.py b/networkx/algorithms/tree/operations.py new file mode 100644 index 00000000..70db6837 --- /dev/null +++ b/networkx/algorithms/tree/operations.py @@ -0,0 +1,110 @@ +# operations.py - binary operations on trees +# +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Operations on trees.""" +from functools import partial +from itertools import chain + +import networkx as nx +from networkx.utils import accumulate + +__all__ = ['join'] + + +def join(rooted_trees, label_attribute=None): + """Returns a new rooted tree with a root node joined with the roots + of each of the given rooted trees. + + Parameters + ---------- + rooted_trees : list + A list of pairs in which each left element is a NetworkX graph + object representing a tree and each right element is the root + node of that tree. The nodes of these trees will be relabeled to + integers. + + label_attribute : str + If provided, the old node labels will be stored in the new tree + under this node attribute. If not provided, the node attribute + ``'_old'`` will store the original label of the node in the + rooted trees given in the input. + + Returns + ------- + NetworkX graph + The rooted tree whose subtrees are the given rooted trees. The + new root node is labeled 0. Each non-root node has an attribute, + as described under the keyword argument ``label_attribute``, + that indicates the label of the original node in the input tree. + + Notes + ----- + Graph, edge, and node attributes are propagated from the given + rooted trees to the created tree. If there are any overlapping graph + attributes, those from later trees will overwrite those from earlier + trees in the tuple of positional arguments. + + Examples + -------- + Join two full balanced binary trees of height *h* to get a full + balanced binary tree of depth *h* + 1:: + + >>> h = 4 + >>> left = nx.balanced_tree(2, h) + >>> right = nx.balanced_tree(2, h) + >>> joined_tree = nx.join([(left, 0), (right, 0)]) + >>> nx.is_isomorphic(joined_tree, nx.balanced_tree(2, h + 1)) + True + + """ + if len(rooted_trees) == 0: + return nx.empty_graph(1) + + # Unzip the zipped list of (tree, root) pairs. + trees, roots = zip(*rooted_trees) + + # The join of the trees has the same type as the type of the first + # tree. + R = type(trees[0])() + + # Relabel the nodes so that their union is the integers starting at 1. + if label_attribute is None: + label_attribute = '_old' + relabel = partial(nx.convert_node_labels_to_integers, + label_attribute=label_attribute) + lengths = (len(tree) for tree in trees[:-1]) + first_labels = chain([0], accumulate(lengths)) + trees = [relabel(tree, first_label=first_label + 1) + for tree, first_label in zip(trees, first_labels)] + + # Get the relabeled roots. + roots = [next(v for v, d in tree.nodes(data=True) if d.get('_old') == root) + for tree, root in zip(trees, roots)] + + # Remove the old node labels. + for tree in trees: + for v in tree: + tree.node[v].pop('_old') + + # Add all sets of nodes and edges, with data. + nodes = (tree.nodes(data=True) for tree in trees) + edges = (tree.edges(data=True) for tree in trees) + R.add_nodes_from(chain.from_iterable(nodes)) + R.add_edges_from(chain.from_iterable(edges)) + + # Add graph attributes; later attributes take precedent over earlier + # attributes. + for tree in trees: + R.graph.update(tree.graph) + + # Finally, join the subtrees at the root. We know 0 is unused by the + # way we relabeled the subtrees. + R.add_node(0) + R.add_edges_from((0, root) for root in roots) + + return R diff --git a/networkx/algorithms/tree/tests/test_coding.py b/networkx/algorithms/tree/tests/test_coding.py new file mode 100644 index 00000000..4605a9be --- /dev/null +++ b/networkx/algorithms/tree/tests/test_coding.py @@ -0,0 +1,127 @@ +# -*- encoding: utf-8 -*- +# test_coding.py - unit tests for the coding module +# +# Copyright 2015, 2016 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Unit tests for the :mod:`~networkx.algorithms.tree.coding` module.""" +from itertools import product + +from nose.tools import assert_equal +from nose.tools import assert_true +from nose.tools import raises + +import networkx as nx + + +class TestPruferSequence(object): + """Unit tests for the Prüfer sequence encoding and decoding + functions. + + """ + + @raises(nx.NotATree) + def test_nontree(self): + G = nx.cycle_graph(3) + nx.to_prufer_sequence(G) + + @raises(nx.NetworkXPointlessConcept) + def test_null_graph(self): + nx.to_prufer_sequence(nx.null_graph()) + + @raises(nx.NetworkXPointlessConcept) + def test_trivial_graph(self): + nx.to_prufer_sequence(nx.trivial_graph()) + + @raises(KeyError) + def test_bad_integer_labels(self): + T = nx.Graph(nx.utils.pairwise('abc')) + nx.to_prufer_sequence(T) + + def test_encoding(self): + """Tests for encoding a tree as a Prüfer sequence using the + iterative strategy. + + """ + # Example from Wikipedia. + tree = nx.Graph([(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]) + sequence = nx.to_prufer_sequence(tree) + assert_equal(sequence, [3, 3, 3, 4]) + + def test_decoding(self): + """Tests for decoding a tree from a Prüfer sequence.""" + # Example from Wikipedia. + sequence = [3, 3, 3, 4] + tree = nx.from_prufer_sequence(sequence) + assert_equal(list(tree), list(range(6))) + edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] + assert_equal(list(tree.edges()), edges) + + def test_decoding2(self): + # Example from "An Optimal Algorithm for Prufer Codes". + sequence = [2, 4, 0, 1, 3, 3] + tree = nx.from_prufer_sequence(sequence) + assert_equal(list(tree), list(range(8))) + edges = [(0, 1), (0, 4), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)] + assert_equal(list(tree.edges()), edges) + + def test_inverse(self): + """Tests that the encoding and decoding functions are inverses. + + """ + for T in nx.nonisomorphic_trees(4): + T2 = nx.from_prufer_sequence(nx.to_prufer_sequence(T)) + assert_equal(list(T), list(T2)) + assert_equal(list(T.edges()), list(T2.edges())) + + for seq in product(range(4), repeat=2): + seq2 = nx.to_prufer_sequence(nx.from_prufer_sequence(seq)) + assert_equal(list(seq), seq2) + + +class TestNestedTuple(object): + """Unit tests for the nested tuple encoding and decoding functions. + + """ + + @raises(nx.NotATree) + def test_nontree(self): + G = nx.cycle_graph(3) + nx.to_nested_tuple(G, 0) + + @raises(nx.NodeNotFound) + def test_unknown_root(self): + G = nx.path_graph(2) + nx.to_nested_tuple(G, 'bogus') + + def test_encoding(self): + T = nx.full_rary_tree(2, 2 ** 3 - 1) + expected = (((), ()), ((), ())) + actual = nx.to_nested_tuple(T, 0) + assert_equal(expected, actual) + + def test_canonical_form(self): + T = nx.Graph() + T.add_edges_from([(0, 1), (0, 2), (0, 3)]) + T.add_edges_from([(1, 4), (1, 5)]) + T.add_edges_from([(3, 6), (3, 7)]) + root = 0 + actual = nx.to_nested_tuple(T, root, canonical_form=True) + expected = ((), ((), ()), ((), ())) + assert_equal(actual, expected) + + def test_decoding(self): + balanced = (((), ()), ((), ())) + expected = nx.full_rary_tree(2, 2 ** 3 - 1) + actual = nx.from_nested_tuple(balanced) + assert_true(nx.is_isomorphic(expected, actual)) + + def test_sensible_relabeling(self): + balanced = (((), ()), ((), ())) + T = nx.from_nested_tuple(balanced, sensible_relabeling=True) + edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] + assert_equal(list(T), list(range(2 ** 3 - 1))) + assert_equal(list(T.edges()), edges) diff --git a/networkx/algorithms/tree/tests/test_operations.py b/networkx/algorithms/tree/tests/test_operations.py new file mode 100644 index 00000000..fd4e7c23 --- /dev/null +++ b/networkx/algorithms/tree/tests/test_operations.py @@ -0,0 +1,46 @@ +# test_operations.py - unit tests for the operations module +# +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Unit tests for the :mod:`networkx.algorithms.tree.operations` module. + +""" +from nose.tools import assert_equal +from nose.tools import assert_true + +import networkx as nx + + +class TestJoin(object): + """Unit tests for the :func:`networkx.tree.join` function.""" + + def test_empty_sequence(self): + """Tests that joining the empty sequence results in the tree + with one node. + + """ + T = nx.join([]) + assert_equal(len(T), 1) + assert_equal(T.number_of_edges(), 0) + + def test_single(self): + """Tests that joining just one tree yields a tree with one more + node. + + """ + T = nx.empty_graph(1) + actual = nx.join([(T, 0)]) + expected = nx.path_graph(2) + assert_equal(list(expected), list(actual)) + assert_equal(list(expected.edges()), list(actual.edges())) + + def test_basic(self): + """Tests for joining multiple subtrees at a root node.""" + trees = [(nx.full_rary_tree(2, 2 ** 2 - 1), 0) for i in range(2)] + actual = nx.join(trees) + expected = nx.full_rary_tree(2, 2 ** 3 - 1) + assert_true(nx.is_isomorphic(actual, expected)) diff --git a/networkx/generators/__init__.py b/networkx/generators/__init__.py index b3b6dab5..f2ce4c34 100644 --- a/networkx/generators/__init__.py +++ b/networkx/generators/__init__.py @@ -19,4 +19,5 @@ from networkx.generators.random_graphs import * from networkx.generators.small import * from networkx.generators.social import * from networkx.generators.stochastic import * +from networkx.generators.tree import * from networkx.generators.triads import * diff --git a/networkx/generators/tests/test_tree.py b/networkx/generators/tests/test_tree.py new file mode 100644 index 00000000..5233f94b --- /dev/null +++ b/networkx/generators/tests/test_tree.py @@ -0,0 +1,18 @@ +# test_tree.py - unit tests for the networkx.generators.tree module +# +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Unit tests for the :mod:`networkx.generators.tree` module.""" +from nose.tools import assert_true + +import networkx as nx + + +def test_random_tree(): + """Tests that a random tree is in fact a tree.""" + T = nx.random_tree(10, seed=1234) + assert_true(nx.is_tree(T)) diff --git a/networkx/generators/tree.py b/networkx/generators/tree.py new file mode 100644 index 00000000..807d6ddd --- /dev/null +++ b/networkx/generators/tree.py @@ -0,0 +1,76 @@ +# -*- encoding: utf-8 -*- +# tree.py - functions for generating trees +# +# Copyright 2015 NetworkX developers. +# +# This file is part of NetworkX. +# +# NetworkX is distributed under a BSD license; see LICENSE.txt for more +# information. +"""Functions for generating trees.""" +import random + +import networkx as nx + +__all__ = ['random_tree'] + + +def sample_with_replacement(population, k): + """Returns a sample of size ``k`` from the given population. + + ``population`` must be a sequence and ``k`` must be a positive + integer. + + This function returns a list of ``k`` elements chosen uniformly at + random from ``population``. + + """ + return [random.choice(population) for i in range(k)] + + +# From the Wikipedia article on Prüfer sequences: +# +# > Generating uniformly distributed random Prüfer sequences and +# > converting them into the corresponding trees is a straightforward +# > method of generating uniformly distributed random labelled trees. +# +def random_tree(n, seed=None): + """Returns a uniformly random tree on `n` nodes. + + Parameters + ---------- + n : int + A positive integer representing the number of nodes in the tree. + + seed : int + A seed for the random number generator. + + Returns + ------- + NetworkX graph + A tree, given as an undirected graph, whose nodes are numbers in + the set {0, …, *n* - 1}. + + Raises + ------ + NetworkXPointlessConcept + If `n` is zero (because the null graph is not a tree). + + Notes + ----- + The current implementation of this function generates a uniformly + random Prüfer sequence then converts that to a tree via the + :func:`~networkx.from_prufer_sequence` function. Since there is a + bijection between Prüfer sequences of length *n* - 2 and trees on + *n* nodes, the tree is chosen uniformly at random from the set of + all trees on *n* nodes. + + """ + if n == 0: + raise nx.NetworkXPointlessConcept('the null graph is not a tree') + # Cannot create a Prüfer sequence unless `n` is at least two. + if n == 1: + return nx.empty_graph(1) + random.seed(seed) + sequence = sample_with_replacement(range(n), n - 2) + return nx.from_prufer_sequence(sequence) |