Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | * | |
10 | * Created on Mar 3, 2004 | |
11 | */ | |
12 | package edu.uci.ics.jung.graph.predicates; | |
13 | ||
14 | import java.util.HashSet; | |
15 | import java.util.Iterator; | |
16 | import java.util.LinkedList; | |
17 | import java.util.Set; | |
18 | ||
19 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
20 | import edu.uci.ics.jung.graph.Graph; | |
21 | import edu.uci.ics.jung.graph.Vertex; | |
22 | ||
23 | /** | |
24 | * | |
25 | * @author Joshua O'Madadhain | |
26 | */ | |
27 | public class ConnectedGraphPredicate extends GraphPredicate | |
28 | { | |
29 | private static ConnectedGraphPredicate instance; | |
30 | 1 | private static String message = "connected graph predicate"; |
31 | ||
32 | /** | |
33 | * Returns an instance of this class. | |
34 | */ | |
35 | public static ConnectedGraphPredicate getInstance() | |
36 | { | |
37 | 1 | if (instance == null) |
38 | 1 | instance = new ConnectedGraphPredicate(); |
39 | 1 | return instance; |
40 | } | |
41 | ||
42 | protected ConnectedGraphPredicate() | |
43 | { | |
44 | 1 | super(); |
45 | 1 | } |
46 | ||
47 | public String toString() | |
48 | { | |
49 | 0 | return message; |
50 | } | |
51 | ||
52 | /** | |
53 | * Returns <code>true</code> if there exists a path from each | |
54 | * vertex to all other vertices (ignoring edge direction). | |
55 | * | |
56 | * <p>Returns <code>true</code> for an empty graph.</p> | |
57 | * | |
58 | * @see org.apache.commons.collections.Predicate#evaluate(java.lang.Object) | |
59 | */ | |
60 | public boolean evaluateGraph(ArchetypeGraph graph) | |
61 | { | |
62 | 3 | Graph g = (Graph)graph; |
63 | 3 | if (g.numVertices() == 0) |
64 | 0 | return true; |
65 | ||
66 | 3 | Vertex start = (Vertex)g.getVertices().iterator().next(); // pick any vertex |
67 | 3 | Set visited = new HashSet(); |
68 | 3 | LinkedList stack = new LinkedList(); |
69 | 3 | stack.add(start); |
70 | // traverse through graph in depth-first order | |
71 | 11 | while (!stack.isEmpty()) |
72 | { | |
73 | 8 | Vertex v = (Vertex)stack.removeFirst(); |
74 | 8 | visited.add(v); |
75 | 8 | Set neighbors = v.getNeighbors(); |
76 | 8 | for (Iterator n_it = neighbors.iterator(); n_it.hasNext(); ) |
77 | { | |
78 | 10 | Vertex w = (Vertex)n_it.next(); |
79 | 10 | if (!visited.contains(w)) |
80 | 5 | stack.addFirst(w); |
81 | } | |
82 | } | |
83 | 3 | return (visited.size() == g.numVertices()); |
84 | } | |
85 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |