+++ /dev/null
-/*
- * Copyright (c) 2004, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- * Created on Jan 28, 2004
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.blockmodel;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.CollectionUtils;
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * Identifies sets of structurally equivalent vertices in a graph. Vertices <i>
- * i</i> and <i>j</i> are structurally equivalent iff the set of <i>i</i>'s
- * neighbors is identical to the set of <i>j</i>'s neighbors, with the
- * exception of <i>i</i> and <i>j</i> themselves. This algorithm finds all
- * sets of equivalent vertices in O(V^2) time.
- *
- * <p>You can extend this class to have a different definition of equivalence (by
- * overriding <code>isStructurallyEquivalent</code>), and may give it hints for
- * accelerating the process by overriding <code>canPossiblyCompare</code>.
- * (For example, in a bipartite graph, <code>canPossiblyCompare</code> may
- * return <code>false</code> for vertices in
- * different partitions. This function should be fast.)
- *
- * @author Danyel Fisher
- */
-public class StructurallyEquivalent<V,E> implements Transformer<Graph<V,E>, VertexPartition<V,E>>
-{
- public VertexPartition<V,E> transform(Graph<V,E> g)
- {
- Set<Pair<V>> vertex_pairs = getEquivalentPairs(g);
-
- Set<Set<V>> rv = new HashSet<Set<V>>();
- Map<V, Set<V>> intermediate = new HashMap<V, Set<V>>();
- for (Pair<V> p : vertex_pairs)
- {
- Set<V> res = intermediate.get(p.getFirst());
- if (res == null)
- res = intermediate.get(p.getSecond());
- if (res == null) // we haven't seen this one before
- res = new HashSet<V>();
- res.add(p.getFirst());
- res.add(p.getSecond());
- intermediate.put(p.getFirst(), res);
- intermediate.put(p.getSecond(), res);
- }
- rv.addAll(intermediate.values());
-
- // pick up the vertices which don't appear in intermediate; they are
- // singletons (equivalence classes of size 1)
- Collection<V> singletons = CollectionUtils.subtract(g.getVertices(),
- intermediate.keySet());
- for (V v : singletons)
- {
- Set<V> v_set = Collections.singleton(v);
- intermediate.put(v, v_set);
- rv.add(v_set);
- }
-
- return new VertexPartition<V, E>(g, intermediate, rv);
- }
-
- /**
- * For each vertex pair v, v1 in G, checks whether v and v1 are fully
- * equivalent: meaning that they connect to the exact same vertices. (Is
- * this regular equivalence, or whathaveyou?)
- *
- * Returns a Set of Pairs of vertices, where all the vertices in the inner
- * Pairs are equivalent.
- *
- * @param g
- */
- protected Set<Pair<V>> getEquivalentPairs(Graph<V,?> g) {
-
- Set<Pair<V>> rv = new HashSet<Pair<V>>();
- Set<V> alreadyEquivalent = new HashSet<V>();
-
- List<V> l = new ArrayList<V>(g.getVertices());
-
- for (V v1 : l)
- {
- if (alreadyEquivalent.contains(v1))
- continue;
-
- for (Iterator<V> iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) {
- V v2 = iterator.next();
-
- if (alreadyEquivalent.contains(v2))
- continue;
-
- if (!canPossiblyCompare(v1, v2))
- continue;
-
- if (isStructurallyEquivalent(g, v1, v2)) {
- Pair<V> p = new Pair<V>(v1, v2);
- alreadyEquivalent.add(v2);
- rv.add(p);
- }
- }
- }
-
- return rv;
- }
-
- /**
- * Checks whether a pair of vertices are structurally equivalent.
- * Specifically, whether v1's predecessors are equal to v2's predecessors,
- * and same for successors.
- *
- * @param g the graph in which the structural equivalence comparison is to take place
- * @param v1 the vertex to check for structural equivalence to v2
- * @param v2 the vertex to check for structural equivalence to v1
- */
- protected boolean isStructurallyEquivalent(Graph<V,?> g, V v1, V v2) {
-
- if( g.degree(v1) != g.degree(v2)) {
- return false;
- }
-
- Set<V> n1 = new HashSet<V>(g.getPredecessors(v1));
- n1.remove(v2);
- n1.remove(v1);
- Set<V> n2 = new HashSet<V>(g.getPredecessors(v2));
- n2.remove(v1);
- n2.remove(v2);
-
- Set<V> o1 = new HashSet<V>(g.getSuccessors(v1));
- Set<V> o2 = new HashSet<V>(g.getSuccessors(v2));
- o1.remove(v1);
- o1.remove(v2);
- o2.remove(v1);
- o2.remove(v2);
-
- // this neglects self-loops and directed edges from 1 to other
- boolean b = (n1.equals(n2) && o1.equals(o2));
- if (!b)
- return b;
-
- // if there's a directed edge v1->v2 then there's a directed edge v2->v1
- b &= ( g.isSuccessor(v1, v2) == g.isSuccessor(v2, v1));
-
- // self-loop check
- b &= ( g.isSuccessor(v1, v1) == g.isSuccessor(v2, v2));
-
- return b;
-
- }
-
- /**
- * This is a space for optimizations. For example, for a bipartite graph,
- * vertices from different partitions cannot possibly be compared.
- *
- * @param v1
- * @param v2
- */
- protected boolean canPossiblyCompare(V v1, V v2) {
- return true;
- }
-
-}
Code Review / controller.git / blobdiff