third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java

   1 /*
   2  * Copyright (c) 2004, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  * Created on Jan 28, 2004
   6  *
   7  * This software is open-source under the BSD license; see either
   8  * "license.txt" or
   9  * http://jung.sourceforge.net/license.txt for a description.
  10  */
  11 package edu.uci.ics.jung.algorithms.blockmodel;
  12
  13 import java.util.ArrayList;
  14 import java.util.Collection;
  15 import java.util.Collections;
  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 org.apache.commons.collections15.CollectionUtils;
  24 import org.apache.commons.collections15.Transformer;
  25
  26 import edu.uci.ics.jung.graph.Graph;
  27 import edu.uci.ics.jung.graph.util.Pair;
  28
  29 /**
  30  * Identifies sets of structurally equivalent vertices in a graph. Vertices <i>
  31  * i</i> and <i>j</i> are structurally equivalent iff the set of <i>i</i>'s
  32  * neighbors is identical to the set of <i>j</i>'s neighbors, with the
  33  * exception of <i>i</i> and <i>j</i> themselves. This algorithm finds all
  34  * sets of equivalent vertices in O(V^2) time.
  35  *
  36  * <p>You can extend this class to have a different definition of equivalence (by
  37  * overriding <code>isStructurallyEquivalent</code>), and may give it hints for
  38  * accelerating the process by overriding <code>canPossiblyCompare</code>.
  39  * (For example, in a bipartite graph, <code>canPossiblyCompare</code> may
  40  * return <code>false</code> for vertices in
  41  * different partitions. This function should be fast.)
  42  *
  43  * @author Danyel Fisher
  44  */
  45 public class StructurallyEquivalent<V,E> implements Transformer<Graph<V,E>, VertexPartition<V,E>>
  46 {
  47         public VertexPartition<V,E> transform(Graph<V,E> g)
  48         {
  49             Set<Pair<V>> vertex_pairs = getEquivalentPairs(g);
  50
  51             Set<Set<V>> rv = new HashSet<Set<V>>();
  52         Map<V, Set<V>> intermediate = new HashMap<V, Set<V>>();
  53         for (Pair<V> p : vertex_pairs)
  54         {
  55             Set<V> res = intermediate.get(p.getFirst());
  56             if (res == null)
  57                 res = intermediate.get(p.getSecond());
  58             if (res == null)  // we haven't seen this one before
  59                 res = new HashSet<V>();
  60             res.add(p.getFirst());
  61             res.add(p.getSecond());
  62             intermediate.put(p.getFirst(), res);
  63             intermediate.put(p.getSecond(), res);
  64         }
  65         rv.addAll(intermediate.values());
  66
  67         // pick up the vertices which don't appear in intermediate; they are
  68         // singletons (equivalence classes of size 1)
  69         Collection<V> singletons = CollectionUtils.subtract(g.getVertices(),
  70                 intermediate.keySet());
  71         for (V v : singletons)
  72         {
  73             Set<V> v_set = Collections.singleton(v);
  74             intermediate.put(v, v_set);
  75             rv.add(v_set);
  76         }
  77
  78         return new VertexPartition<V, E>(g, intermediate, rv);
  79         }
  80
  81         /**
  82          * For each vertex pair v, v1 in G, checks whether v and v1 are fully
  83          * equivalent: meaning that they connect to the exact same vertices. (Is
  84          * this regular equivalence, or whathaveyou?)
  85          *
  86          * Returns a Set of Pairs of vertices, where all the vertices in the inner
  87          * Pairs are equivalent.
  88          *
  89          * @param g
  90          */
  91         protected Set<Pair<V>> getEquivalentPairs(Graph<V,?> g) {
  92
  93                 Set<Pair<V>> rv = new HashSet<Pair<V>>();
  94                 Set<V> alreadyEquivalent = new HashSet<V>();
  95
  96                 List<V> l = new ArrayList<V>(g.getVertices());
  97
  98                 for (V v1 : l)
  99                 {
 100                         if (alreadyEquivalent.contains(v1))
 101                                 continue;
 102
 103                         for (Iterator<V> iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) {
 104                             V v2 = iterator.next();
 105
 106                                 if (alreadyEquivalent.contains(v2))
 107                                         continue;
 108
 109                                 if (!canPossiblyCompare(v1, v2))
 110                                         continue;
 111
 112                                 if (isStructurallyEquivalent(g, v1, v2)) {
 113                                         Pair<V> p = new Pair<V>(v1, v2);
 114                                         alreadyEquivalent.add(v2);
 115                                         rv.add(p);
 116                                 }
 117                         }
 118                 }
 119
 120                 return rv;
 121         }
 122
 123         /**
 124          * Checks whether a pair of vertices are structurally equivalent.
 125          * Specifically, whether v1's predecessors are equal to v2's predecessors,
 126          * and same for successors.
 127          *
 128          * @param g the graph in which the structural equivalence comparison is to take place
 129          * @param v1 the vertex to check for structural equivalence to v2
 130          * @param v2 the vertex to check for structural equivalence to v1
 131          */
 132         protected boolean isStructurallyEquivalent(Graph<V,?> g, V v1, V v2) {
 133
 134                 if( g.degree(v1) != g.degree(v2)) {
 135                         return false;
 136                 }
 137
 138                 Set<V> n1 = new HashSet<V>(g.getPredecessors(v1));
 139                 n1.remove(v2);
 140                 n1.remove(v1);
 141                 Set<V> n2 = new HashSet<V>(g.getPredecessors(v2));
 142                 n2.remove(v1);
 143                 n2.remove(v2);
 144
 145                 Set<V> o1 = new HashSet<V>(g.getSuccessors(v1));
 146                 Set<V> o2 = new HashSet<V>(g.getSuccessors(v2));
 147                 o1.remove(v1);
 148                 o1.remove(v2);
 149                 o2.remove(v1);
 150                 o2.remove(v2);
 151
 152                 // this neglects self-loops and directed edges from 1 to other
 153                 boolean b = (n1.equals(n2) && o1.equals(o2));
 154                 if (!b)
 155                         return b;
 156
 157                 // if there's a directed edge v1->v2 then there's a directed edge v2->v1
 158                 b &= ( g.isSuccessor(v1, v2) == g.isSuccessor(v2, v1));
 159
 160                 // self-loop check
 161                 b &= ( g.isSuccessor(v1, v1) == g.isSuccessor(v2, v2));
 162
 163                 return b;
 164
 165         }
 166
 167         /**
 168          * This is a space for optimizations. For example, for a bipartite graph,
 169          * vertices from different partitions cannot possibly be compared.
 170          *
 171          * @param v1
 172          * @param v2
 173          */
 174         protected boolean canPossiblyCompare(V v1, V v2) {
 175                 return true;
 176         }
 177
 178 }