View Javadoc

1   /*
2    * Created on Sep 24, 2005
3    *
4    * Copyright (c) 2005, the JUNG Project and the Regents of the University 
5    * of California
6    * All rights reserved.
7    *
8    * This software is open-source under the BSD license; see either
9    * "license.txt" or
10   * http://jung.sourceforge.net/license.txt for a description.
11   */
12  package edu.uci.ics.jung.graph.util;
13  
14  import java.util.Collection;
15  import java.util.HashMap;
16  import java.util.HashSet;
17  import java.util.Iterator;
18  import java.util.Map;
19  
20  import edu.uci.ics.jung.graph.Graph;
21  
22  /**
23   * A class which creates and maintains indices for parallel edges.
24   * Parallel edges are defined here to be the collection of edges 
25   * that are returned by <code>v.findEdgeSet(w)</code> for some 
26   * <code>v</code> and <code>w</code>.
27   * 
28   * <p>At this time, users are responsible for resetting the indices 
29   * (by calling <code>reset()</code>) if changes to the
30   * graph make it appropriate.</p>
31   * 
32   * @author Joshua O'Madadhain
33   * @author Tom Nelson
34   *
35   */
36  public class DefaultParallelEdgeIndexFunction<V,E> implements EdgeIndexFunction<V,E>
37  {
38      protected Map<Context<Graph<V,E>,E>, Integer> edge_index = new HashMap<Context<Graph<V,E>,E>, Integer>();
39      
40      private DefaultParallelEdgeIndexFunction() {
41      }
42      
43      /**
44       * Returns an instance of this class.
45       * @param <V> the vertex type
46       * @param <E> the edge type
47       */
48      public static <V,E> DefaultParallelEdgeIndexFunction<V,E> getInstance() {
49          return new DefaultParallelEdgeIndexFunction<V,E>();
50      }
51      
52      /**
53       * Returns the index for <code>e</code> in <code>graph</code>.
54       * Calculates the indices for <code>e</code> and for all edges parallel
55       * to <code>e</code>, if they are not already assigned.
56       */
57      public int getIndex(Graph<V,E> graph, E e)
58      {
59      	
60          Integer index = edge_index.get(Context.<Graph<V,E>,E>getInstance(graph,e));
61          	//edge_index.get(e);
62          if(index == null) {
63          	Pair<V> endpoints = graph.getEndpoints(e);
64          	V u = endpoints.getFirst();
65          	V v = endpoints.getSecond();
66          	if(u.equals(v)) {
67          		index = getIndex(graph, e, v);
68          	} else {
69          		index = getIndex(graph, e, u, v);
70          	}
71          }
72          return index.intValue();
73      }
74  
75      protected int getIndex(Graph<V,E> graph, E e, V v, V u) {
76      	Collection<E> commonEdgeSet = new HashSet<E>(graph.getIncidentEdges(u));
77      	commonEdgeSet.retainAll(graph.getIncidentEdges(v));
78      	for(Iterator<E> iterator=commonEdgeSet.iterator(); iterator.hasNext(); ) {
79      		E edge = iterator.next();
80      		Pair<V> ep = graph.getEndpoints(edge);
81      		V first = ep.getFirst();
82      		V second = ep.getSecond();
83      		// remove loops
84      		if(first.equals(second) == true) {
85      			iterator.remove();
86      		}
87      		// remove edges in opposite direction
88      		if(first.equals(v) == false) {
89      			iterator.remove();
90      		}
91      	}
92      	int count=0;
93      	for(E other : commonEdgeSet) {
94      		if(e.equals(other) == false) {
95      			edge_index.put(Context.<Graph<V,E>,E>getInstance(graph,other), count);
96      			count++;
97      		}
98      	}
99      	edge_index.put(Context.<Graph<V,E>,E>getInstance(graph,e), count);
100     	return count;
101      }
102     
103     protected int getIndex(Graph<V,E> graph, E e, V v) {
104     	Collection<E> commonEdgeSet = new HashSet<E>();
105     	for(E another : graph.getIncidentEdges(v)) {
106     		V u = graph.getOpposite(v, another);
107     		if(u.equals(v)) {
108     			commonEdgeSet.add(another);
109     		}
110     	}
111     	int count=0;
112     	for(E other : commonEdgeSet) {
113     		if(e.equals(other) == false) {
114     			edge_index.put(Context.<Graph<V,E>,E>getInstance(graph,other), count);
115     			count++;
116     		}
117     	}
118     	edge_index.put(Context.<Graph<V,E>,E>getInstance(graph,e), count);
119     	return count;
120     }
121 
122     
123     /**
124      * Resets the indices for this edge and its parallel edges.
125      * Should be invoked when an edge parallel to <code>e</code>
126      * has been added or removed.
127      * @param e
128      */
129     public void reset(Graph<V,E> graph, E e) {
130     	Pair<V> endpoints = graph.getEndpoints(e);
131         getIndex(graph, e, endpoints.getFirst());
132         getIndex(graph, e, endpoints.getFirst(), endpoints.getSecond());
133     }
134     
135     /**
136      * Clears all edge indices for all edges in all graphs.
137      * Does not recalculate the indices.
138      */
139     public void reset()
140     {
141         edge_index.clear();
142     }
143 }