Source code: org/objectstyle/ashwood/test/TestApp.java
1 /* ====================================================================
2 *
3 * Copyright(c) 2003, Andriy Shapochka
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above
11 * copyright notice, this list of conditions and the following
12 * disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following
16 * disclaimer in the documentation and/or other materials
17 * provided with the distribution.
18 *
19 * 3. Neither the name of the ASHWOOD nor the
20 * names of its contributors may be used to endorse or
21 * promote products derived from this software without
22 * specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *
35 * ====================================================================
36 *
37 * This software consists of voluntary contributions made by
38 * individuals on behalf of the ASHWOOD Project and was originally
39 * created by Andriy Shapochka.
40 *
41 */
42
43 package org.objectstyle.ashwood.test;
44
45 import java.util.*;
46 import java.io.*;
47 import org.objectstyle.ashwood.graph.*;
48
49 public class TestApp {
50 static String[] vertices = {"A", "B", "C", "D", "E", "F", "G", "H", "K"};
51 public static void main(String[] args) throws Exception {
52 Digraph graph = new MapDigraph(MapDigraph.TREEMAP_FACTORY);
53 //loadDigraph(graph, new File("d:/temp/cycle.txt"));
54 //loadDigraph(graph, new File("d:/temp/sample_graph.txt"));
55 loadDigraph(graph, new File("d:/temp/test_graph.txt"));
56 System.out.println("===== Vertices =====");
57 for (Iterator i = graph.vertexIterator(); i.hasNext();) {
58 System.out.print(i.next() + ", ");
59 }
60 System.out.println();
61 System.out.println("===== Arcs =====");
62 for (ArcIterator i = graph.arcIterator(); i.hasNext();) {
63 Object arc = i.next();
64 Object origin = i.getOrigin();
65 Object dst = i.getDestination();
66 System.out.print(origin + " -> " + dst + ", ");
67 }
68 System.out.println();
69 System.out.println("===== Incoming Arcs =====");
70 for (Iterator j = graph.vertexIterator(); j.hasNext();) {
71 Object vertex = j.next();
72 System.out.print(vertex + "<-");
73 for (ArcIterator i = graph.incomingIterator(vertex); i.hasNext();) {
74 Object arc = i.next();
75 Object origin = i.getOrigin();
76 Object dst = i.getDestination();
77 System.out.print(origin + ", ");
78 }
79 System.out.println();
80 }
81 System.out.println("===== BFS =====");
82 Algorithm bfs = new BreadthFirstSearch(graph, "A");
83 while (bfs.hasNext()) {
84 System.out.print("->" + bfs.next());
85 }
86 System.out.println();
87 System.out.println("===== DFS 1 =====");
88 Algorithm dfs = new DepthFirstSearch(graph, "A");
89 while (dfs.hasNext()) {
90 System.out.print("->" + dfs.next());
91 }
92 System.out.println();
93 System.out.println("===== Reversed DFS 2 =====");
94 DepthFirstStampSearch dfss = new DepthFirstStampSearch(graph, "A");
95 while (dfss.hasNext()) {
96 System.out.print("->" + dfss.next() + "(" + dfss.getStamp() + ")");
97 }
98 System.out.println();
99 System.out.println("===== DFS 2 Traverse =====");
100 dfss.reset("A");
101 Map orders = dfss.traverse(new HashMap());
102 for (Iterator i = graph.vertexIterator(); i.hasNext();) {
103 Object vertex = i.next();
104 System.out.print("; " + vertex + orders.get(vertex));
105 }
106 System.out.println();
107 System.out.println("===== Strongly Connected =====");
108 System.out.println(GraphUtils.isStronglyConnected(graph));
109 System.out.println();
110 System.out.println("===== Acyclic =====");
111 System.out.println(GraphUtils.isAcyclic(graph));
112 System.out.println();
113 System.out.println("===== DFS 2 Reversed Topological Sort =====");
114 DFSReverseTopologicalSort ts = new DFSReverseTopologicalSort(graph, "A");
115 System.out.print("Reversed: ");
116 int order = 0;
117 while (ts.hasNext())
118 System.out.print(ts.next() + "(" + (++order) + "), ");
119 System.out.println();
120
121 ts.reset("A");
122 System.out.print("Direct: ");
123 SortedMap sortedVertices = ts.sort();
124 for (Iterator i = sortedVertices.entrySet().iterator(); i.hasNext();) {
125 Map.Entry entry = (Map.Entry)i.next();
126 System.out.print(entry.getValue() + "(" + entry.getKey() + "), ");
127 }
128 System.out.println();
129 System.out.println("===== In-degree Topological Sort =====");
130 Algorithm ints = new IndegreeTopologicalSort(graph);
131 while (ints.hasNext()) {
132 Object vertex = ints.next();
133 if (vertex == null) {
134 System.out.println();
135 System.out.println("Cycle found!");
136 break;
137 }
138 System.out.print(vertex + ", ");
139 }
140 System.out.println();
141 System.out.println("===== Strongly Connected Components =====");
142 StrongConnection sc = new StrongConnection(graph, CollectionFactory.ARRAYLIST_FACTORY);
143 int index = 0;
144 while (sc.hasNext()) {
145 index++;
146 Collection component = (Collection)sc.next();
147 System.out.print("comp " + index + ": ");
148 for (Iterator i = component.iterator(); i.hasNext();) {
149 Object vertex = i.next();
150 System.out.print(vertex + ", ");
151 }
152 System.out.println();
153 }
154 System.out.println("===== Strongly Connected Component Contraction =====");
155 sc = new StrongConnection(graph, CollectionFactory.ARRAYLIST_FACTORY);
156 Digraph contractedGraph = new MapDigraph(MapDigraph.HASHMAP_FACTORY);
157 sc.contract(contractedGraph);
158 System.out.println("===== Contracted Vertices =====");
159 for (Iterator i = contractedGraph.vertexIterator(); i.hasNext();) {
160 Collection vertex = (Collection)i.next();
161 System.out.print('{');
162 for (Iterator j = vertex.iterator(); j.hasNext();)
163 System.out.print(j.next() + ", ");
164 System.out.println("}");
165 }
166 System.out.println("===== Contracted Arcs =====");
167 for (ArcIterator i = contractedGraph.arcIterator(); i.hasNext();) {
168 Object arc = i.next();
169 Collection origin = (Collection)i.getOrigin();
170 Collection dst = (Collection)i.getDestination();
171 System.out.print('{');
172 if (origin != null) {
173 for (Iterator j = origin.iterator(); j.hasNext();)
174 System.out.print(j.next() + ", ");
175 }
176 System.out.print("} -> {");
177 if (dst != null) {
178 for (Iterator j = dst.iterator(); j.hasNext();)
179 System.out.print(j.next() + ", ");
180 }
181 System.out.println('}');
182 }
183 }
184
185 static void loadDigraph(Digraph graph, File source) throws Exception {
186 Properties ps = new Properties();
187 FileInputStream in = new FileInputStream(source);
188 ps.load(in);
189 in.close();
190 for (Iterator i = ps.entrySet().iterator(); i.hasNext();) {
191 Map.Entry entry = (Map.Entry)i.next();
192 Object origin = entry.getKey();
193 StringTokenizer st = new StringTokenizer((String)entry.getValue(), ";");
194 while (st.hasMoreTokens()) {
195 graph.putArc(origin, st.nextToken(), Boolean.TRUE);
196 }
197 }
198 }
199 }