/*
 * 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.