a

doum

23 小时以前 307960b07d8cb122d9de0c8267b8cb7a63cfc605

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/env python
 
# Copyright 2013 Google Inc. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
 
"""Unit tests for the input.py file."""
 
import gyp.input
import unittest
import sys
 
 
class TestFindCycles(unittest.TestCase):
  def setUp(self):
    self.nodes = {}
    for x in ('a', 'b', 'c', 'd', 'e'):
      self.nodes[x] = gyp.input.DependencyGraphNode(x)
 
  def _create_dependency(self, dependent, dependency):
    dependent.dependencies.append(dependency)
    dependency.dependents.append(dependent)
 
  def test_no_cycle_empty_graph(self):
    for label, node in self.nodes.iteritems():
      self.assertEquals([], node.FindCycles())
 
  def test_no_cycle_line(self):
    self._create_dependency(self.nodes['a'], self.nodes['b'])
    self._create_dependency(self.nodes['b'], self.nodes['c'])
    self._create_dependency(self.nodes['c'], self.nodes['d'])
 
    for label, node in self.nodes.iteritems():
      self.assertEquals([], node.FindCycles())
 
  def test_no_cycle_dag(self):
    self._create_dependency(self.nodes['a'], self.nodes['b'])
    self._create_dependency(self.nodes['a'], self.nodes['c'])
    self._create_dependency(self.nodes['b'], self.nodes['c'])
 
    for label, node in self.nodes.iteritems():
      self.assertEquals([], node.FindCycles())
 
  def test_cycle_self_reference(self):
    self._create_dependency(self.nodes['a'], self.nodes['a'])
 
    self.assertEquals([[self.nodes['a'], self.nodes['a']]],
                      self.nodes['a'].FindCycles())
 
  def test_cycle_two_nodes(self):
    self._create_dependency(self.nodes['a'], self.nodes['b'])
    self._create_dependency(self.nodes['b'], self.nodes['a'])
 
    self.assertEquals([[self.nodes['a'], self.nodes['b'], self.nodes['a']]],
                      self.nodes['a'].FindCycles())
    self.assertEquals([[self.nodes['b'], self.nodes['a'], self.nodes['b']]],
                      self.nodes['b'].FindCycles())
 
  def test_two_cycles(self):
    self._create_dependency(self.nodes['a'], self.nodes['b'])
    self._create_dependency(self.nodes['b'], self.nodes['a'])
 
    self._create_dependency(self.nodes['b'], self.nodes['c'])
    self._create_dependency(self.nodes['c'], self.nodes['b'])
 
    cycles = self.nodes['a'].FindCycles()
    self.assertTrue(
       [self.nodes['a'], self.nodes['b'], self.nodes['a']] in cycles)
    self.assertTrue(
       [self.nodes['b'], self.nodes['c'], self.nodes['b']] in cycles)
    self.assertEquals(2, len(cycles))
 
  def test_big_cycle(self):
    self._create_dependency(self.nodes['a'], self.nodes['b'])
    self._create_dependency(self.nodes['b'], self.nodes['c'])
    self._create_dependency(self.nodes['c'], self.nodes['d'])
    self._create_dependency(self.nodes['d'], self.nodes['e'])
    self._create_dependency(self.nodes['e'], self.nodes['a'])
 
    self.assertEquals([[self.nodes['a'],
                        self.nodes['b'],
                        self.nodes['c'],
                        self.nodes['d'],
                        self.nodes['e'],
                        self.nodes['a']]],
                      self.nodes['a'].FindCycles())
 
 
if __name__ == '__main__':
  unittest.main()