001 package org.expasy.jpl.commons.collection.graph;
002
003
004 import java.util.Collection;
005 import edu.uci.ics.jung.graph.Graph;
006 import edu.uci.ics.jung.graph.util.Pair;
007
008
009 /**
010 * This object comes from jung. We had to rewrite it because of the original
011 * {@code createGraph()} method that internally create a new instance of {@code
012 * Graph} by reflexion that is not accessible and cannot be overridden. We had
013 * some problem while collapsing/expanding {@code KPartiteGraph} as constructor
014 * has no parameters whereas Predicate is really needed.
015 *
016 * <p>
017 * The object is now handling generic param
018 * </p>
019 *
020 * @author nikitin
021 *
022 * @version 1.0
023 *
024 */
025 public class GraphCollapser<V, E> {
026
027 protected Graph<V, E> originalGraph;
028
029 public GraphCollapser(Graph<V, E> originalGraph) {
030 this.originalGraph = originalGraph;
031 }
032
033 @SuppressWarnings("unchecked")
034 Graph<V, E> createGraph() throws InstantiationException,
035 IllegalAccessException {
036 Graph<V, E> g = (Graph) originalGraph.getClass().newInstance();
037
038 initGraph(g);
039
040 return g;
041 }
042
043 // to override in subclasses
044 public void initGraph(Graph<V, E> g) {}
045
046 @SuppressWarnings("unchecked")
047 public Graph<V, E> collapse(Graph<V, E> inGraph, Graph<V, E> clusterGraph) {
048
049 if (clusterGraph.getVertexCount() < 2)
050 return inGraph;
051
052 // the new collapsed graph
053 Graph<V, E> graph = inGraph;
054 try {
055 graph = createGraph();
056 } catch (Exception ex) {
057 ex.printStackTrace();
058 }
059 Collection<V> cluster = clusterGraph.getVertices();
060
061 // add all vertices in the delegate, unless the vertex found in the
062 // cluster.
063 for (V v : inGraph.getVertices()) {
064 if (cluster.contains(v) == false) {
065 graph.addVertex(v);
066 }
067 }
068
069 // add the clusterGraph as a vertex
070 graph.addVertex((V) clusterGraph);
071
072 // add all edges from the inGraph, unless both endpoints of
073 // the edge are in the cluster
074 for (E e : inGraph.getEdges()) {
075 Pair<V> endpoints = inGraph.getEndpoints(e);
076
077 boolean isOk = false;
078
079 // don't add edges whose endpoints are both in the cluster
080 if (cluster.containsAll(endpoints) == false) {
081
082 if (cluster.contains(endpoints.getFirst())) {
083 isOk =
084 graph.addEdge(e, (V) clusterGraph, endpoints
085 .getSecond(), inGraph.getEdgeType(e));
086 } else if (cluster.contains(endpoints.getSecond())) {
087 isOk =
088 graph.addEdge(e, endpoints.getFirst(),
089 (V) clusterGraph, inGraph.getEdgeType(e));
090 } else {
091 isOk =
092 graph.addEdge(e, endpoints.getFirst(), endpoints
093 .getSecond(), inGraph.getEdgeType(e));
094 }
095
096 if (!isOk) {
097 System.err.println("error when adding edge " + e);
098 }
099 }
100 }
101 return graph;
102 }
103
104 public Graph<V, E> expand(Graph<V, E> inGraph, Graph<V, E> clusterGraph) {
105 Graph<V, E> graph = inGraph;
106 try {
107 graph = createGraph();
108 } catch (Exception ex) {
109 ex.printStackTrace();
110 }
111 Collection<V> cluster = clusterGraph.getVertices();
112
113 // put all clusterGraph vertices and edges into the new Graph
114 for (V v : cluster) {
115 graph.addVertex(v);
116
117 for (E edge : clusterGraph.getIncidentEdges(v)) {
118 Pair<V> endpoints = clusterGraph.getEndpoints(edge);
119 graph.addEdge(edge, endpoints.getFirst(),
120 endpoints.getSecond(), clusterGraph.getEdgeType(edge));
121 }
122 }
123 // add all the vertices from the current graph except for
124 // the cluster we are expanding
125 for (V v : inGraph.getVertices()) {
126
127 if (v.equals(clusterGraph) == false) {
128 graph.addVertex(v);
129 }
130 }
131
132 // now that all vertices have been added, add the edges,
133 // ensuring that no edge contains a vertex that has not
134 // already been added
135 for (V v : inGraph.getVertices()) {
136 if (v.equals(clusterGraph) == false) {
137
138 for (E edge : inGraph.getIncidentEdges(v)) {
139 Pair<V> endpoints = inGraph.getEndpoints(edge);
140 V v1 = endpoints.getFirst();
141 V v2 = endpoints.getSecond();
142 if (cluster.containsAll(endpoints) == false) {
143
144 // v1 is the subgraph to expand
145 if (clusterGraph.equals(v1)) {
146
147 // i need a new v1
148 V originalV1 =
149 originalGraph.getEndpoints(edge).getFirst();
150
151 V newV1 = findVertex(graph, originalV1);
152
153 if (newV1 == null) {
154 throw new NullPointerException("newV1 for "
155 + originalV1 + " was not found!");
156 }
157 graph.addEdge(edge, newV1, v2, inGraph
158 .getEdgeType(edge));
159
160 } else if (clusterGraph.equals(v2)) {
161
162 // i need a new v2
163 V originalV2 =
164 originalGraph.getEndpoints(edge).getSecond();
165 V newV2 = findVertex(graph, originalV2);
166
167 if (newV2 == null) {
168 throw new NullPointerException(v1 + " --> "
169 + v2 + ": in edge " + edge + ", newV2 for "
170 + originalV2 + " was not found in "
171 + graph.toString() + "!");
172 }
173 graph.addEdge(edge, v1, newV2, inGraph
174 .getEdgeType(edge));
175
176 } else {
177 graph.addEdge(edge, v1, v2, inGraph
178 .getEdgeType(edge));
179 }
180 }
181 }
182 }
183 }
184 return graph;
185 }
186
187 @SuppressWarnings("unchecked")
188 V findVertex(Graph<V, E> inGraph, V vertex) {
189 Collection<V> vertices = inGraph.getVertices();
190 if (vertices.contains(vertex)) {
191 return vertex;
192 }
193 for (V v : vertices) {
194 if (v instanceof Graph) {
195 Graph<V, E> g = (Graph<V, E>) v;
196 if (contains(g, vertex)) {
197 return v;
198 }
199 }
200 }
201 return null;
202 }
203
204 @SuppressWarnings("unchecked")
205 private boolean contains(Graph<V, E> inGraph, V vertex) {
206 boolean contained = false;
207 if (inGraph.getVertices().contains(vertex))
208 return true;
209 for (V v : inGraph.getVertices()) {
210 if (v instanceof Graph) {
211 contained |= contains((Graph<V, E>) v, vertex);
212 }
213 }
214 return contained;
215 }
216
217 // get the sub graph
218 public Graph<V, E> getClusterGraph(Graph<V, E> inGraph,
219 Collection<? extends V> picked) {
220
221 Graph<V, E> clusterGraph;
222 try {
223 clusterGraph = createGraph();
224 } catch (InstantiationException e) {
225 // TODO Auto-generated catch block
226 e.printStackTrace();
227 return null;
228 } catch (IllegalAccessException e) {
229 // TODO Auto-generated catch block
230 e.printStackTrace();
231 return null;
232 }
233 for (V v : picked) {
234 clusterGraph.addVertex(v);
235 Collection<E> edges = inGraph.getIncidentEdges(v);
236 for (E edge : edges) {
237 Pair<V> endpoints = inGraph.getEndpoints(edge);
238 V v1 = endpoints.getFirst();
239 V v2 = endpoints.getSecond();
240 if (picked.containsAll(endpoints)) {
241 clusterGraph.addEdge(edge, v1, v2, inGraph
242 .getEdgeType(edge));
243 }
244 }
245 }
246 return clusterGraph;
247 }
248
249 }