| 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 | 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() { | |
| 38 | 4 | if (instance == null) { |
| 39 | 1 | instance = new StructurallyEquivalentII(); |
| 40 | } | |
| 41 | 4 | return instance; |
| 42 | } | |
| 43 | ||
| 44 | 1 | public StructurallyEquivalentII() { |
| 45 | 1 | } |
| 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) { | |
| 58 | 6 | 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 | */ | |
| 65 | 6 | Set alreadyEquivalent = new HashSet(); |
| 66 | /* | |
| 67 | * Tracks all vertices that we've used as an origin point. | |
| 68 | */ | |
| 69 | 6 | Set alreadyChecked = new HashSet(); |
| 70 | 6 | List l = new ArrayList(g.getVertices()); |
| 71 | 6 | for (Iterator iter = l.iterator(); iter.hasNext();) { |
| 72 | 28 | Vertex v1 = (Vertex) iter.next(); |
| 73 | 28 | alreadyChecked.add(v1); |
| 74 | 28 | if (alreadyEquivalent.contains(v1)) |
| 75 | 12 | continue; |
| 76 | 16 | boolean haveHitOne = false; |
| 77 | 16 | Set neighbors = new HashSet( v1.getNeighbors() ); |
| 78 | 16 | neighbors.removeAll( alreadyChecked ); |
| 79 | // check if we're equivalent to any neighbor | |
| 80 | 16 | for (Iterator iterator = neighbors.iterator(); iterator.hasNext();) { |
| 81 | 18 | Vertex v2 = (Vertex) iterator.next(); |
| 82 | 18 | 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 | |
| 89 | 16 | if (!haveHitOne) { |
| 90 | 16 | Set secondNeighbors = getSecondNeighbors(v1); |
| 91 | 16 | secondNeighbors.removeAll(alreadyChecked); |
| 92 | 16 | for (Iterator iterator = secondNeighbors.iterator(); iterator |
| 93 | 41 | .hasNext();) { |
| 94 | 25 | Vertex v2 = (Vertex) iterator.next(); |
| 95 | 25 | checkEquivalence(v1, v2, alreadyEquivalent, rv ); |
| 96 | } | |
| 97 | ||
| 98 | } | |
| 99 | } | |
| 100 | 6 | return rv; |
| 101 | } | |
| 102 | ||
| 103 | ||
| 104 | boolean checkEquivalence( Vertex v1, Vertex v2, Set alreadyEquivalent, Set rv ) { | |
| 105 | 43 | if (alreadyEquivalent.contains(v2)) |
| 106 | 5 | return false; |
| 107 | 38 | if (!canpossiblycompare(v1, v2)) |
| 108 | 0 | return false; |
| 109 | 38 | if (isStructurallyEquivalent(v1, v2)) { |
| 110 | 12 | Pair p = new Pair(v1, v2); |
| 111 | 12 | alreadyEquivalent.add(v2); |
| 112 | 12 | rv.add(p); |
| 113 | 12 | return true; |
| 114 | } | |
| 115 | 26 | return false; |
| 116 | } | |
| 117 | ||
| 118 | private Set getSecondNeighbors(Vertex v1) { | |
| 119 | 16 | Set secondNeighbors = new HashSet(); |
| 120 | 16 | for (Iterator iterator = v1.getNeighbors().iterator(); iterator |
| 121 | 55 | .hasNext();) { |
| 122 | 39 | Vertex intermediate = (Vertex) iterator.next(); |
| 123 | 39 | secondNeighbors.addAll(intermediate.getNeighbors()); |
| 124 | } | |
| 125 | 16 | return secondNeighbors; |
| 126 | } | |
| 127 | ||
| 128 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |