View Javadoc

1   /*
2    * Created on May 8, 2008
3    *
4    * Copyright (c) 2008, 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;
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   * An implementation of <code>Tree</code> in which each vertex has
29   * <= k children.  The value of 'k' is specified by the constructor
30   * parameter.  A specific child (edge) can be retrieved directly by specifying the
31   * index at which the child is located.  By default, new (child) vertices
32   * are added at the lowest index available, if no index is specified.
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       * Returns a {@code Factory} that creates an instance of this graph type.
46       * @param <V> the vertex type for the graph factory
47       * @param <E> the edge type for the graph factory
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       * Creates a new instance with the specified order (maximum number of children).
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       * Returns the number of children that {@code vertex} has.  
71       * @see edu.uci.ics.jung.graph.Tree#getChildCount(java.lang.Object)
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       * Returns the child edge of the vertex at index <code>index</code>.
88       * @param vertex
89       * @param index
90       * @return the child edge of the vertex at index <code>index</code>
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      * @see edu.uci.ics.jung.graph.Tree#getChildEdges(java.lang.Object)
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      * Returns an ordered list of {@code vertex}'s child vertices.
116      * If there is no child in position i, then the list will contain
117      * {@code null} in position i.  If {@code vertex} has no children
118      * then the empty set will be returned.
119      * @see edu.uci.ics.jung.graph.Tree#getChildren(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Tree#getDepth(java.lang.Object)
136      * @return the depth of the vertex in this tree, or -1 if the vertex is
137      * not present in this tree
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      * Returns the height of the tree, or -1 if the tree is empty.
148      * @see edu.uci.ics.jung.graph.Tree#getHeight()
149      */
150     public int getHeight() 
151     {
152         return height;
153     }
154   
155     /**
156      * @see edu.uci.ics.jung.graph.Tree#getParent(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Tree#getParentEdge(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Tree#getRoot()
179      */
180     public V getRoot() 
181     {
182         return root;
183     }
184   
185     /**
186      * @see edu.uci.ics.jung.graph.Forest#getTrees()
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      * Adds the specified {@code child} vertex and edge {@code e} to the graph
197      * with the specified parent vertex {@code parent}.  If {@code index} is 
198      * greater than or equal to 0, then the child is placed at position
199      * {@code index}; if it is less than 0, the child is placed at the lowest
200      * available position; if it is greater than or equal to the order of this
201      * tree, an exception is thrown.
202      * 
203      * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
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     	// initialize VertexData for child; leave child's child_edges null for now
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      * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)
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      * @see edu.uci.ics.jung.graph.Graph#getDest(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getEndpoints(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getInEdges(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getOpposite(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getOutEdges(java.lang.Object)
333      */
334     public Collection<E> getOutEdges(V vertex) 
335     {
336         return getChildEdges(vertex);
337     }
338   
339     /**
340      * @see edu.uci.ics.jung.graph.Graph#getPredecessorCount(java.lang.Object)
341      * @return 0 if <code>vertex</code> is the root, -1 if the vertex is 
342      * not an element of this tree, and 1 otherwise
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      * @see edu.uci.ics.jung.graph.Graph#getPredecessors(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getSource(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#getSuccessorCount(java.lang.Object)
376      */
377     @Override
378     public int getSuccessorCount(V vertex) 
379     {
380         return getChildCount(vertex);
381     }
382   
383     /**
384      * @see edu.uci.ics.jung.graph.Graph#getSuccessors(java.lang.Object)
385      */
386     public Collection<V> getSuccessors(V vertex) 
387     {
388         return getChildren(vertex);
389     }
390   
391     /**
392      * @see edu.uci.ics.jung.graph.Graph#inDegree(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#isDest(java.lang.Object, java.lang.Object)
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      * Returns <code>true</code> if <code>vertex</code> is a leaf of this tree,
416      * i.e., if it has no children.
417      * @param vertex the vertex to be queried
418      * @return <code>true</code> if <code>outDegree(vertex)==0</code>
419      */
420     public boolean isLeaf(V vertex)
421     {
422         if (!containsVertex(vertex))
423             return false;
424         return outDegree(vertex) == 0;
425     }
426     
427     /**
428      * Returns true iff <code>v1</code> is the parent of <code>v2</code>.
429      * Note that if <code>v2</code> is the root and <code>v1</code> is <code>null</code>,
430      * this method returns <code>true</code>.
431      * 
432      * @see edu.uci.ics.jung.graph.Graph#isPredecessor(java.lang.Object, java.lang.Object)
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      * Returns <code>true</code> if <code>vertex</code> is a leaf of this tree,
444      * i.e., if it has no children.
445      * @param vertex the vertex to be queried
446      * @return <code>true</code> if <code>outDegree(vertex)==0</code>
447      */
448     public boolean isRoot(V vertex)
449     {
450         if (root == null)
451             return false;
452         return root.equals(vertex);
453     }
454     
455     /**
456      * @see edu.uci.ics.jung.graph.Graph#isSource(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#isSuccessor(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Graph#outDegree(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#addEdge(java.lang.Object, java.util.Collection)
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      * @see edu.uci.ics.jung.graph.Hypergraph#addVertex(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#isIncident(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#isNeighbor(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#containsEdge(java.lang.Object)
563      */
564     public boolean containsEdge(E edge) 
565     {
566     	return edge_vpairs.containsKey(edge);
567     }
568   
569     /**
570      * @see edu.uci.ics.jung.graph.Hypergraph#containsVertex(java.lang.Object)
571      */
572     public boolean containsVertex(V vertex) 
573     {
574     	return vertex_data.containsKey(vertex);
575     }
576   
577   
578     /**
579      * @see edu.uci.ics.jung.graph.Hypergraph#findEdge(java.lang.Object, java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#findEdgeSet(java.lang.Object, java.lang.Object)
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      * Returns the child of <code>vertex</code> at position <code>index</code> 
613      * in this tree, or <code>null</code> if it has no child at that position.
614      * @param vertex the vertex to query
615      * @return the child of <code>vertex</code> at position <code>index</code> 
616      * in this tree, or <code>null</code> if it has no child at that position
617      * @throws ArrayIndexOutOfBoundsException if <code>index</code> is not in 
618      * the range {@code [0, order-1]}
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      * @see edu.uci.ics.jung.graph.Hypergraph#getEdgeCount()
635      */
636     public int getEdgeCount() 
637     {
638     	return edge_vpairs.size();
639     }
640   
641     /**
642      * @see edu.uci.ics.jung.graph.Hypergraph#getEdges()
643      */
644     public Collection<E> getEdges() 
645     {
646     	return CollectionUtils.unmodifiableCollection(edge_vpairs.keySet());
647     }
648   
649     /**
650      * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentCount(java.lang.Object)
651      */
652     @Override
653     public int getIncidentCount(E edge) 
654     {
655     	return 2;  // all tree edges have 2 incident vertices
656     }
657   
658     /**
659      * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentEdges(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#getIncidentVertices(java.lang.Object)
682      */
683     @Override
684     public Collection<V> getIncidentVertices(E edge) 
685     {
686     	return edge_vpairs.get(edge);
687     }
688   
689     /**
690      * @see edu.uci.ics.jung.graph.Hypergraph#getNeighborCount(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#getNeighbors(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#getVertexCount()
724      */
725     public int getVertexCount() 
726     {
727     	return vertex_data.size();
728     }
729   
730     /**
731      * @see edu.uci.ics.jung.graph.Hypergraph#getVertices()
732      */
733     public Collection<V> getVertices() 
734     {
735       return CollectionUtils.unmodifiableCollection(vertex_data.keySet());
736     }
737   
738     /**
739      * @see edu.uci.ics.jung.graph.Hypergraph#removeEdge(java.lang.Object)
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      * @see edu.uci.ics.jung.graph.Hypergraph#removeVertex(java.lang.Object)
754      */
755     public boolean removeVertex(V vertex) 
756     {
757     	if (!containsVertex(vertex))
758     		return false;
759     	
760     	// recursively remove all of vertex's children
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 }