1
2
3
4
5
6
7
8
9
10
11
12 package edu.uci.ics.jung.graph;
13
14 import java.util.ArrayList;
15 import java.util.Collection;
16 import java.util.Collections;
17 import java.util.HashMap;
18 import java.util.List;
19 import java.util.Map;
20
21 import org.apache.commons.collections15.CollectionUtils;
22 import org.apache.commons.collections15.Factory;
23
24 import edu.uci.ics.jung.graph.util.EdgeType;
25 import edu.uci.ics.jung.graph.util.Pair;
26
27
28
29
30
31
32
33
34
35 @SuppressWarnings("serial")
36 public class OrderedKAryTree<V, E> extends AbstractTypedGraph<V, E> implements Tree<V, E>
37 {
38 protected Map<E, Pair<V>> edge_vpairs;
39 protected Map<V, VertexData> vertex_data;
40 protected int height;
41 protected V root;
42 protected int order;
43
44
45
46
47
48
49 public static <V,E> Factory<DirectedGraph<V,E>> getFactory(final int order) {
50 return new Factory<DirectedGraph<V,E>> () {
51 public DirectedGraph<V,E> create() {
52 return new OrderedKAryTree<V,E>(order);
53 }
54 };
55 }
56
57
58
59
60 public OrderedKAryTree(int order)
61 {
62 super(EdgeType.DIRECTED);
63 this.order = order;
64 this.height = -1;
65 this.edge_vpairs = new HashMap<E, Pair<V>>();
66 this.vertex_data = new HashMap<V, VertexData>();
67 }
68
69
70
71
72
73 public int getChildCount(V vertex) {
74 if (!containsVertex(vertex))
75 return 0;
76 List<E> edges = vertex_data.get(vertex).child_edges;
77 if (edges == null)
78 return 0;
79 int count = 0;
80 for (E edge : edges)
81 count += edge == null ? 0 : 1;
82
83 return count;
84 }
85
86
87
88
89
90
91
92 public E getChildEdge(V vertex, int index)
93 {
94 if (!containsVertex(vertex))
95 return null;
96 List<E> edges = vertex_data.get(vertex).child_edges;
97 if (edges == null)
98 return null;
99 return edges.get(index);
100 }
101
102
103
104
105 public Collection<E> getChildEdges(V vertex)
106 {
107 if (!containsVertex(vertex))
108 return null;
109 List<E> edges = vertex_data.get(vertex).child_edges;
110 return edges == null ? Collections.<E>emptySet() :
111 CollectionUtils.unmodifiableCollection(edges);
112 }
113
114
115
116
117
118
119
120
121 public Collection<V> getChildren(V vertex)
122 {
123 if (!containsVertex(vertex))
124 return null;
125 List<E> edges = vertex_data.get(vertex).child_edges;
126 if (edges == null)
127 return Collections.emptySet();
128 Collection<V> children = new ArrayList<V>(order);
129 for (E edge : edges)
130 children.add(this.getOpposite(vertex, edge));
131 return CollectionUtils.unmodifiableCollection(children);
132 }
133
134
135
136
137
138
139 public int getDepth(V vertex)
140 {
141 if (!containsVertex(vertex))
142 return -1;
143 return vertex_data.get(vertex).depth;
144 }
145
146
147
148
149
150 public int getHeight()
151 {
152 return height;
153 }
154
155
156
157
158 public V getParent(V vertex)
159 {
160 if (!containsVertex(vertex))
161 return null;
162 else if (vertex.equals(root))
163 return null;
164 return edge_vpairs.get(vertex_data.get(vertex).parent_edge).getFirst();
165 }
166
167
168
169
170 public E getParentEdge(V vertex)
171 {
172 if (!containsVertex(vertex))
173 return null;
174 return vertex_data.get(vertex).parent_edge;
175 }
176
177
178
179
180 public V getRoot()
181 {
182 return root;
183 }
184
185
186
187
188 public Collection<Tree<V, E>> getTrees()
189 {
190 Collection<Tree<V, E>> forest = new ArrayList<Tree<V, E>>(1);
191 forest.add(this);
192 return forest;
193 }
194
195
196
197
198
199
200
201
202
203
204
205 public boolean addEdge(E e, V parent, V child, int index)
206 {
207 if (e == null || child == null || parent == null)
208 throw new IllegalArgumentException("Inputs may not be null");
209 if (!containsVertex(parent))
210 throw new IllegalArgumentException("Tree must already " +
211 "include parent: " + parent);
212 if (containsVertex(child))
213 throw new IllegalArgumentException("Tree must not already " +
214 "include child: " + child);
215 if (parent.equals(child))
216 throw new IllegalArgumentException("Input vertices must be distinct");
217 if (index < 0 || index >= order)
218 throw new IllegalArgumentException("'index' must be in [0, [order-1]]");
219
220 Pair<V> endpoints = new Pair<V>(parent, child);
221 if (containsEdge(e))
222 if (!endpoints.equals(edge_vpairs.get(e)))
223 throw new IllegalArgumentException("Tree already includes edge" +
224 e + " with different endpoints " + edge_vpairs.get(e));
225 else
226 return false;
227
228 VertexData parent_data = vertex_data.get(parent);
229 List<E> outedges = parent_data.child_edges;
230
231 if (outedges == null)
232 outedges = new ArrayList<E>(this.order);
233
234 boolean edge_placed = false;
235 if (index >= 0)
236 if (outedges.get(index) != null)
237 throw new IllegalArgumentException("Parent " + parent +
238 " already has a child at index " + index + " in this tree");
239 else
240 outedges.set(index, e);
241 for (int i = 0; i < order; i++)
242 {
243 if (outedges.get(i) == null)
244 {
245 outedges.set(i, e);
246 edge_placed = true;
247 break;
248 }
249 }
250 if (!edge_placed)
251 throw new IllegalArgumentException("Parent " + parent + " already" +
252 " has " + order + " children in this tree");
253
254
255 VertexData child_data = new VertexData(e, parent_data.depth + 1);
256 vertex_data.put(child, child_data);
257
258 height = child_data.depth > height ? child_data.depth : height;
259 edge_vpairs.put(e, endpoints);
260
261 return true;
262 }
263
264
265
266
267 @Override
268 public boolean addEdge(E e, V parent, V child)
269 {
270 return addEdge(e, parent, child, -1);
271 }
272
273
274
275
276
277 @Override
278 public boolean addEdge(E e, V v1, V v2, EdgeType edge_type)
279 {
280 this.validateEdgeType(edge_type);
281 return addEdge(e, v1, v2);
282 }
283
284
285
286
287 public V getDest(E directed_edge)
288 {
289 if (!containsEdge(directed_edge))
290 return null;
291 return edge_vpairs.get(directed_edge).getSecond();
292 }
293
294
295
296
297 public Pair<V> getEndpoints(E edge)
298 {
299 if (!containsEdge(edge))
300 return null;
301 return edge_vpairs.get(edge);
302 }
303
304
305
306
307 public Collection<E> getInEdges(V vertex)
308 {
309 if (!containsVertex(vertex))
310 return null;
311 else if (vertex.equals(root))
312 return Collections.emptySet();
313 else
314 return Collections.singleton(getParentEdge(vertex));
315 }
316
317
318
319
320 @Override
321 public V getOpposite(V vertex, E edge)
322 {
323 if (!containsVertex(vertex) || !containsEdge(edge))
324 return null;
325 Pair<V> endpoints = edge_vpairs.get(edge);
326 V v1 = endpoints.getFirst();
327 V v2 = endpoints.getSecond();
328 return v1.equals(vertex) ? v2 : v1;
329 }
330
331
332
333
334 public Collection<E> getOutEdges(V vertex)
335 {
336 return getChildEdges(vertex);
337 }
338
339
340
341
342
343
344 @Override
345 public int getPredecessorCount(V vertex)
346 {
347 if (!containsVertex(vertex))
348 return -1;
349 return vertex.equals(root) ? 0 : 1;
350 }
351
352
353
354
355 public Collection<V> getPredecessors(V vertex)
356 {
357 if (!containsVertex(vertex))
358 return null;
359 if (vertex.equals(root))
360 return Collections.emptySet();
361 return Collections.singleton(getParent(vertex));
362 }
363
364
365
366
367 public V getSource(E directed_edge)
368 {
369 if (!containsEdge(directed_edge))
370 return null;
371 return edge_vpairs.get(directed_edge).getSecond();
372 }
373
374
375
376
377 @Override
378 public int getSuccessorCount(V vertex)
379 {
380 return getChildCount(vertex);
381 }
382
383
384
385
386 public Collection<V> getSuccessors(V vertex)
387 {
388 return getChildren(vertex);
389 }
390
391
392
393
394 @Override
395 public int inDegree(V vertex)
396 {
397 if (!containsVertex(vertex))
398 return 0;
399 if (vertex.equals(root))
400 return 0;
401 return 1;
402 }
403
404
405
406
407 public boolean isDest(V vertex, E edge)
408 {
409 if (!containsEdge(edge) || !containsVertex(vertex))
410 return false;
411 return edge_vpairs.get(edge).getSecond().equals(vertex);
412 }
413
414
415
416
417
418
419
420 public boolean isLeaf(V vertex)
421 {
422 if (!containsVertex(vertex))
423 return false;
424 return outDegree(vertex) == 0;
425 }
426
427
428
429
430
431
432
433
434 @Override
435 public boolean isPredecessor(V v1, V v2)
436 {
437 if (!containsVertex(v2))
438 return false;
439 return getParent(v2).equals(v1);
440 }
441
442
443
444
445
446
447
448 public boolean isRoot(V vertex)
449 {
450 if (root == null)
451 return false;
452 return root.equals(vertex);
453 }
454
455
456
457
458 public boolean isSource(V vertex, E edge)
459 {
460 if (!containsEdge(edge) || !containsVertex(vertex))
461 return false;
462 return edge_vpairs.get(edge).getFirst().equals(vertex);
463 }
464
465
466
467
468 @Override
469 public boolean isSuccessor(V v1, V v2)
470 {
471 if (!containsVertex(v2))
472 return false;
473 if (containsVertex(v1))
474 return getParent(v1).equals(v2);
475 return isLeaf(v2) && v1 == null;
476 }
477
478
479
480
481 @Override
482 public int outDegree(V vertex)
483 {
484 if (!containsVertex(vertex))
485 return 0;
486 List<E> out_edges = vertex_data.get(vertex).child_edges;
487 if (out_edges == null)
488 return 0;
489 int degree = 0;
490 for (E e : out_edges)
491 degree += (e == null) ? 0 : 1;
492 return degree;
493 }
494
495
496
497
498 @Override
499 @SuppressWarnings("unchecked")
500 public boolean addEdge(E edge, Collection<? extends V> vertices, EdgeType edge_type)
501 {
502 if (edge == null || vertices == null)
503 throw new IllegalArgumentException("inputs may not be null");
504 if (vertices.size() != 2)
505 throw new IllegalArgumentException("'vertices' must contain " +
506 "exactly 2 distinct vertices");
507 this.validateEdgeType(edge_type);
508 Pair<V> endpoints;
509 if (vertices instanceof Pair)
510 endpoints = (Pair<V>)vertices;
511 else
512 endpoints = new Pair<V>(vertices);
513 V v1 = endpoints.getFirst();
514 V v2 = endpoints.getSecond();
515 if (v1.equals(v2))
516 throw new IllegalArgumentException("Input vertices must be distinct");
517 return addEdge(edge, v1, v2);
518 }
519
520
521
522
523 public boolean addVertex(V vertex)
524 {
525 if(root == null)
526 {
527 this.root = vertex;
528 vertex_data.put(vertex, new VertexData(null, 0));
529 this.height = 0;
530 return true;
531 }
532 else
533 {
534 throw new UnsupportedOperationException("Unless you are setting " +
535 "the root, use addEdge() or addChild()");
536 }
537 }
538
539
540
541
542 @Override
543 public boolean isIncident(V vertex, E edge)
544 {
545 if (!containsVertex(vertex) || !containsEdge(edge))
546 return false;
547 return edge_vpairs.get(edge).contains(vertex);
548 }
549
550
551
552
553 @Override
554 public boolean isNeighbor(V v1, V v2)
555 {
556 if (!containsVertex(v1) || !containsVertex(v2))
557 return false;
558 return getNeighbors(v1).contains(v2);
559 }
560
561
562
563
564 public boolean containsEdge(E edge)
565 {
566 return edge_vpairs.containsKey(edge);
567 }
568
569
570
571
572 public boolean containsVertex(V vertex)
573 {
574 return vertex_data.containsKey(vertex);
575 }
576
577
578
579
580
581 @Override
582 public E findEdge(V v1, V v2)
583 {
584 if (!containsVertex(v1) || !containsVertex(v2))
585 return null;
586 VertexData v1_data = vertex_data.get(v1);
587 if (edge_vpairs.get(v1_data.parent_edge).getFirst().equals(v2))
588 return v1_data.parent_edge;
589 List<E> edges = v1_data.child_edges;
590 if (edges == null)
591 return null;
592 for (E edge : edges)
593 if (edge != null && edge_vpairs.get(edge).getSecond().equals(v2))
594 return edge;
595 return null;
596 }
597
598
599
600
601 @Override
602 public Collection<E> findEdgeSet(V v1, V v2)
603 {
604 E edge = findEdge(v1, v2);
605 if (edge == null)
606 return Collections.emptySet();
607 else
608 return Collections.singleton(edge);
609 }
610
611
612
613
614
615
616
617
618
619
620 public V getChild(V vertex, int index)
621 {
622 if (index < 0 || index >= order)
623 throw new ArrayIndexOutOfBoundsException(index + " is not in [0, order-1]");
624 if (!containsVertex(vertex))
625 return null;
626 List<E> edges = vertex_data.get(vertex).child_edges;
627 if (edges == null)
628 return null;
629 E edge = edges.get(index);
630 return edge == null ? null : edge_vpairs.get(edge).getSecond();
631 }
632
633
634
635
636 public int getEdgeCount()
637 {
638 return edge_vpairs.size();
639 }
640
641
642
643
644 public Collection<E> getEdges()
645 {
646 return CollectionUtils.unmodifiableCollection(edge_vpairs.keySet());
647 }
648
649
650
651
652 @Override
653 public int getIncidentCount(E edge)
654 {
655 return 2;
656 }
657
658
659
660
661 public Collection<E> getIncidentEdges(V vertex)
662 {
663 if (!containsVertex(vertex))
664 return null;
665 ArrayList<E> edges = new ArrayList<E>(order+1);
666 VertexData v_data = vertex_data.get(vertex);
667 if (v_data.parent_edge != null)
668 edges.add(v_data.parent_edge);
669 if (v_data.child_edges != null)
670 {
671 for (E edge : v_data.child_edges)
672 if (edge != null)
673 edges.add(edge);
674 }
675 if (edges.isEmpty())
676 return Collections.emptySet();
677 return Collections.unmodifiableCollection(edges);
678 }
679
680
681
682
683 @Override
684 public Collection<V> getIncidentVertices(E edge)
685 {
686 return edge_vpairs.get(edge);
687 }
688
689
690
691
692 @Override
693 public int getNeighborCount(V vertex)
694 {
695 if (!containsVertex(vertex))
696 return 0;
697 return (vertex.equals(root) ? 0 : 1) + this.getChildCount(vertex);
698 }
699
700
701
702
703 public Collection<V> getNeighbors(V vertex)
704 {
705 if (!containsVertex(vertex))
706 return null;
707 ArrayList<V> vertices = new ArrayList<V>(order+1);
708 VertexData v_data = vertex_data.get(vertex);
709 if (v_data.parent_edge != null)
710 vertices.add(edge_vpairs.get(v_data.parent_edge).getFirst());
711 if (v_data.child_edges != null)
712 {
713 for (E edge : v_data.child_edges)
714 if (edge != null)
715 vertices.add(edge_vpairs.get(edge).getSecond());
716 }
717 if (vertices.isEmpty())
718 return Collections.emptySet();
719 return Collections.unmodifiableCollection(vertices);
720 }
721
722
723
724
725 public int getVertexCount()
726 {
727 return vertex_data.size();
728 }
729
730
731
732
733 public Collection<V> getVertices()
734 {
735 return CollectionUtils.unmodifiableCollection(vertex_data.keySet());
736 }
737
738
739
740
741 public boolean removeEdge(E edge)
742 {
743 if (!containsEdge(edge))
744 return false;
745
746 removeVertex(edge_vpairs.get(edge).getSecond());
747 edge_vpairs.remove(edge);
748
749 return true;
750 }
751
752
753
754
755 public boolean removeVertex(V vertex)
756 {
757 if (!containsVertex(vertex))
758 return false;
759
760
761 for(V v : getChildren(vertex))
762 removeVertex(v);
763
764 E parent_edge = getParentEdge(vertex);
765 edge_vpairs.remove(parent_edge);
766 List<E> edges = vertex_data.get(vertex).child_edges;
767 if (edges != null)
768 for (E edge : edges)
769 edge_vpairs.remove(edge);
770 vertex_data.remove(vertex);
771
772 return true;
773 }
774
775 protected class VertexData
776 {
777 List<E> child_edges;
778 E parent_edge;
779 int depth;
780
781 protected VertexData(E parent_edge, int depth)
782 {
783 this.parent_edge = parent_edge;
784 this.depth = depth;
785 }
786 }
787
788 @Override
789 public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
790 {
791 if (edge == null || endpoints == null)
792 throw new IllegalArgumentException("inputs must not be null");
793 return addEdge(edge, endpoints.getFirst(), endpoints.getSecond(), edgeType);
794 }
795 }