| 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 | /* | |
| 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 | ||
| 45 | 2 | static StructurallyEquivalent instance = null; |
| 46 | ||
| 47 | public static StructurallyEquivalent getInstance() { | |
| 48 | 3 | if ( instance == null ) { |
| 49 | 1 | instance = new StructurallyEquivalent(); |
| 50 | } | |
| 51 | 3 | return instance; |
| 52 | } | |
| 53 | ||
| 54 | 2 | public StructurallyEquivalent() { |
| 55 | ||
| 56 | 2 | } |
| 57 | ||
| 58 | public EquivalenceRelation getEquivalences(Graph g) { | |
| 59 | 8 | 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) { | |
| 67 | 8 | Set rv = new HashSet(); |
| 68 | 8 | Map intermediate = new HashMap(); |
| 69 | 8 | for (Iterator iter = s.iterator(); iter.hasNext();) { |
| 70 | 20 | Pair p = (Pair) iter.next(); |
| 71 | 20 | Set res = (Set) intermediate.get(p.getFirst()); |
| 72 | 20 | if (res == null) |
| 73 | 12 | res = (Set) intermediate.get(p.getSecond()); |
| 74 | 20 | if (res == null) { |
| 75 | // we haven't seen this one before | |
| 76 | 12 | res = new HashSet(); |
| 77 | } | |
| 78 | 20 | res.add(p.getFirst()); |
| 79 | 20 | res.add(p.getSecond()); |
| 80 | 20 | intermediate.put(p.getFirst(), res); |
| 81 | 20 | intermediate.put(p.getSecond(), res); |
| 82 | ||
| 83 | } | |
| 84 | 8 | rv.addAll(intermediate.values()); |
| 85 | 8 | 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 | ||
| 100 | 3 | Set rv = new HashSet(); |
| 101 | 3 | Set alreadyEquivalent = new HashSet(); |
| 102 | ||
| 103 | 3 | List l = new ArrayList(g.getVertices()); |
| 104 | ||
| 105 | 3 | for (Iterator iter = l.iterator(); iter.hasNext();) { |
| 106 | 20 | Vertex v1 = (Vertex) iter.next(); |
| 107 | ||
| 108 | 20 | if (alreadyEquivalent.contains(v1)) |
| 109 | 10 | continue; |
| 110 | ||
| 111 | 10 | for (Iterator iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) { |
| 112 | 40 | Vertex v2 = (Vertex) iterator.next(); |
| 113 | ||
| 114 | 40 | if (alreadyEquivalent.contains(v2)) |
| 115 | 16 | continue; |
| 116 | ||
| 117 | 24 | if (!canpossiblycompare(v1, v2)) |
| 118 | 0 | continue; |
| 119 | ||
| 120 | 24 | if (isStructurallyEquivalent(v1, v2)) { |
| 121 | 10 | Pair p = new Pair(v1, v2); |
| 122 | 10 | alreadyEquivalent.add(v2); |
| 123 | 10 | rv.add(p); |
| 124 | } | |
| 125 | ||
| 126 | } | |
| 127 | } | |
| 128 | ||
| 129 | 3 | 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 | ||
| 143 | 62 | count ++; |
| 144 | ||
| 145 | 62 | if( v1.degree() != v2.degree()) { |
| 146 | 37 | return false; |
| 147 | } | |
| 148 | ||
| 149 | 25 | Set n1 = new HashSet(v1.getPredecessors()); |
| 150 | 25 | n1.remove(v2); |
| 151 | 25 | n1.remove(v1); |
| 152 | 25 | Set n2 = new HashSet(v2.getPredecessors()); |
| 153 | 25 | n2.remove(v1); |
| 154 | 25 | n2.remove(v2); |
| 155 | ||
| 156 | 25 | Set o1 = new HashSet(v1.getSuccessors()); |
| 157 | 25 | Set o2 = new HashSet(v2.getSuccessors()); |
| 158 | 25 | o1.remove(v1); |
| 159 | 25 | o1.remove(v2); |
| 160 | 25 | o2.remove(v1); |
| 161 | 25 | o2.remove(v2); |
| 162 | ||
| 163 | // this neglects self-loops and directed edges from 1 to other | |
| 164 | 25 | boolean b = (n1.equals(n2) && o1.equals(o2)); |
| 165 | 25 | if (!b) |
| 166 | 3 | return b; |
| 167 | ||
| 168 | // if there's a directed edge v1->v2 then there's a directed edge v2->v1 | |
| 169 | 22 | b &= ( v1.isSuccessorOf(v2) == v1.isSuccessorOf(v2)); |
| 170 | ||
| 171 | // self-loop check | |
| 172 | 22 | b &= ( v1.isSuccessorOf(v1) == v2.isSuccessorOf(v2)); |
| 173 | ||
| 174 | 22 | return b; |
| 175 | ||
| 176 | } | |
| 177 | ||
| 178 | 2 | 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) { | |
| 188 | 62 | return true; |
| 189 | } | |
| 190 | ||
| 191 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |