Source code: com/port80/graph/algorithm/impl/DFDirectedVertexWalker.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 transversal of a directed graph.
12 */
13 public class DFDirectedVertexWalker implements IVertexWalker {
14
15 ////////////////////////////////////////////////////////////////////////
16
17 public static List walks(IVertex start) {
18 return new DFDirectedVertexWalker().walk(start);
19 }
20 public static Object walks(IVertex start, IVertexVisitor visitor, Object data) {
21 return new DFDirectedVertexWalker().walk(start, visitor, data);
22 }
23 public static Object walks(IVertex start, IDFVertexVisitor visitor, Object data) {
24 return new DFDirectedVertexWalker().walk(start, visitor, data);
25 }
26
27 ////////////////////////////////////////////////////////////////////////
28
29 public List walk(IVertex start) {
30 List ret = new ArrayList();
31 Set visited = new HashSet();
32 //
33 visited.add(start);
34 return dfWalk(start, visited, ret);
35 }
36
37 public Object walk(IVertex start, IVertexVisitor visitor, Object data) {
38 Set visited = new HashSet();
39 //
40 visited.add(start);
41 return dfWalk(start, visited, visitor, data);
42 }
43
44 public Object walk(IVertex start, IDFVertexVisitor visitor, Object data) {
45 Set visited = new HashSet();
46 //
47 visited.add(start);
48 return dfWalk(start, visited, visitor, data);
49 }
50
51 ////////////////////////////////////////////////////////////////////////
52
53 private List dfWalk(IVertex start, Set visited, List ret) {
54 IVertex v;
55 IEdge[] outs = start.outs();
56 for (int i = 0, max = outs.length; i < max; ++i) {
57 v = outs[i].getHead();
58 if (visited.add(v)) dfWalk(v, visited, ret);
59 }
60 ret.add(start);
61 return ret;
62 }
63
64 private Object dfWalk(IVertex start, Set visited, IVertexVisitor visitor, Object data) {
65 IVertex v;
66 IEdge[] outs = start.outs();
67 for (int i = 0, max = outs.length; i < max; ++i) {
68 v = outs[i].getHead();
69 if (visited.add(v)) dfWalk(v, visited, visitor, data);
70 }
71 visitor.visit(start, visited, data);
72 return data;
73 }
74
75 private Object dfWalk(IVertex start, Set visited, IDFVertexVisitor visitor, Object data) {
76 IVertex v;
77 visitor.preVisit(start,visited,data);
78 IEdge[] outs = start.outs();
79 for (int i = 0, max = outs.length; i < max; ++i) {
80 v = outs[i].getHead();
81 if (visited.add(v)) dfWalk(v, visited, visitor, data);
82 }
83 visitor.visit(start, visited, data);
84 return data;
85 }
86
87 ////////////////////////////////////////////////////////////////////////
88
89 }