Coverage Report

Coverage Report - edu.uci.ics.jung.graph.DelegateForest

Classes in this File

0/80

0/42

 package edu.uci.ics.jung.graph;
 
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
 
 import edu.uci.ics.jung.graph.util.EdgeType;
 import edu.uci.ics.jung.graph.util.Pair;
 import edu.uci.ics.jung.graph.util.TreeUtils;
 
 /**
  * An implementation of <code>Forest<V,E></code> that delegates to a specified <code>DirectedGraph</code>
  * instance.
  * @author Tom Nelson
  *
  * @param <V> the vertex type
  * @param <E> the edge type
  */
 @SuppressWarnings("serial")
 public class DelegateForest<V,E> extends GraphDecorator<V,E> implements Forest<V,E> 
 {
         /**
          * Creates an instance backed by a new {@code DirectedSparseGraph} instance.
          */
         public DelegateForest() {
                 this(new DirectedSparseGraph<V,E>());
         }
 
         /**
          * Creates an instance backed by the input {@code DirectedGraph} i
          */
         public DelegateForest(DirectedGraph<V,E> delegate) {
                 super(delegate);
         }
 
         /**
          * Add an edge to the tree, connecting v1, the parent and v2, the child.
          * v1 must already exist in the tree, and v2 must not already exist
          * the passed edge must be unique in the tree. Passing an edgeType
          * other than EdgeType.DIRECTED may cause an illegal argument exception
          * in the delegate graph.
          *
          * @param e a unique edge to add
          * @param v1 the parent node
          * @param v2 the child node
          * @param edgeType should be EdgeType.DIRECTED
          * @return true if this call mutates the underlying graph
          * @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)
          */
         @Override
         public boolean addEdge(E e, V v1, V v2, EdgeType edgeType) {
                 if(delegate.getVertices().contains(v1) == false) {
                         throw new IllegalArgumentException("Tree must already contain "+v1);
                 }
                 if(delegate.getVertices().contains(v2)) {
                         throw new IllegalArgumentException("Tree must not already contain "+v2);
                 }
                 return delegate.addEdge(e, v1, v2, edgeType);
         }
 
         /**
          * Add vertex as a root of the tree
          *
          * @param vertex the tree root to add
          * @return true if this call mutates the underlying graph
          * @see edu.uci.ics.jung.graph.Graph#addVertex(java.lang.Object)
          */
         @Override
         public boolean addVertex(V vertex) {
                 setRoot(vertex);
                 return true;
         }
 
         /**
          * Removes <code>edge</code> from this tree, and the subtree rooted
          * at the child vertex incident to <code>edge</code>.
          * (The subtree is removed to ensure that the tree in which the edge
          * was found is still a tree rather than a forest.  To change this
          * behavior so that the
          * @param edge the edge to remove
          * @return <code>true</code> iff the tree was modified
          * @see edu.uci.ics.jung.graph.Hypergraph#removeEdge(java.lang.Object)
          */
         @Override
         public boolean removeEdge(E edge) {
             return removeEdge(edge, true);
         }
 
         /**
          * Removes <code>edge</code> from this tree.
          * If <code>remove_subtree</code> is <code>true</code>, removes
          * the subtree rooted at the child vertex incident to <code>edge</code>.
          * Otherwise, leaves the subtree intact as a new component tree of this
          * forest.
          * @param edge the edge to remove
          * @param remove_subtree if <code>true</code>, remove the subtree
          * @return <code>true</code> iff the tree was modified
          */
         public boolean removeEdge(E edge, boolean remove_subtree)
         {
         if (!delegate.containsEdge(edge))
             return false;
         V child = getDest(edge);
         if (remove_subtree)
             return removeVertex(child);
         else
         {
             delegate.removeEdge(edge);
             return false;
         }
         }
 
         /**
          * Removes <code>vertex</code> from this tree, and the subtree
          * rooted at <code>vertex</code>.
          * @param vertex the vertex to remove
          * @return <code>true</code> iff the tree was modified
          * @see edu.uci.ics.jung.graph.Hypergraph#removeVertex(java.lang.Object)
          */
         @Override
         public boolean removeVertex(V vertex) {
             return removeVertex(vertex, true);
         }
 
         /**
          * Removes <code>vertex</code> from this tree.
      * If <code>remove_subtrees</code> is <code>true</code>, removes
      * the subtrees rooted at the children of <code>vertex</code>.
      * Otherwise, leaves these subtrees intact as new component trees of this
      * forest.
      * @param vertex the vertex to remove
          * @param remove_subtrees if <code>true</code>, remove the subtrees
          * rooted at <code>vertex</code>'s children
          * @return <code>true</code> iff the tree was modified
          */
         public boolean removeVertex(V vertex, boolean remove_subtrees)
         {
         if (!delegate.containsVertex(vertex))
             return false;
         if (remove_subtrees)
             for(V v : new ArrayList<V>(delegate.getSuccessors(vertex)))
                 removeVertex(v, true);
         return delegate.removeVertex(vertex);
         }
 
         /**
          * returns an ordered list of the nodes beginning at the root
          * and ending at the passed child node, including all intermediate
          * nodes.
          * @param child the last node in the path from the root
          * @return an ordered list of the nodes from root to child
          */
         public List<V> getPath(V child) {
         if (!delegate.containsVertex(child))
             return null;
                 List<V> list = new ArrayList<V>();
                 list.add(child);
                 V parent = getParent(child);
                 while(parent != null) {
                         list.add(list.size(), parent);
                         parent = getParent(parent);
                 }
                 return list;
         }
 
         public V getParent(V child) {
         if (!delegate.containsVertex(child))
             return null;
                 Collection<V> parents = delegate.getPredecessors(child);
                 if(parents.size() > 0) {
                         return parents.iterator().next();
                 }
                 return null;
         }
 
         /**
          * getter for the root of the tree
          * returns null, as this tree has >1 roots
          * @return the root
          */
         public V getRoot() {
                 return null;
         }
 
         /**
          * adds root as a root of the tree
          * @param root the initial tree root
          */
         public void setRoot(V root) {
                 delegate.addVertex(root);
         }
 
         /**
          * removes a node from the tree, causing all descendants of
          * the removed node also to be removed
          * @param orphan the node to remove
          * @return whether this call mutates the underlying graph
          */
         public boolean removeChild(V orphan) {
                 return removeVertex(orphan);
         }
 
         /**
          * computes and returns the depth of the tree from the
          * root to the passed vertex
          *
          * @param v the node who's depth is computed
          * @return the depth to the passed node.
          */
         public int getDepth(V v) {
                 return getPath(v).size();
         }
 
         /**
          * computes and returns the height of the tree
          *
          * @return the height
          */
         public int getHeight() {
                 int height = 0;
                 for(V v : getVertices()) {
                         height = Math.max(height, getDepth(v));
                 }
                 return height;
         }
 
         /**
          * computes and returns whether the passed node is
          * neither the root, nor a leaf node.
          * @return <code>true</code> if <code>v</code> is neither a leaf
          * nor a root
          */
         public boolean isInternal(V v) {
                 return isLeaf(v) == false && isRoot(v) == false;
         }
 
         /**
          * Returns true if {@code v} has no child nodes.
          */
         public boolean isLeaf(V v) {
                 return getChildren(v).size() == 0;
         }
 
         /**
          * Returns the children of {@code v}.
          */
         public Collection<V> getChildren(V v) {
                 return delegate.getSuccessors(v);
         }
 
         /**
          * Returns true if {@code v} has no parent node.
          */
         public boolean isRoot(V v) {
                 return getParent(v) == null;
         }
 
         @Override
     public int getIncidentCount(E edge)
     {
         return 2;
     }
 
         @SuppressWarnings("unchecked")
         @Override
         public boolean addEdge(E edge, Collection<? extends V> vertices) {
                 Pair<V> pair = null;
                 if(vertices instanceof Pair) {
                         pair = (Pair<V>)vertices;
                 } else {
                         pair = new Pair<V>(vertices);
                 }
                 return addEdge(edge, pair.getFirst(), pair.getSecond());
         }
 
         /**
          * Returns the root of each tree of this forest as a {@code Collection}.
          */
         public Collection<V> getRoots() {
                 Collection<V> roots = new HashSet<V>();
                 for(V v : delegate.getVertices()) {
                         if(delegate.getPredecessorCount(v) == 0) {
                                 roots.add(v);
                         }
                 }
                 return roots;
         }
 
         public Collection<Tree<V, E>> getTrees() {
                 Collection<Tree<V,E>> trees = new HashSet<Tree<V,E>>();
                 for(V v : getRoots()) {
                         Tree<V,E> tree = new DelegateTree<V,E>();
                         tree.addVertex(v);
                         TreeUtils.growSubTree(this, tree, v);
                         trees.add(tree);
                 }
                 return trees;
         }
 
         /**
          * Adds {@code tree} to this graph as an element of this forest.
          *
          * @param tree the tree to add to this forest as a component
          */
         public void addTree(Tree<V,E> tree) {
                 TreeUtils.addSubTree(this, tree, null, null);
         }
 
     public int getChildCount(V vertex)
     {
         return delegate.getSuccessorCount(vertex);
     }
 
     public Collection<E> getChildEdges(V vertex)
     {
         return delegate.getOutEdges(vertex);
     }
 
     public E getParentEdge(V vertex)
     {
         if (isRoot(vertex))
             return null;
         return delegate.getInEdges(vertex).iterator().next();
     }
 
 }

1		package edu.uci.ics.jung.graph;
2
3		import java.util.ArrayList;
4		import java.util.Collection;
5		import java.util.HashSet;
6		import java.util.List;
7
8		import edu.uci.ics.jung.graph.util.EdgeType;
9		import edu.uci.ics.jung.graph.util.Pair;
10		import edu.uci.ics.jung.graph.util.TreeUtils;
11
12		/**
13		* An implementation of <code>Forest<V,E></code> that delegates to a specified <code>DirectedGraph</code>
14		* instance.
15		* @author Tom Nelson
16		*
17		* @param <V> the vertex type
18		* @param <E> the edge type
19		*/
20		@SuppressWarnings("serial")
21		public class DelegateForest<V,E> extends GraphDecorator<V,E> implements Forest<V,E>
22		{
23		/**
24		* Creates an instance backed by a new {@code DirectedSparseGraph} instance.
25		*/
26		public DelegateForest() {
27	0	this(new DirectedSparseGraph<V,E>());
28	0	}
29
30		/**
31		* Creates an instance backed by the input {@code DirectedGraph} i
32		*/
33		public DelegateForest(DirectedGraph<V,E> delegate) {
34	0	super(delegate);
35	0	}
36
37		/**
38		* Add an edge to the tree, connecting v1, the parent and v2, the child.
39		* v1 must already exist in the tree, and v2 must not already exist
40		* the passed edge must be unique in the tree. Passing an edgeType
41		* other than EdgeType.DIRECTED may cause an illegal argument exception
42		* in the delegate graph.
43		*
44		* @param e a unique edge to add
45		* @param v1 the parent node
46		* @param v2 the child node
47		* @param edgeType should be EdgeType.DIRECTED
48		* @return true if this call mutates the underlying graph
49		* @see edu.uci.ics.jung.graph.Graph#addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)
50		*/
51		@Override
52		public boolean addEdge(E e, V v1, V v2, EdgeType edgeType) {
53	0	if(delegate.getVertices().contains(v1) == false) {
54	0	throw new IllegalArgumentException("Tree must already contain "+v1);
55		}
56	0	if(delegate.getVertices().contains(v2)) {
57	0	throw new IllegalArgumentException("Tree must not already contain "+v2);
58		}
59	0	return delegate.addEdge(e, v1, v2, edgeType);
60		}
61
62		/**
63		* Add vertex as a root of the tree
64		*
65		* @param vertex the tree root to add
66		* @return true if this call mutates the underlying graph
67		* @see edu.uci.ics.jung.graph.Graph#addVertex(java.lang.Object)
68		*/
69		@Override
70		public boolean addVertex(V vertex) {
71	0	setRoot(vertex);
72	0	return true;
73		}
74
75		/**
76		* Removes <code>edge</code> from this tree, and the subtree rooted
77		* at the child vertex incident to <code>edge</code>.
78		* (The subtree is removed to ensure that the tree in which the edge
79		* was found is still a tree rather than a forest. To change this
80		* behavior so that the
81		* @param edge the edge to remove
82		* @return <code>true</code> iff the tree was modified
83		* @see edu.uci.ics.jung.graph.Hypergraph#removeEdge(java.lang.Object)
84		*/
85		@Override
86		public boolean removeEdge(E edge) {
87	0	return removeEdge(edge, true);
88		}
89
90		/**
91		* Removes <code>edge</code> from this tree.
92		* If <code>remove_subtree</code> is <code>true</code>, removes
93		* the subtree rooted at the child vertex incident to <code>edge</code>.
94		* Otherwise, leaves the subtree intact as a new component tree of this
95		* forest.
96		* @param edge the edge to remove
97		* @param remove_subtree if <code>true</code>, remove the subtree
98		* @return <code>true</code> iff the tree was modified
99		*/
100		public boolean removeEdge(E edge, boolean remove_subtree)
101		{
102	0	if (!delegate.containsEdge(edge))
103	0	return false;
104	0	V child = getDest(edge);
105	0	if (remove_subtree)
106	0	return removeVertex(child);
107		else
108		{
109	0	delegate.removeEdge(edge);
110	0	return false;
111		}
112		}
113
114		/**
115		* Removes <code>vertex</code> from this tree, and the subtree
116		* rooted at <code>vertex</code>.
117		* @param vertex the vertex to remove
118		* @return <code>true</code> iff the tree was modified
119		* @see edu.uci.ics.jung.graph.Hypergraph#removeVertex(java.lang.Object)
120		*/
121		@Override
122		public boolean removeVertex(V vertex) {
123	0	return removeVertex(vertex, true);
124		}
125
126		/**
127		* Removes <code>vertex</code> from this tree.
128		* If <code>remove_subtrees</code> is <code>true</code>, removes
129		* the subtrees rooted at the children of <code>vertex</code>.
130		* Otherwise, leaves these subtrees intact as new component trees of this
131		* forest.
132		* @param vertex the vertex to remove
133		* @param remove_subtrees if <code>true</code>, remove the subtrees
134		* rooted at <code>vertex</code>'s children
135		* @return <code>true</code> iff the tree was modified
136		*/
137		public boolean removeVertex(V vertex, boolean remove_subtrees)
138		{
139	0	if (!delegate.containsVertex(vertex))
140	0	return false;
141	0	if (remove_subtrees)
142	0	for(V v : new ArrayList<V>(delegate.getSuccessors(vertex)))
143	0	removeVertex(v, true);
144	0	return delegate.removeVertex(vertex);
145		}
146
147		/**
148		* returns an ordered list of the nodes beginning at the root
149		* and ending at the passed child node, including all intermediate
150		* nodes.
151		* @param child the last node in the path from the root
152		* @return an ordered list of the nodes from root to child
153		*/
154		public List<V> getPath(V child) {
155	0	if (!delegate.containsVertex(child))
156	0	return null;
157	0	List<V> list = new ArrayList<V>();
158	0	list.add(child);
159	0	V parent = getParent(child);
160	0	while(parent != null) {
161	0	list.add(list.size(), parent);
162	0	parent = getParent(parent);
163		}
164	0	return list;
165		}
166
167		public V getParent(V child) {
168	0	if (!delegate.containsVertex(child))
169	0	return null;
170	0	Collection<V> parents = delegate.getPredecessors(child);
171	0	if(parents.size() > 0) {
172	0	return parents.iterator().next();
173		}
174	0	return null;
175		}
176
177		/**
178		* getter for the root of the tree
179		* returns null, as this tree has >1 roots
180		* @return the root
181		*/
182		public V getRoot() {
183	0	return null;
184		}
185
186		/**
187		* adds root as a root of the tree
188		* @param root the initial tree root
189		*/
190		public void setRoot(V root) {
191	0	delegate.addVertex(root);
192	0	}
193
194		/**
195		* removes a node from the tree, causing all descendants of
196		* the removed node also to be removed
197		* @param orphan the node to remove
198		* @return whether this call mutates the underlying graph
199		*/
200		public boolean removeChild(V orphan) {
201	0	return removeVertex(orphan);
202		}
203
204		/**
205		* computes and returns the depth of the tree from the
206		* root to the passed vertex
207		*
208		* @param v the node who's depth is computed
209		* @return the depth to the passed node.
210		*/
211		public int getDepth(V v) {
212	0	return getPath(v).size();
213		}
214
215		/**
216		* computes and returns the height of the tree
217		*
218		* @return the height
219		*/
220		public int getHeight() {
221	0	int height = 0;
222	0	for(V v : getVertices()) {
223	0	height = Math.max(height, getDepth(v));
224		}
225	0	return height;
226		}
227
228		/**
229		* computes and returns whether the passed node is
230		* neither the root, nor a leaf node.
231		* @return <code>true</code> if <code>v</code> is neither a leaf
232		* nor a root
233		*/
234		public boolean isInternal(V v) {
235	0	return isLeaf(v) == false && isRoot(v) == false;
236		}
237
238		/**
239		* Returns true if {@code v} has no child nodes.
240		*/
241		public boolean isLeaf(V v) {
242	0	return getChildren(v).size() == 0;
243		}
244
245		/**
246		* Returns the children of {@code v}.
247		*/
248		public Collection<V> getChildren(V v) {
249	0	return delegate.getSuccessors(v);
250		}
251
252		/**
253		* Returns true if {@code v} has no parent node.
254		*/
255		public boolean isRoot(V v) {
256	0	return getParent(v) == null;
257		}
258
259		@Override
260		public int getIncidentCount(E edge)
261		{
262	0	return 2;
263		}
264
265		@SuppressWarnings("unchecked")
266		@Override
267		public boolean addEdge(E edge, Collection<? extends V> vertices) {
268	0	Pair<V> pair = null;
269	0	if(vertices instanceof Pair) {
270	0	pair = (Pair<V>)vertices;
271		} else {
272	0	pair = new Pair<V>(vertices);
273		}
274	0	return addEdge(edge, pair.getFirst(), pair.getSecond());
275		}
276
277		/**
278		* Returns the root of each tree of this forest as a {@code Collection}.
279		*/
280		public Collection<V> getRoots() {
281	0	Collection<V> roots = new HashSet<V>();
282	0	for(V v : delegate.getVertices()) {
283	0	if(delegate.getPredecessorCount(v) == 0) {
284	0	roots.add(v);
285		}
286		}
287	0	return roots;
288		}
289
290		public Collection<Tree<V, E>> getTrees() {
291	0	Collection<Tree<V,E>> trees = new HashSet<Tree<V,E>>();
292	0	for(V v : getRoots()) {
293	0	Tree<V,E> tree = new DelegateTree<V,E>();
294	0	tree.addVertex(v);
295	0	TreeUtils.growSubTree(this, tree, v);
296	0	trees.add(tree);
297	0	}
298	0	return trees;
299		}
300
301		/**
302		* Adds {@code tree} to this graph as an element of this forest.
303		*
304		* @param tree the tree to add to this forest as a component
305		*/
306		public void addTree(Tree<V,E> tree) {
307	0	TreeUtils.addSubTree(this, tree, null, null);
308	0	}
309
310		public int getChildCount(V vertex)
311		{
312	0	return delegate.getSuccessorCount(vertex);
313		}
314
315		public Collection<E> getChildEdges(V vertex)
316		{
317	0	return delegate.getOutEdges(vertex);
318		}
319
320		public E getParentEdge(V vertex)
321		{
322	0	if (isRoot(vertex))
323	0	return null;
324	0	return delegate.getInEdges(vertex).iterator().next();
325		}
326
327		}