Coverage details for edu.uci.ics.jung.algorithms.blockmodel.StructurallyEquivalentII

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 /*
11  * Created on Jan 28, 2004
12  */
13 package edu.uci.ics.jung.algorithms.blockmodel;
14 import java.util.*;
15  
16 import edu.uci.ics.jung.graph.Graph;
17 import edu.uci.ics.jung.graph.Vertex;
18 import edu.uci.ics.jung.utils.Pair;
19 /**
20  * Checks a graph for sets of structurally equivalent vertices: vertices that
21  * share all the same edges. Specifically, In order for a pair of vertices <i>
22  * i </i> and <i>j </i> to be structurally equivalent, the set of <i>i </i>'s
23  * neighbors must be identical to the set of <i>j </i>'s neighbors, with the
24  * exception of <i>i </i> and <i>j </i> themselves. This algorithm finds all
25  * sets of equivalent vertices in O(V^2) time.
26  *
27  * You can extend this class to have a different definition of equivalence (by
28  * overriding "isStructurallyEquivalent"), and may give it hints for
29  * accelerating the process by overriding canpossiblycompare. (For example, in
30  * a bipartitegraph, canPossiblyCompare may return false for vertices in
31  * different partitions. This function should be fast.)
32  *
33  * @author danyelf
34  */
35 public class StructurallyEquivalentII extends StructurallyEquivalent {
36  
37     public static StructurallyEquivalent getInstance() {
384        if (instance == null) {
391            instance = new StructurallyEquivalentII();
40         }
414        return instance;
42     }
43  
441    public StructurallyEquivalentII() {
451    }
46  
47     /**
48      * For each vertex pair v, v1 in G, checks whether v and v1 are fully
49      * equivalent: meaning that they connect to the exact same vertices. (Is
50      * this regular equivalence, or whathaveyou?)
51      *
52      * Returns a Set of Pairs of vertices, where all the vertices in the inner
53      * Pairs are equivalent.
54      *
55      * @param g
56      */
57     public Set checkEquivalent(Graph g) {
586        Set rv = new HashSet();
59         /*
60          * this is kind of subtle. if a vertex is equivalent to any other
61          * vertex, then all the equivalences will be found on the first pass.
62          * That is : if A is equivalent to B, then there are no neighbors of B
63          * that are equivalent to it that are not also neighbors of A.
64          */
656        Set alreadyEquivalent = new HashSet();
66         /*
67          * Tracks all vertices that we've used as an origin point.
68          */
696        Set alreadyChecked = new HashSet();
706        List l = new ArrayList(g.getVertices());
716        for (Iterator iter = l.iterator(); iter.hasNext();) {
7228            Vertex v1 = (Vertex) iter.next();
7328            alreadyChecked.add(v1);
7428            if (alreadyEquivalent.contains(v1))
7512                continue;
7616            boolean haveHitOne = false;
7716            Set neighbors = new HashSet( v1.getNeighbors() );
7816            neighbors.removeAll( alreadyChecked );
79             // check if we're equivalent to any neighbor
8016            for (Iterator iterator = neighbors.iterator(); iterator.hasNext();) {
8118                Vertex v2 = (Vertex) iterator.next();
8218                haveHitOne |= checkEquivalence(v1, v2, alreadyEquivalent, rv );
83             }
84  
85             // if we aren't, then we might be equivalent to one or another 2nd
86             // remove neighbor
87             // NOTE: v1 can only be equiv to a second-neighbor if it is not
88             // equivalnt to a first neighbor
8916            if (!haveHitOne) {
9016                Set secondNeighbors = getSecondNeighbors(v1);
9116                secondNeighbors.removeAll(alreadyChecked);
9216                for (Iterator iterator = secondNeighbors.iterator(); iterator
9341                        .hasNext();) {
9425                    Vertex v2 = (Vertex) iterator.next();
9525                    checkEquivalence(v1, v2, alreadyEquivalent, rv );
96                 }
97  
98             }
99         }
1006        return rv;
101     }
102     
103     
104     boolean checkEquivalence( Vertex v1, Vertex v2, Set alreadyEquivalent, Set rv ) {
10543        if (alreadyEquivalent.contains(v2))
1065            return false;
10738        if (!canpossiblycompare(v1, v2))
1080            return false;
10938        if (isStructurallyEquivalent(v1, v2)) {
11012            Pair p = new Pair(v1, v2);
11112            alreadyEquivalent.add(v2);
11212            rv.add(p);
11312            return true;
114         }
11526        return false;
116     }
117     
118     private Set getSecondNeighbors(Vertex v1) {
11916        Set secondNeighbors = new HashSet();
12016        for (Iterator iterator = v1.getNeighbors().iterator(); iterator
12155                .hasNext();) {
12239            Vertex intermediate = (Vertex) iterator.next();
12339            secondNeighbors.addAll(intermediate.getNeighbors());
124         }
12516        return secondNeighbors;
126     }
127  
128 }

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.