/*
* Created on Sep 24, 2005
*
* Copyright (c) 2005, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.graph.util;
import static com.google.common.base.Preconditions.checkNotNull;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import edu.uci.ics.jung.graph.Graph;
/**
* A class which creates and maintains indices for parallel edges.
* Parallel edges are defined here to be the collection of edges
* that are returned by v.findEdgeSet(w) for some
* v and w.
*
* At this time, users are responsible for resetting the indices
* (by calling reset()) if changes to the
* graph make it appropriate.
*
* @author Joshua O'Madadhain
* @author Tom Nelson
*
*/
public class DefaultParallelEdgeIndexFunction implements EdgeIndexFunction
{
protected Map,E>, Integer> edge_index = new HashMap,E>, Integer>();
private DefaultParallelEdgeIndexFunction() {
}
/**
* @param the vertex type
* @param the edge type
* @return an instance of this class
*/
public static DefaultParallelEdgeIndexFunction getInstance() {
return new DefaultParallelEdgeIndexFunction();
}
/**
* Returns the index for e in graph.
* Calculates the indices for e and for all edges parallel
* to e, if they are not already assigned.
*/
public int getIndex(Graph graph, E e)
{
checkNotNull(graph, "graph must not be null");
checkNotNull(e, "'e' must not be null");
Integer index = edge_index.get(Context.,E>getInstance(graph,e));
//edge_index.get(e);
if(index == null) {
Pair endpoints = graph.getEndpoints(e);
V u = endpoints.getFirst();
V v = endpoints.getSecond();
if(u.equals(v)) {
index = getIndex(graph, e, v);
} else {
index = getIndex(graph, e, u, v);
}
}
return index.intValue();
}
protected int getIndex(Graph graph, E e, V v, V u) {
Collection commonEdgeSet = new HashSet(graph.getIncidentEdges(u));
commonEdgeSet.retainAll(graph.getIncidentEdges(v));
for(Iterator iterator=commonEdgeSet.iterator(); iterator.hasNext(); ) {
E edge = iterator.next();
Pair ep = graph.getEndpoints(edge);
V first = ep.getFirst();
V second = ep.getSecond();
// remove loops
if(first.equals(second) == true) {
iterator.remove();
}
// remove edges in opposite direction
if(first.equals(v) == false) {
iterator.remove();
}
}
int count=0;
for(E other : commonEdgeSet) {
if(e.equals(other) == false) {
edge_index.put(Context.,E>getInstance(graph,other), count);
count++;
}
}
edge_index.put(Context.,E>getInstance(graph,e), count);
return count;
}
protected int getIndex(Graph graph, E e, V v) {
Collection commonEdgeSet = new HashSet();
for(E another : graph.getIncidentEdges(v)) {
V u = graph.getOpposite(v, another);
if(u.equals(v)) {
commonEdgeSet.add(another);
}
}
int count=0;
for(E other : commonEdgeSet) {
if(e.equals(other) == false) {
edge_index.put(Context.,E>getInstance(graph,other), count);
count++;
}
}
edge_index.put(Context.,E>getInstance(graph,e), count);
return count;
}
/**
* Resets the indices for this edge and its parallel edges.
* Should be invoked when an edge parallel to e
* has been added or removed.
* @param graph the graph for which the indices are to be reset
* @param e the edge whose indices are to be reset
*
*/
public void reset(Graph graph, E e) {
Pair endpoints = graph.getEndpoints(e);
getIndex(graph, e, endpoints.getFirst());
getIndex(graph, e, endpoints.getFirst(), endpoints.getSecond());
}
/**
* Clears all edge indices for all edges in all graphs.
* Does not recalculate the indices.
*/
public void reset()
{
edge_index.clear();
}
}
Ads help maintain this website.