text: # test_boundary.py - unit tests for the boundary 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.boundary` module."""
  from __future__ import division
  
  from itertools import combinations
  
  from nose.tools import assert_almost_equals
  from nose.tools import assert_equal
  
  import networkx as nx
  from networkx import convert_node_labels_to_integers as cnlti
  
  
  class TestNodeBoundary(object):
      """Unit tests for the :func:`~networkx.node_boundary` function."""
  
      def test_null_graph(self):
          """Tests that the null graph has empty node boundaries."""
          null = nx.null_graph()
          assert_equal(nx.node_boundary(null, []), set())
          assert_equal(nx.node_boundary(null, [], []), set())
          assert_equal(nx.node_boundary(null, [1, 2, 3]), set())
          assert_equal(nx.node_boundary(null, [1, 2, 3], [4, 5, 6]), set())
          assert_equal(nx.node_boundary(null, [1, 2, 3], [3, 4, 5]), set())
  
      def test_path_graph(self):
          P10 = cnlti(nx.path_graph(10), first_label=1)
          assert_equal(nx.node_boundary(P10, []), set())
          assert_equal(nx.node_boundary(P10, [], []), set())
          assert_equal(nx.node_boundary(P10, [1, 2, 3]), {4})
          assert_equal(nx.node_boundary(P10, [4, 5, 6]), {3, 7})
          assert_equal(nx.node_boundary(P10, [3, 4, 5, 6, 7]), {2, 8})
          assert_equal(nx.node_boundary(P10, [8, 9, 10]), {7})
          assert_equal(nx.node_boundary(P10, [4, 5, 6], [9, 10]), set())
  
      def test_complete_graph(self):
          K10 = cnlti(nx.complete_graph(10), first_label=1)
          assert_equal(nx.node_boundary(K10, []), set())
          assert_equal(nx.node_boundary(K10, [], []), set())
          assert_equal(nx.node_boundary(K10, [1, 2, 3]), {4, 5, 6, 7, 8, 9, 10})
          assert_equal(nx.node_boundary(K10, [4, 5, 6]), {1, 2, 3, 7, 8, 9, 10})
          assert_equal(nx.node_boundary(K10, [3, 4, 5, 6, 7]), {1, 2, 8, 9, 10})
          assert_equal(nx.node_boundary(K10, [4, 5, 6], []), set())
          assert_equal(nx.node_boundary(K10, K10), set())
          assert_equal(nx.node_boundary(K10, [1, 2, 3], [3, 4, 5]), {4, 5})
  
      def test_petersen(self):
          """Check boundaries in the petersen graph
  
          cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
  
          """
  
          def cheeger(G, k):
              return min(len(nx.node_boundary(G, nn)) / k
                         for nn in combinations(G, k))
  
          P = nx.petersen_graph()
          assert_almost_equals(cheeger(P, 1), 3.00, places=2)
          assert_almost_equals(cheeger(P, 2), 2.00, places=2)
          assert_almost_equals(cheeger(P, 3), 1.67, places=2)
          assert_almost_equals(cheeger(P, 4), 1.00, places=2)
          assert_almost_equals(cheeger(P, 5), 0.80, places=2)
  
      def test_directed(self):
          """Tests the node boundary of a directed graph."""
          G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
          S = {0, 1}
          boundary = nx.node_boundary(G, S)
          expected = {2}
          assert_equal(boundary, expected)
  
      def test_multigraph(self):
          """Tests the node boundary of a multigraph."""
          G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
          S = {0, 1}
          boundary = nx.node_boundary(G, S)
          expected = {2, 4}
          assert_equal(boundary, expected)
  
      def test_multidigraph(self):
          """Tests the edge boundary of a multdiigraph."""
          edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
          G = nx.MultiDiGraph(edges * 2)
          S = {0, 1}
          boundary = nx.node_boundary(G, S)
          expected = {2}
          assert_equal(boundary, expected)
  
  
  class TestEdgeBoundary(object):
      """Unit tests for the :func:`~networkx.edge_boundary` function."""
  
      def test_null_graph(self):
          null = nx.null_graph()
          assert_equal(list(nx.edge_boundary(null, [])), [])
          assert_equal(list(nx.edge_boundary(null, [], [])), [])
          assert_equal(list(nx.edge_boundary(null, [1, 2, 3])), [])
          assert_equal(list(nx.edge_boundary(null, [1, 2, 3], [4, 5, 6])), [])
          assert_equal(list(nx.edge_boundary(null, [1, 2, 3], [3, 4, 5])), [])
  
      def test_path_graph(self):
          P10 = cnlti(nx.path_graph(10), first_label=1)
          assert_equal(list(nx.edge_boundary(P10, [])), [])
          assert_equal(list(nx.edge_boundary(P10, [], [])), [])
          assert_equal(list(nx.edge_boundary(P10, [1, 2, 3])), [(3, 4)])
          assert_equal(sorted(nx.edge_boundary(P10, [4, 5, 6])),
                       [(4, 3), (6, 7)])
          assert_equal(sorted(nx.edge_boundary(P10, [3, 4, 5, 6, 7])),
                       [(3, 2), (7, 8)])
          assert_equal(list(nx.edge_boundary(P10, [8, 9, 10])), [(8, 7)])
          assert_equal(sorted(nx.edge_boundary(P10, [4, 5, 6], [9, 10])), [])
          assert_equal(list(nx.edge_boundary(P10, [1, 2, 3], [3, 4, 5])),
                       [(2, 3), (3, 4)])
  
      def test_complete_graph(self):
          K10 = cnlti(nx.complete_graph(10), first_label=1)
          ilen = lambda iterable: sum(1 for i in iterable)
          assert_equal(list(nx.edge_boundary(K10, [])), [])
          assert_equal(list(nx.edge_boundary(K10, [], [])), [])
          assert_equal(ilen(nx.edge_boundary(K10, [1, 2, 3])), 21)
          assert_equal(ilen(nx.edge_boundary(K10, [4, 5, 6, 7])), 24)
          assert_equal(ilen(nx.edge_boundary(K10, [3, 4, 5, 6, 7])), 25)
          assert_equal(ilen(nx.edge_boundary(K10, [8, 9, 10])), 21)
          assert_equal(sorted(nx.edge_boundary(K10, [4, 5, 6], [9, 10])),
                       [(4, 9), (4, 10), (5, 9), (5, 10), (6, 9), (6, 10)])
          assert_equal(sorted(nx.edge_boundary(K10, [1, 2, 3], [3, 4, 5])),
                       [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4),
                        (2, 5), (3, 4), (3, 5)])
  
      def test_directed(self):
          """Tests the edge boundary of a directed graph."""
          G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
          S = {0, 1}
          boundary = list(nx.edge_boundary(G, S))
          expected = [(1, 2)]
          assert_equal(boundary, expected)
  
      def test_multigraph(self):
          """Tests the edge boundary of a multigraph."""
          G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
          S = {0, 1}
          boundary = list(nx.edge_boundary(G, S))
          expected = [(0, 4), (0, 4), (1, 2), (1, 2)]
          assert_equal(boundary, expected)
  
      def test_multidigraph(self):
          """Tests the edge boundary of a multdiigraph."""
          edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
          G = nx.MultiDiGraph(edges * 2)
          S = {0, 1}
          boundary = list(nx.edge_boundary(G, S))
          expected = [(1, 2), (1, 2)]
          assert_equal(boundary, expected)
  