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

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  
15 import java.util.ArrayList;
16 import java.util.HashMap;
17 import java.util.HashSet;
18 import java.util.Iterator;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.Set;
22  
23 import edu.uci.ics.jung.graph.Graph;
24 import edu.uci.ics.jung.graph.Vertex;
25 import edu.uci.ics.jung.utils.Pair;
26  
27 /**
28  * Checks a graph for sets of structurally equivalent vertices: vertices that
29  * share all the same edges. Specifically, In order for a pair of vertices <i>
30  * i</i> and <i>j</i> to be structurally equivalent, the set of <i>i</i>'s
31  * neighbors must be identical to the set of <i>j</i>'s neighbors, with the
32  * exception of <i>i</i> and <i>j</i> themselves. This algorithm finds all
33  * sets of equivalent vertices in O(V^2) time.
34  *
35  * You can extend this class to have a different definition of equivalence (by
36  * overriding "isStructurallyEquivalent"), and may give it hints for
37  * accelerating the process by overriding canpossiblycompare. (For example, in
38  * a bipartitegraph, canPossiblyCompare may return false for vertices in
39  * different partitions. This function should be fast.)
40  *
41  * @author danyelf
42  */
43 public class StructurallyEquivalent implements EquivalenceAlgorithm {
44  
452    static StructurallyEquivalent instance = null;
46     
47     public static StructurallyEquivalent getInstance() {
483        if ( instance == null ) {
491            instance = new StructurallyEquivalent();
50         }
513        return instance;
52     }
53     
542    public StructurallyEquivalent() {
55  
562    }
57  
58     public EquivalenceRelation getEquivalences(Graph g) {
598        return createEquivalenceClasses(g, checkEquivalent(g));
60     }
61  
62     /**
63      * Takes in a Set of Pairs (as in the resutls of checkEquivalent) and
64      * massages into a Set of Sets, where each Set is an equivalence class.
65      */
66     protected EquivalenceRelation createEquivalenceClasses(Graph g, Set s) {
678        Set rv = new HashSet();
688        Map intermediate = new HashMap();
698        for (Iterator iter = s.iterator(); iter.hasNext();) {
7020            Pair p = (Pair) iter.next();
7120            Set res = (Set) intermediate.get(p.getFirst());
7220            if (res == null)
7312                res = (Set) intermediate.get(p.getSecond());
7420            if (res == null) {
75                 // we haven't seen this one before
7612                res = new HashSet();
77             }
7820            res.add(p.getFirst());
7920            res.add(p.getSecond());
8020            intermediate.put(p.getFirst(), res);
8120            intermediate.put(p.getSecond(), res);
82  
83         }
848        rv.addAll(intermediate.values());
858        return new EquivalenceRelation(rv, g);
86     }
87  
88     /**
89      * For each vertex pair v, v1 in G, checks whether v and v1 are fully
90      * equivalent: meaning that they connect to the exact same vertices. (Is
91      * this regular equivalence, or whathaveyou?)
92      *
93      * Returns a Set of Pairs of vertices, where all the vertices in the inner
94      * Pairs are equivalent.
95      *
96      * @param g
97      */
98     public Set checkEquivalent(Graph g) {
99  
1003        Set rv = new HashSet();
1013        Set alreadyEquivalent = new HashSet();
102  
1033        List l = new ArrayList(g.getVertices());
104  
1053        for (Iterator iter = l.iterator(); iter.hasNext();) {
10620            Vertex v1 = (Vertex) iter.next();
107  
10820            if (alreadyEquivalent.contains(v1))
10910                continue;
110  
11110            for (Iterator iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) {
11240                Vertex v2 = (Vertex) iterator.next();
113  
11440                if (alreadyEquivalent.contains(v2))
11516                    continue;
116  
11724                if (!canpossiblycompare(v1, v2))
1180                    continue;
119  
12024                if (isStructurallyEquivalent(v1, v2)) {
12110                    Pair p = new Pair(v1, v2);
12210                    alreadyEquivalent.add(v2);
12310                    rv.add(p);
124                 }
125  
126             }
127         }
128  
1293        return rv;
130  
131     }
132  
133     /**
134      * Checks whether a pair of vertices are structurally equivalent.
135      * Specifically, whether v1's predecessors are equal to v2's predecessors,
136      * and same for successors.
137      *
138      * @param v1
139      * @param v2
140      */
141     protected boolean isStructurallyEquivalent(Vertex v1, Vertex v2) {
142         
14362        count ++;
144         
14562        if( v1.degree() != v2.degree()) {
14637            return false;
147         }
148  
14925        Set n1 = new HashSet(v1.getPredecessors());
15025        n1.remove(v2);
15125        n1.remove(v1);
15225        Set n2 = new HashSet(v2.getPredecessors());
15325        n2.remove(v1);
15425        n2.remove(v2);
155  
15625        Set o1 = new HashSet(v1.getSuccessors());
15725        Set o2 = new HashSet(v2.getSuccessors());
15825        o1.remove(v1);
15925        o1.remove(v2);
16025        o2.remove(v1);
16125        o2.remove(v2);
162  
163         // this neglects self-loops and directed edges from 1 to other
16425        boolean b = (n1.equals(n2) && o1.equals(o2));
16525        if (!b)
1663            return b;
167         
168         // if there's a directed edge v1->v2 then there's a directed edge v2->v1
16922        b &= ( v1.isSuccessorOf(v2) == v1.isSuccessorOf(v2));
170         
171         // self-loop check
17222        b &= ( v1.isSuccessorOf(v1) == v2.isSuccessorOf(v2));
173  
17422        return b;
175  
176     }
177  
1782    public static int count = 0;
179     
180     /**
181      * This is a space for optimizations. For example, for a bipartitegraph,
182      * vertices from class_A and class_B cannot possibly be compared.
183      *
184      * @param v1
185      * @param v2
186      */
187     protected boolean canpossiblycompare(Vertex v1, Vertex v2) {
18862        return true;
189     }
190  
191 }

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.