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.Map;
18  
19  import edu.uci.ics.jung.graph.Graph;
20  
21  /**
22   * A class which creates and maintains indices for incident edges.
23   * 
24   * @author Tom Nelson
25   *
26   */
27  public class IncidentEdgeIndexFunction<V,E> implements EdgeIndexFunction<V,E>
28  {
29      protected Map<E, Integer> edge_index = new HashMap<E, Integer>();
30      
31      private IncidentEdgeIndexFunction() {
32      }
33      
34      /**
35       * Returns an instance of this type.
36       * @param <V> the vertex type
37       * @param <E> the edge type
38       */
39      public static <V,E> IncidentEdgeIndexFunction<V,E> getInstance() {
40          return new IncidentEdgeIndexFunction<V,E>();
41      }
42      
43      /**
44       * Returns the index for the specified edge.
45       * Calculates the indices for <code>e</code> and for all edges parallel
46       * to <code>e</code>.
47       */
48      public int getIndex(Graph<V,E> graph, E e)
49      {
50          Integer index = edge_index.get(e);
51          if(index == null) {
52          	Pair<V> endpoints = graph.getEndpoints(e);
53          	V u = endpoints.getFirst();
54          	V v = endpoints.getSecond();
55          	if(u.equals(v)) {
56          		index = getIndex(graph, e, v);
57          	} else {
58          		index = getIndex(graph, e, u, v);
59          	}
60          }
61          return index.intValue();
62      }
63  
64      protected int getIndex(Graph<V,E> graph, E e, V u, V v) {
65      	Collection<E> commonEdgeSet = new HashSet<E>(graph.getIncidentEdges(u));
66      	int count=0;
67      	for(E other : commonEdgeSet) {
68      		if(e.equals(other) == false) {
69      			edge_index.put(other, count);
70      			count++;
71      		}
72      	}
73      	edge_index.put(e, count);
74      	return count;
75       }
76      
77      protected int getIndex(Graph<V,E> graph, E e, V v) {
78      	Collection<E> commonEdgeSet = new HashSet<E>();
79      	for(E another : graph.getIncidentEdges(v)) {
80      		V u = graph.getOpposite(v, another);
81      		if(u.equals(v)) {
82      			commonEdgeSet.add(another);
83      		}
84      	}
85      	int count=0;
86      	for(E other : commonEdgeSet) {
87      		if(e.equals(other) == false) {
88      			edge_index.put(other, count);
89      			count++;
90      		}
91      	}
92      	edge_index.put(e, count);
93      	return count;
94      }
95  
96      
97      /**
98       * Resets the indices for this edge and its parallel edges.
99       * Should be invoked when an edge parallel to <code>e</code>
100      * has been added or removed.
101      * @param e
102      */
103     public void reset(Graph<V,E> graph, E e) {
104     	Pair<V> endpoints = graph.getEndpoints(e);
105         getIndex(graph, e, endpoints.getFirst());
106         getIndex(graph, e, endpoints.getFirst(), endpoints.getSecond());
107     }
108     
109     /**
110      * Clears all edge indices for all edges in all graphs.
111      * Does not recalculate the indices.
112      */
113     public void reset()
114     {
115         edge_index.clear();
116     }
117 }