OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 import 'package:dart2js_info/src/graph.dart'; |
| 6 import 'package:test/test.dart'; |
| 7 |
| 8 main() { |
| 9 var graph = makeTestGraph(); |
| 10 |
| 11 test('preorder traversal', () { |
| 12 expect(graph.preOrder('A').toList(), equals(['A', 'E', 'D', 'C', 'B'])); |
| 13 }); |
| 14 |
| 15 test('postorder traversal', () { |
| 16 expect(graph.postOrder('A').toList(), equals(['C', 'E', 'D', 'B', 'A'])); |
| 17 }); |
| 18 |
| 19 test('topological sort', () { |
| 20 expect( |
| 21 graph.computeTopologicalSort(), |
| 22 equals([ |
| 23 ['C'], |
| 24 ['E'], |
| 25 ['D', 'B', 'A'] |
| 26 ])); |
| 27 }); |
| 28 |
| 29 test('contains path', () { |
| 30 expect(graph.containsPath('A', 'C'), isTrue); |
| 31 expect(graph.containsPath('B', 'E'), isTrue); |
| 32 expect(graph.containsPath('C', 'A'), isFalse); |
| 33 expect(graph.containsPath('E', 'B'), isFalse); |
| 34 }); |
| 35 |
| 36 test('dominator tree', () { |
| 37 // A dominates all other nodes in the graph, the resulting tree looks like |
| 38 // A |
| 39 // / / | | |
| 40 // B C D E |
| 41 var dom = graph.dominatorTree('A'); |
| 42 expect(dom.targetsOf('A').length, equals(4)); |
| 43 }); |
| 44 |
| 45 test('cycle finding', () { |
| 46 expect(graph.findCycleContaining('B'), equals(['A', 'D', 'B'])); |
| 47 expect(graph.findCycleContaining('C'), equals(['C'])); |
| 48 }); |
| 49 } |
| 50 |
| 51 /// Creates a simple test graph with the following structure: |
| 52 /// ``` |
| 53 /// A -> E |
| 54 /// / ^ ^ |
| 55 /// / \ / |
| 56 /// v v / |
| 57 /// B -> D |
| 58 /// \ / |
| 59 /// v v |
| 60 /// C |
| 61 /// ``` |
| 62 Graph<String> makeTestGraph() { |
| 63 var graph = new EdgeListGraph<String>(); |
| 64 graph.addEdge('A', 'B'); |
| 65 graph.addEdge('A', 'D'); |
| 66 graph.addEdge('A', 'E'); |
| 67 graph.addEdge('B', 'C'); |
| 68 graph.addEdge('B', 'D'); |
| 69 graph.addEdge('D', 'A'); |
| 70 graph.addEdge('D', 'C'); |
| 71 graph.addEdge('D', 'E'); |
| 72 return graph; |
| 73 } |
OLD | NEW |