Source code: com/port80/graph/algorithm/impl/DFTBDirectedVertexWalker.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.algorithm.impl;
6
7 import java.util.*;
8 import com.port80.graph.*;
9 import com.port80.graph.algorithm.*;
10
11 /** Depth first top to bottom transversal of a directed graph.
12 *
13 * . This is not a strictly depth first transversal. Depth first
14 * transversal should return the bottom-left first and the root last.
15 * . This transversal walk from top to bottom from left to right.
16 *
17 * The same order can be archived by using the IDFVertexVisitor.preVisit() and
18 * DFDirectedVertexWalker.walk(IVertex,Set,IDFVertexVisitor,Object).
19 */
20 public class DFTBDirectedVertexWalker implements IVertexWalker {
21
22 ////////////////////////////////////////////////////////////////////////
23
24 public static List walks(IVertex start) {
25 return new DFTBDirectedVertexWalker().walk(start);
26 }
27 public static Object walks(IVertex start, IVertexVisitor visitor, Object data) {
28 return new DFTBDirectedVertexWalker().walk(start, visitor, data);
29 }
30
31 ////////////////////////////////////////////////////////////////////////
32
33 public List walk(IVertex start) {
34 Set visited = new HashSet();
35 List queue = new ArrayList();
36 Stack stack = new Stack();
37 IVertex v;
38 IEdge[] outs;
39 int size = 1;
40 //
41 stack.push(start);
42 visited.add(start);
43 while (size != 0) {
44 v = (IVertex)stack.pop();
45 queue.add(v);
46 --size;
47 outs = v.outs();
48 for (int i = 0, max = outs.length; i < max; ++i) {
49 v = outs[i].getHead();
50 if (visited.add(v)) {
51 stack.push(v);
52 ++size;
53 }
54 }
55 }
56 return queue;
57 }
58
59 public Object walk(IVertex start, IVertexVisitor visitor, Object data) {
60 Set visited = new HashSet();
61 Stack stack = new Stack();
62 IVertex v;
63 IEdge[] outs;
64 int size = 1;
65 //
66 stack.push(start);
67 visited.add(start);
68 while (size != 0) {
69 v = (IVertex)stack.pop();
70 if (!visitor.visit(v, visited, data)) return data;
71 --size;
72 outs = v.outs();
73 for (int i = 0, max = outs.length; i < max; ++i) {
74 v = outs[i].getHead();
75 if (visited.add(v)) {
76 stack.push(v);
77 ++size;
78 }
79 }
80 }
81 return data;
82 }
83 }