text: #! python
  from nose.tools import *
  import networkx
  import networkx as nx
  
  from networkx.algorithms import find_cycle
  from networkx.algorithms import minimum_cycle_basis
  
  FORWARD = nx.algorithms.edgedfs.FORWARD
  REVERSE = nx.algorithms.edgedfs.REVERSE
  
  
  class TestCycles:
      def setUp(self):
          G = networkx.Graph()
          nx.add_cycle(G, [0, 1, 2, 3])
          nx.add_cycle(G, [0, 3, 4, 5])
          nx.add_cycle(G, [0, 1, 6, 7, 8])
          G.add_edge(8, 9)
          self.G = G
  
      def is_cyclic_permutation(self, a, b):
          n = len(a)
          if len(b) != n:
              return False
          l = a + a
          return any(l[i:i + n] == b for i in range(2 * n - n + 1))
  
      def test_cycle_basis(self):
          G = self.G
          cy = networkx.cycle_basis(G, 0)
          sort_cy = sorted(sorted(c) for c in cy)
          assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]])
          cy = networkx.cycle_basis(G, 1)
          sort_cy = sorted(sorted(c) for c in cy)
          assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]])
          cy = networkx.cycle_basis(G, 9)
          sort_cy = sorted(sorted(c) for c in cy)
          assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]])
          # test disconnected graphs
          nx.add_cycle(G, "ABC")
          cy = networkx.cycle_basis(G, 9)
          sort_cy = sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])]
          assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5],
                                 ['A', 'B', 'C']])
  
      @raises(nx.NetworkXNotImplemented)
      def test_cycle_basis(self):
          G = nx.DiGraph()
          cy = networkx.cycle_basis(G, 0)
  
      @raises(nx.NetworkXNotImplemented)
      def test_cycle_basis(self):
          G = nx.MultiGraph()
          cy = networkx.cycle_basis(G, 0)
  
      def test_simple_cycles(self):
          edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
          G = nx.DiGraph(edges)
          cc = sorted(nx.simple_cycles(G))
          ca = [[0], [0, 1, 2], [0, 2], [1, 2], [2]]
          for c in cc:
              assert_true(any(self.is_cyclic_permutation(c, rc) for rc in ca))
  
      @raises(nx.NetworkXNotImplemented)
      def test_simple_cycles_graph(self):
          G = nx.Graph()
          c = sorted(nx.simple_cycles(G))
  
      def test_unsortable(self):
          #  TODO What does this test do?  das 6/2013
          G = nx.DiGraph()
          nx.add_cycle(G, ['a', 1])
          c = list(nx.simple_cycles(G))
  
      def test_simple_cycles_small(self):
          G = nx.DiGraph()
          nx.add_cycle(G, [1, 2, 3])
          c = sorted(nx.simple_cycles(G))
          assert_equal(len(c), 1)
          assert_true(self.is_cyclic_permutation(c[0], [1, 2, 3]))
          nx.add_cycle(G, [10, 20, 30])
          cc = sorted(nx.simple_cycles(G))
          ca = [[1, 2, 3], [10, 20, 30]]
          for c in cc:
              assert_true(any(self.is_cyclic_permutation(c, rc) for rc in ca))
  
      def test_simple_cycles_empty(self):
          G = nx.DiGraph()
          assert_equal(list(nx.simple_cycles(G)), [])
  
      def test_complete_directed_graph(self):
          # see table 2 in Johnson's paper
          ncircuits = [1, 5, 20, 84, 409, 2365, 16064]
          for n, c in zip(range(2, 9), ncircuits):
              G = nx.DiGraph(nx.complete_graph(n))
              assert_equal(len(list(nx.simple_cycles(G))), c)
  
      def worst_case_graph(self, k):
          # see figure 1 in Johnson's paper
          # this graph has exactly 3k simple cycles
          G = nx.DiGraph()
          for n in range(2, k + 2):
              G.add_edge(1, n)
              G.add_edge(n, k + 2)
          G.add_edge(2 * k + 1, 1)
          for n in range(k + 2, 2 * k + 2):
              G.add_edge(n, 2 * k + 2)
              G.add_edge(n, n + 1)
          G.add_edge(2 * k + 3, k + 2)
          for n in range(2 * k + 3, 3 * k + 3):
              G.add_edge(2 * k + 2, n)
              G.add_edge(n, 3 * k + 3)
          G.add_edge(3 * k + 3, 2 * k + 2)
          return G
  
      def test_worst_case_graph(self):
          # see figure 1 in Johnson's paper
          for k in range(3, 10):
              G = self.worst_case_graph(k)
              l = len(list(nx.simple_cycles(G)))
              assert_equal(l, 3 * k)
  
      def test_recursive_simple_and_not(self):
          for k in range(2, 10):
              G = self.worst_case_graph(k)
              cc = sorted(nx.simple_cycles(G))
              rcc = sorted(nx.recursive_simple_cycles(G))
              assert_equal(len(cc), len(rcc))
              for c in cc:
                  assert_true(any(self.is_cyclic_permutation(c, r) for r in rcc))
              for rc in rcc:
                  assert_true(any(self.is_cyclic_permutation(rc, c) for c in cc))
  
      def test_simple_graph_with_reported_bug(self):
          G = nx.DiGraph()
          edges = [(0, 2), (0, 3), (1, 0), (1, 3), (2, 1), (2, 4),
                   (3, 2), (3, 4), (4, 0), (4, 1), (4, 5), (5, 0),
                   (5, 1), (5, 2), (5, 3)]
          G.add_edges_from(edges)
          cc = sorted(nx.simple_cycles(G))
          assert_equal(len(cc), 26)
          rcc = sorted(nx.recursive_simple_cycles(G))
          assert_equal(len(cc), len(rcc))
          for c in cc:
              assert_true(any(self.is_cyclic_permutation(c, rc) for rc in rcc))
          for rc in rcc:
              assert_true(any(self.is_cyclic_permutation(rc, c) for c in cc))
  
  # These tests might fail with hash randomization since they depend on
  # edge_dfs. For more information, see the comments in:
  #    networkx/algorithms/traversal/tests/test_edgedfs.py
  
  
  class TestFindCycle(object):
      def setUp(self):
          self.nodes = [0, 1, 2, 3]
          self.edges = [(-1, 0), (0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]
  
      def test_graph_nocycle(self):
          G = nx.Graph(self.edges)
          assert_raises(nx.exception.NetworkXNoCycle, find_cycle, G, self.nodes)
  
      def test_graph_cycle(self):
          G = nx.Graph(self.edges)
          G.add_edge(2, 0)
          x = list(find_cycle(G, self.nodes))
          x_ = [(0, 1), (1, 2), (2, 0)]
          assert_equal(x, x_)
  
      def test_graph_orientation_none(self):
          G = nx.Graph(self.edges)
          G.add_edge(2, 0)
          x = list(find_cycle(G, self.nodes, orientation=None))
          x_ = [(0, 1), (1, 2), (2, 0)]
          assert_equal(x, x_)
  
      def test_graph_orientation_original(self):
          G = nx.Graph(self.edges)
          G.add_edge(2, 0)
          x = list(find_cycle(G, self.nodes, orientation='original'))
          x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 0, FORWARD)]
          assert_equal(x, x_)
  
      def test_digraph(self):
          G = nx.DiGraph(self.edges)
          x = list(find_cycle(G, self.nodes))
          x_ = [(0, 1), (1, 0)]
          assert_equal(x, x_)
  
      def test_digraph_orientation_none(self):
          G = nx.DiGraph(self.edges)
          x = list(find_cycle(G, self.nodes, orientation=None))
          x_ = [(0, 1), (1, 0)]
          assert_equal(x, x_)
  
      def test_digraph_orientation_original(self):
          G = nx.DiGraph(self.edges)
          x = list(find_cycle(G, self.nodes, orientation='original'))
          x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
          assert_equal(x, x_)
  
      def test_multigraph(self):
          G = nx.MultiGraph(self.edges)
          x = list(find_cycle(G, self.nodes))
          x_ = [(0, 1, 0), (1, 0, 1)]  # or (1, 0, 2)
          # Hash randomization...could be any edge.
          assert_equal(x[0], x_[0])
          assert_equal(x[1][:2], x_[1][:2])
  
      def test_multidigraph(self):
          G = nx.MultiDiGraph(self.edges)
          x = list(find_cycle(G, self.nodes))
          x_ = [(0, 1, 0), (1, 0, 0)]  # (1, 0, 1)
          assert_equal(x[0], x_[0])
          assert_equal(x[1][:2], x_[1][:2])
  
      def test_digraph_ignore(self):
          G = nx.DiGraph(self.edges)
          x = list(find_cycle(G, self.nodes, orientation='ignore'))
          x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
          assert_equal(x, x_)
  
      def test_digraph_reverse(self):
          G = nx.DiGraph(self.edges)
          x = list(find_cycle(G, self.nodes, orientation='reverse'))
          x_ = [(1, 0, REVERSE), (0, 1, REVERSE)]
          assert_equal(x, x_)
  
      def test_multidigraph_ignore(self):
          G = nx.MultiDiGraph(self.edges)
          x = list(find_cycle(G, self.nodes, orientation='ignore'))
          x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD)]  # or (1, 0, 1, 1)
          assert_equal(x[0], x_[0])
          assert_equal(x[1][:2], x_[1][:2])
          assert_equal(x[1][3], x_[1][3])
  
      def test_multidigraph_ignore2(self):
          # Loop traversed an edge while ignoring its orientation.
          G = nx.MultiDiGraph([(0, 1), (1, 2), (1, 2)])
          x = list(find_cycle(G, [0, 1, 2], orientation='ignore'))
          x_ = [(1, 2, 0, FORWARD), (1, 2, 1, REVERSE)]
          assert_equal(x, x_)
  
      def test_multidigraph_original(self):
          # Node 2 doesn't need to be searched again from visited from 4.
          # The goal here is to cover the case when 2 to be researched from 4,
          # when 4 is visited from the first time (so we must make sure that 4
          # is not visited from 2, and hence, we respect the edge orientation).
          G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 3), (4, 2)])
          assert_raises(nx.exception.NetworkXNoCycle,
                        find_cycle, G, [0, 1, 2, 3, 4], orientation='original')
  
      def test_dag(self):
          G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
          assert_raises(nx.exception.NetworkXNoCycle,
                        find_cycle, G, orientation='original')
          x = list(find_cycle(G, orientation='ignore'))
          assert_equal(x, [(0, 1, FORWARD), (1, 2, FORWARD), (0, 2, REVERSE)])
  
      def test_prev_explored(self):
          # https://github.com/networkx/networkx/issues/2323
  
          G = nx.DiGraph()
          G.add_edges_from([(1, 0), (2, 0), (1, 2), (2, 1)])
          assert_raises(nx.NetworkXNoCycle, find_cycle, G, source=0)
          x = list(nx.find_cycle(G, 1))
          x_ = [(1, 2), (2, 1)]
          assert_equal(x, x_)
  
          x = list(nx.find_cycle(G, 2))
          x_ = [(2, 1), (1, 2)]
          assert_equal(x, x_)
  
          x = list(nx.find_cycle(G))
          x_ = [(1, 2), (2, 1)]
          assert_equal(x, x_)
  
      def test_no_cycle(self):
          # https://github.com/networkx/networkx/issues/2439
  
          G = nx.DiGraph()
          G.add_edges_from([(1, 2), (2, 0), (3, 1), (3, 2)])
          assert_raises(nx.NetworkXNoCycle, find_cycle, G, source=0)
          assert_raises(nx.NetworkXNoCycle, find_cycle, G)
  
  
  def assert_basis_equal(a, b):
      assert_list_equal(sorted(a), sorted(b))
  
  
  class TestMinimumCycles(object):
      def setUp(self):
          T = nx.Graph()
          T.add_cycle([1, 2, 3, 4], weight=1)
          T.add_edge(2, 4, weight=5)
          self.diamond_graph = T
  
      def test_unweighted_diamond(self):
          mcb = minimum_cycle_basis(self.diamond_graph)
          assert_basis_equal(mcb, [[1, 2, 4], [2, 3, 4]])
  
      def test_weighted_diamond(self):
          mcb = minimum_cycle_basis(self.diamond_graph, weight='weight')
          assert_basis_equal(mcb, [[1, 2, 4], [1, 2, 3, 4]])
  
      def test_dimensionality(self):
          # checks |MCB|=|E|-|V|+|NC|
          ntrial = 10
          for _ in range(ntrial):
              rg = nx.erdos_renyi_graph(10, 0.3)
              nnodes = rg.number_of_nodes()
              nedges = rg.number_of_edges()
              ncomp = nx.number_connected_components(rg)
  
              dim_mcb = len(minimum_cycle_basis(rg))
              assert_equal(dim_mcb, nedges - nnodes + ncomp)
  
      def test_complete_graph(self):
          cg = nx.complete_graph(5)
          mcb = minimum_cycle_basis(cg)
          assert_true(all([len(cycle) == 3 for cycle in mcb]))
  
      def test_tree_graph(self):
          tg = nx.balanced_tree(3, 3)
          assert_false(minimum_cycle_basis(tg))
  