1
2
3
4
5
6
7
8
9
10
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
24
25
26
27
28
29
30
31
32
33
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
45
46
47
48 public static <V,E> DefaultParallelEdgeIndexFunction<V,E> getInstance() {
49 return new DefaultParallelEdgeIndexFunction<V,E>();
50 }
51
52
53
54
55
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
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
84 if(first.equals(second) == true) {
85 iterator.remove();
86 }
87
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
125
126
127
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
137
138
139 public void reset()
140 {
141 edge_index.clear();
142 }
143 }