001 /**
002 *
003 */
004 package edu.wwu.tobikley.acgc.graphcoloring;
005
006 import java.util.Collection;
007 import java.util.HashMap;
008 import java.util.Iterator;
009 import java.util.Set;
010
011 import edu.uci.ics.jung.graph.ArchetypeGraph;
012 import edu.uci.ics.jung.graph.Edge;
013 import edu.uci.ics.jung.graph.Graph;
014 import edu.uci.ics.jung.graph.Vertex;
015 import edu.uci.ics.jung.graph.event.GraphEventListener;
016 import edu.uci.ics.jung.graph.event.GraphEventType;
017 import edu.uci.ics.jung.utils.UserDataContainer;
018
019 /**
020 * Extends any <code>Graph</code>-Implementation with a node- and an edge-coloring.
021 *
022 * @version 1.0
023 * @author Tobias Kley
024 */
025 public class ColoredGraph implements Graph {
026
027 /** Graph object all method calls are delegated to. */
028 protected Graph graph = null;
029
030 /** Mapping the graphs vertices to Integer ids. */
031 protected HashMap<Vertex,Integer> vertexIds = null;
032
033 /** Mapping the graphs edges to Integer ids. */
034 protected HashMap<Edge,Integer> edgeIds = null;
035
036 /** Mapping the vertice ids to the corresponding vertices. */
037 protected HashMap<Integer,Vertex> verticesById = null;
038
039 /** Mapping the edge ids to the corresponding edges. */
040 protected HashMap<Integer,Edge> edgesById = null;
041
042 /** The current vertex coloring. */
043 protected int[] vertexColoring = null;
044
045 /** The current edge coloring. */
046 protected int[] edgeColoring = null;
047
048 /**
049 * Creates a new instance of a colored graph.
050 * A copy of the given graph will be create and extended with the
051 * coloring properties.
052 *
053 * @param g Master graph to create a colored copy from.
054 */
055 public ColoredGraph(Graph g) {
056
057 this.graph = (Graph)g.copy();
058
059 // Initialize colors
060 vertexColoring = new int[graph.numVertices()];
061 edgeColoring = new int[graph.numEdges()];
062
063 Integer i;
064 // Add Vertice-Metadata
065 vertexIds = new HashMap<Vertex,Integer>(graph.numVertices());
066 verticesById = new HashMap<Integer,Vertex>(graph.numVertices());
067 i = 1;
068 Iterator verticeIterator = graph.getVertices().iterator();
069 while (verticeIterator.hasNext()) {
070 Vertex v = (Vertex)verticeIterator.next();
071 vertexIds.put(v,i);
072 verticesById.put(i,v);
073 i++;
074 }
075
076 // Add Edge-Metadata
077 edgeIds = new HashMap<Edge,Integer>(graph.numEdges());
078 edgesById = new HashMap<Integer,Edge>(graph.numEdges());
079 i = 1;
080 Iterator edgeIterator = graph.getEdges().iterator();
081 while (edgeIterator.hasNext()) {
082 Edge e = (Edge)edgeIterator.next();
083 edgeIds.put(e,i);
084 edgesById.put(i,e);
085 i++;
086 }
087 }
088
089 /**
090 * Returns the edge that corresponds to the given id.
091 *
092 * @param id Edge identifier.
093 * @return Edge by identifier id.
094 */
095 public Edge getEdge(int id) {
096 return edgesById.get(id);
097 }
098
099 /**
100 * Returns the vertex that corresponds to the given id.
101 *
102 * @param id Vertex identifier.
103 * @return Vertex by identifier id.
104 */
105 public Vertex getVertex(int id) {
106 return verticesById.get(id);
107 }
108
109 /**
110 * Returns the edge's identifier.
111 *
112 * @param edge Edge.
113 * @return Identifier of edge.
114 */
115 public int getEdgeId(Edge edge) {
116 return edgeIds.get(edge);
117 }
118
119 /**
120 * Returns the vertex's identifier.
121 *
122 * @param vertex Vertex.
123 * @return Identifier of vertex.
124 */
125 public int getVertexId(Vertex vertex) {
126 return vertexIds.get(vertex);
127 }
128
129 /**
130 * Returns the color of a vertex.
131 *
132 * @param vertex Vertex.
133 * @return Color of vertex.
134 */
135 public int getColor(Vertex vertex) {
136 return vertexColoring[getVertexId(vertex)-1];
137 }
138
139 /**
140 * Returns the color of an edge.
141 *
142 * @param edge Edge.
143 * @return Color of edge.
144 */
145 public int getColor(Edge edge) {
146 return edgeColoring[getEdgeId(edge)-1];
147 }
148
149 /**
150 * Returns the color of a vertex by its identifier.
151 *
152 * @param id Vertex's identifier.
153 * @return Color of vertex.
154 */
155 public int getVertexColor(int id) {
156 return vertexColoring[id-1];
157 }
158
159 /**
160 * Returns the color of an edge by its identifier.
161 *
162 * @param id Edge's identifier.
163 * @return Color of vertex.
164 */
165 public int getEdgeColor(int id) {
166 return edgeColoring[id-1];
167 }
168
169 /**
170 * Sets the color of a vertex.
171 *
172 * @param vertex Vertex.
173 * @param color Color to set.
174 */
175 public void setColor(Vertex vertex, int color) {
176 vertexColoring[getVertexId(vertex)-1] = color;
177 }
178
179 /**
180 * Sets the color of an edge.
181 *
182 * @param edge Edge.
183 * @param color Color to set.
184 */
185 public void setColor(Edge edge, int color) {
186 edgeColoring[getEdgeId(edge)-1] = color;
187 }
188
189 /**
190 * Sets the color of a vertex by its identifier.
191 *
192 * @param id Vertex's identifier.
193 * @param color Color to set.
194 */
195 public void setVertexColor(int id, int color) {
196 vertexColoring[id-1] = color;
197 }
198
199 /**
200 * Sets the color of an edge by its identifier.
201 *
202 * @param id Edge's identifier.
203 * @param color Color to set.
204 */
205 public void setEdgeColor(int id, int color) {
206 edgeColoring[id-1] = color;
207 }
208
209 /**
210 * Determines if the current vertex coloring is proper.
211 * To determine if it is a proper colorings, each edge in the graph is
212 * examined. A coloring is proper if the endnodes of all edges are of
213 * different colors.
214 *
215 * @return <code>true</code> if the current vertex coloring is proper, and
216 * <code>false</code> if it is not.
217 */
218 public boolean isProperVertexColoring() {
219 boolean result = true;
220 Iterator edgeIterator = graph.getEdges().iterator();
221 while (edgeIterator.hasNext()) {
222 Edge e = (Edge)edgeIterator.next();
223 int c1 = getColor((Vertex)e.getEndpoints().getFirst());
224 int c2 = getColor((Vertex)e.getEndpoints().getSecond());
225 if (c1 == c2) {
226 result = false;
227 }
228 }
229 return result;
230 }
231
232 /**
233 * Determines the maximum degree of the graph and returns it.
234 *
235 * @return Maximum degree of the graph.
236 */
237 public int getMaxDegree() {
238 int returnVal = 0;
239 Iterator verticeIterator = graph.getVertices().iterator();
240 while (verticeIterator.hasNext()) {
241 Vertex v = (Vertex)verticeIterator.next();
242 if(v.degree() > returnVal) {
243 returnVal = v.degree();
244 }
245 }
246 return returnVal;
247 }
248 /**
249 * Determines if the graph is Delta-regular.
250 *
251 * @return <code>true</code> if the graph is regular, and
252 * <code>false</code> if it is not.
253 */
254 public boolean isRegular() {
255 boolean returnVal = true;
256 int maxDegree = getMaxDegree();
257 Iterator verticeIterator = graph.getVertices().iterator();
258 while (verticeIterator.hasNext()) {
259 Vertex v = (Vertex)verticeIterator.next();
260 if(v.degree() != maxDegree) {
261 returnVal = false;
262 }
263 }
264 return returnVal;
265 }
266
267 /**
268 * @return the graph
269 */
270 public Graph getGraph() {
271 return graph;
272 }
273
274 /**
275 * @return the edgeColoring
276 */
277 public int[] getEdgeColoring() {
278 return edgeColoring;
279 }
280
281 /**
282 * @param edgeColoring the edgeColoring to set
283 */
284 public void setEdgeColoring(int[] edgeColoring) {
285 this.edgeColoring = edgeColoring;
286 }
287
288 /**
289 * @return the vertexColoring
290 */
291 public int[] getVertexColoring() {
292 return vertexColoring;
293 }
294
295 /**
296 * @param vertexColoring the vertexColoring to set
297 */
298 public void setVertexColoring(int[] vertexColoring) {
299 this.vertexColoring = vertexColoring;
300 }
301
302
303 // Delegates to graph
304
305 /**
306 * @param e
307 * @return the edge
308 * @see edu.uci.ics.jung.graph.Graph#addEdge(edu.uci.ics.jung.graph.Edge)
309 */
310 public Edge addEdge(Edge e) {
311 return graph.addEdge(e);
312 }
313
314 /**
315 * @param gel
316 * @param get
317 * @see edu.uci.ics.jung.graph.ArchetypeGraph#addListener(edu.uci.ics.jung.graph.event.GraphEventListener, edu.uci.ics.jung.graph.event.GraphEventType)
318 */
319 public void addListener(GraphEventListener gel, GraphEventType get) {
320 graph.addListener(gel, get);
321 }
322
323 /**
324 * @param key
325 * @param datum
326 * @param copyAct
327 * @see edu.uci.ics.jung.utils.UserDataContainer#addUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction)
328 */
329 public void addUserDatum(Object key, Object datum, CopyAction copyAct) {
330 graph.addUserDatum(key, datum, copyAct);
331 }
332
333 /**
334 * @param v
335 * @return the vertex
336 * @see edu.uci.ics.jung.graph.Graph#addVertex(edu.uci.ics.jung.graph.Vertex)
337 */
338 public Vertex addVertex(Vertex v) {
339 return graph.addVertex(v);
340 }
341
342 /**
343 * @return the object
344 * @throws CloneNotSupportedException
345 * @see edu.uci.ics.jung.utils.UserDataContainer#clone()
346 */
347 public Object clone() throws CloneNotSupportedException {
348 return graph.clone();
349 }
350
351 /**
352 * @param key
353 * @return ???
354 * @see edu.uci.ics.jung.utils.UserDataContainer#containsUserDatumKey(java.lang.Object)
355 */
356 public boolean containsUserDatumKey(Object key) {
357 return graph.containsUserDatumKey(key);
358 }
359
360 /**
361 * @return copy of the graph
362 * @see edu.uci.ics.jung.graph.ArchetypeGraph#copy()
363 */
364 public ColoredGraph copy() {
365 return new ColoredGraph(this);
366 }
367
368 /**
369 * @return the edge constraints
370 * @see edu.uci.ics.jung.graph.ArchetypeGraph#getEdgeConstraints()
371 */
372 public Collection getEdgeConstraints() {
373 return graph.getEdgeConstraints();
374 }
375
376 /**
377 * @return the set of edges
378 * @see edu.uci.ics.jung.graph.ArchetypeGraph#getEdges()
379 */
380 public Set getEdges() {
381 return graph.getEdges();
382 }
383
384 /**
385 * @param key
386 * @return the user datum
387 * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatum(java.lang.Object)
388 */
389 public Object getUserDatum(Object key) {
390 return graph.getUserDatum(key);
391 }
392
393 /**
394 * @param key
395 * @return the user datum copy action
396 * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatumCopyAction(java.lang.Object)
397 */
398 public CopyAction getUserDatumCopyAction(Object key) {
399 return graph.getUserDatumCopyAction(key);
400 }
401
402 /**
403 * @return the user datum key iterator
404 * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatumKeyIterator()
405 */
406 public Iterator getUserDatumKeyIterator() {
407 return graph.getUserDatumKeyIterator();
408 }
409
410 /**
411 * @return the vertex constraints
412 * @see edu.uci.ics.jung.graph.ArchetypeGraph#getVertexConstraints()
413 */
414 public Collection getVertexConstraints() {
415 return graph.getVertexConstraints();
416 }
417
418 /**
419 * @return the set of vertices
420 * @see edu.uci.ics.jung.graph.ArchetypeGraph#getVertices()
421 */
422 public Set getVertices() {
423 return graph.getVertices();
424 }
425
426 /**
427 * @param udc
428 * @see edu.uci.ics.jung.utils.UserDataContainer#importUserData(edu.uci.ics.jung.utils.UserDataContainer)
429 */
430 public void importUserData(UserDataContainer udc) {
431 graph.importUserData(udc);
432 }
433
434 /**
435 * @return true if it is directed
436 * @deprecated
437 * @see edu.uci.ics.jung.graph.Graph#isDirected()
438 */
439 public boolean isDirected() {
440 return graph.isDirected();
441 }
442
443 /**
444 * @return a new instance
445 * @see edu.uci.ics.jung.graph.ArchetypeGraph#newInstance()
446 */
447 public ArchetypeGraph newInstance() {
448 return graph.newInstance();
449 }
450
451 /**
452 * @return the number of edges
453 * @see edu.uci.ics.jung.graph.ArchetypeGraph#numEdges()
454 */
455 public int numEdges() {
456 return graph.numEdges();
457 }
458
459 /**
460 * @return the number of vertices
461 * @see edu.uci.ics.jung.graph.ArchetypeGraph#numVertices()
462 */
463 public int numVertices() {
464 return graph.numVertices();
465 }
466
467 /**
468 *
469 * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeAllEdges()
470 */
471 public void removeAllEdges() {
472 graph.removeAllEdges();
473 }
474
475 /**
476 *
477 * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeAllVertices()
478 */
479 public void removeAllVertices() {
480 graph.removeAllVertices();
481 }
482
483 /**
484 * @param e
485 * @see edu.uci.ics.jung.graph.Graph#removeEdge(edu.uci.ics.jung.graph.Edge)
486 */
487 public void removeEdge(Edge e) {
488 graph.removeEdge(e);
489 }
490
491 /**
492 * @param edges
493 * @deprecated
494 * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeEdges(java.util.Set)
495 */
496 public void removeEdges(Set edges) {
497 graph.removeEdges(edges);
498 }
499
500 /**
501 * @param gel
502 * @param get
503 * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeListener(edu.uci.ics.jung.graph.event.GraphEventListener, edu.uci.ics.jung.graph.event.GraphEventType)
504 */
505 public void removeListener(GraphEventListener gel, GraphEventType get) {
506 graph.removeListener(gel, get);
507 }
508
509 /**
510 * @param key
511 * @return the user datum removed (???)
512 * @see edu.uci.ics.jung.utils.UserDataContainer#removeUserDatum(java.lang.Object)
513 */
514 public Object removeUserDatum(Object key) {
515 return graph.removeUserDatum(key);
516 }
517
518 /**
519 * @param v
520 * @see edu.uci.ics.jung.graph.Graph#removeVertex(edu.uci.ics.jung.graph.Vertex)
521 */
522 public void removeVertex(Vertex v) {
523 graph.removeVertex(v);
524 }
525
526 /**
527 * @param vertices
528 * @deprecated
529 * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeVertices(java.util.Set)
530 */
531 public void removeVertices(Set vertices) {
532 graph.removeVertices(vertices);
533 }
534
535 /**
536 * @param key
537 * @param datum
538 * @param copyAct
539 * @see edu.uci.ics.jung.utils.UserDataContainer#setUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction)
540 */
541 public void setUserDatum(Object key, Object datum, CopyAction copyAct) {
542 graph.setUserDatum(key, datum, copyAct);
543 }
544
545 }