Coverage details for edu.uci.ics.jung.graph.predicates.ConnectedGraphPredicate

LineHitsSource
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;
301    private static String message = "connected graph predicate";
31     
32     /**
33      * Returns an instance of this class.
34      */
35     public static ConnectedGraphPredicate getInstance()
36     {
371        if (instance == null)
381            instance = new ConnectedGraphPredicate();
391        return instance;
40     }
41     
42     protected ConnectedGraphPredicate()
43     {
441        super();
451    }
46     
47     public String toString()
48     {
490        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     {
623        Graph g = (Graph)graph;
633        if (g.numVertices() == 0)
640            return true;
65         
663        Vertex start = (Vertex)g.getVertices().iterator().next(); // pick any vertex
673        Set visited = new HashSet();
683        LinkedList stack = new LinkedList();
693        stack.add(start);
70         // traverse through graph in depth-first order
7111        while (!stack.isEmpty())
72         {
738            Vertex v = (Vertex)stack.removeFirst();
748            visited.add(v);
758            Set neighbors = v.getNeighbors();
768            for (Iterator n_it = neighbors.iterator(); n_it.hasNext(); )
77             {
7810                Vertex w = (Vertex)n_it.next();
7910                if (!visited.contains(w))
805                    stack.addFirst(w);
81             }
82         }
833        return (visited.size() == g.numVertices());
84     }
85 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.