Coverage Report

 /*
 
     dsh-graph  Directed graph interface and implementation.
     Copyright (c) 2004-2012 held jointly by the individual authors.
 
     This library is free software; you can redistribute it and/or modify it
     under the terms of the GNU Lesser General Public License as published
     by the Free Software Foundation; either version 3 of the License, or (at
     your option) any later version.
 
     This library is distributed in the hope that it will be useful, but WITHOUT
     ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
     License for more details.
 
     You should have received a copy of the GNU Lesser General Public License
     along with this library;  if not, write to the Free Software Foundation,
     Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA.
 
     > http://www.fsf.org/licensing/licenses/lgpl.html
     > http://www.opensource.org/licenses/lgpl-license.php
 
 */
 package org.dishevelled.graph.impl;
 
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Queue;
 import java.util.Set;
 
 import java.util.concurrent.ArrayBlockingQueue;
 
 import org.dishevelled.functor.UnaryProcedure;
 
 import org.dishevelled.graph.Edge;
 import org.dishevelled.graph.Graph;
 import org.dishevelled.graph.Node;
 
 /**
  * Static utility methods on directed graphs.
  *
  * @author  Michael Heuer
  * @version $Revision$ $Date$
  */
 public final class GraphUtils
 {
 
     /**
      * Private no-arg constructor.
      */
     private GraphUtils()
     {
         // empty
     }
 
 
     /**
      * Create and return a new directed graph.  The graph will not be null.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @return a new directed graph
      */
     public static <N, E> Graph<N, E> createGraph()
     {
         return new GraphImpl<N, E>();
     }
 
     /**
      * Create and return a new directed graph with the specified initial node
      * and edge capacities.  The graph will not be null.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param nodeCapacity initial node capacity, must be <code>&gt;= 0</code>
      * @param edgeCapacity initial edge capacity, must be <code>&gt;= 0</code>
      * @return a new directed graph with the specified initial node and edge capacities
      */
     public static <N, E> Graph<N, E> createGraph(final int nodeCapacity, final int edgeCapacity)
     {
         return new GraphImpl<N, E>(nodeCapacity, edgeCapacity);
     }
 
     /**
      * Create and return a new directed graph with the same structure and same node
      * and edge values as the specified graph.  The graph will not be null.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph to copy, must not be null
      * @return a new directed graph with the same structure and same node
      *    and edge values as the specified graph
      */
     public static <N, E> Graph<N, E> createGraph(final Graph<N, E> graph)
     {
         return new GraphImpl<N, E>(graph);
     }
 
     /**
      * Find the connected components of the specified graph.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph, must not be null
      * @return a set of the connected components of the specified graph
      */
     public static <N, E> Set<Set<Node<N, E>>> connectedComponents(final Graph<N, E> graph)
     {
         if (graph == null)
         {
             throw new IllegalArgumentException("graph must not be null");
         }
         final Set<Node<N, E>> empty = Collections.emptySet();
         final Set<Set<Node<N, E>>> connectedComponents = new HashSet<Set<Node<N, E>>>();
         final Map<Node<N, E>, Set<Node<N, E>>> componentsPerNode = graph.nodeMap(empty);
 
         for (Node<N, E> node : graph.nodes())
         {
             if (empty.equals(componentsPerNode.get(node)))
             {
                 final Set<Node<N, E>> collect = new HashSet<Node<N, E>>();
                 undirectedBreadthFirstSearch(graph, node, new UnaryProcedure<Node<N, E>>()
                                              {
                                                  @Override
                                                  public void run(final Node<N, E> node)
                                                  {
                                                      collect.add(node);
                                                  }
                                              });
                 for (Node<N, E> connected : collect)
                 {
                     componentsPerNode.put(connected, collect);
                 }
                 connectedComponents.add(collect);
             }
         }
         return connectedComponents;
     }
 
     /**
      * Depth-first search.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph to search, must not be null
      * @param node node to start from, must not be null and must be contained in
      *    the specified graph
      * @param procedure procedure to run when visiting each node, must not be null
      */
     public static <N, E> void depthFirstSearch(final Graph<N, E> graph,
                                   final Node<N, E> node,
                                   final UnaryProcedure<Node<N, E>> procedure)
     {
         if (graph == null)
         {
             throw new IllegalArgumentException("graph must not be null");
         }
         if (node == null)
         {
             throw new IllegalArgumentException("node must not be null");
         }
         if (!graph.nodes().contains(node))
         {
             throw new IllegalArgumentException("node must be contained in the specified graph");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
         recursiveDepthFirstSearch(node, visited, procedure);
     }
 
     /**
      * Recursive depth-first search implementation.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param node node
      * @param visited map of visited state keyed by node
      * @param procedure procedure
      */
     private static <N, E> void recursiveDepthFirstSearch(final Node<N, E> node,
                                     final Map<Node<N, E>, Boolean> visited,
                                     final UnaryProcedure<Node<N, E>> procedure)
     {
         if (visited.get(node))
         {
             return;
         }
         for (Edge<N, E> edge : node.outEdges())
         {
             recursiveDepthFirstSearch(edge.target(), visited, procedure);
         }
         procedure.run(node);
         visited.put(node, true);
     }
 
     /**
      * Breadth-first search.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph to search, must not be null
      * @param node node to start from, must not be null and must be contained in
      *    the specified graph
      * @param procedure procedure to run when visiting each node, must not be null
      */
     public static <N, E> void breadthFirstSearch(final Graph<N, E> graph,
                                   final Node<N, E> node,
                                   final UnaryProcedure<Node<N, E>> procedure)
     {
         if (graph == null)
         {
             throw new IllegalArgumentException("graph must not be null");
         }
         if (node == null)
         {
             throw new IllegalArgumentException("node must not be null");
         }
         if (!graph.nodes().contains(node))
         {
             throw new IllegalArgumentException("node must be contained in the specified graph");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
         Queue<Node<N, E>> queue = new ArrayBlockingQueue<Node<N, E>>(graph.nodeCount());
         queue.offer(node);
         while (!queue.isEmpty())
         {
             Node<N, E> next = queue.poll();
             if (!visited.get(next))
             {
                 procedure.run(next);
                 visited.put(next, Boolean.TRUE);
             }
             for (Edge<N, E> out : next.outEdges())
             {
                 queue.offer(out.target());
             }
         }
     }
 
     /**
      * Undirected breadth-first search.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph to search, must not be null
      * @param node node to start from, must not be null and must be contained in
      *    the specified graph
      * @param procedure procedure to run when visiting each node, must not be null
      */
     public static <N, E> void undirectedBreadthFirstSearch(final Graph<N, E> graph,
                                             final Node<N, E> node,
                                             final UnaryProcedure<Node<N, E>> procedure)
     {
         if (graph == null)
         {
             throw new IllegalArgumentException("graph must not be null");
         }
         if (node == null)
         {
             throw new IllegalArgumentException("node must not be null");
         }
         if (!graph.nodes().contains(node))
         {
             throw new IllegalArgumentException("node must be contained in the specified graph");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
         Queue<Node<N, E>> queue = new ArrayBlockingQueue<Node<N, E>>(graph.nodeCount());
         queue.offer(node);
         while (!queue.isEmpty())
         {
             Node<N, E> next = queue.poll();
             if (!visited.get(next))
             {
                 procedure.run(next);
                 visited.put(next, Boolean.TRUE);
             }
             for (Edge<N, E> in : next.inEdges())
             {
                 Node<N, E> source = in.source();
                 if (!visited.get(source))
                 {
                     queue.offer(source);
                 }
             }
             for (Edge<N, E> out : next.outEdges())
             {
                 Node<N, E> target = out.target();
                 if (!visited.get(target))
                 {
                     queue.offer(target);
                 }
             }
         }
     }
 
     /**
      * Create and return an unmodifiable graph decorator that decorates the specified graph.
      *
      * @param <N> node value type
      * @param <E> edge value type
      * @param graph graph to decorate, must not be null
      * @return an unmodifiable graph decorator that decorates the specified graph
      */
     public static <N, E> Graph<N, E> unmodifiableGraph(final Graph<N, E> graph)
     {
         return new UnmodifiableGraph<N, E>(graph);
     }
 
     /**
      * Unmodifiable graph decorator.
      */
     private static final class UnmodifiableGraph<N, E>
         extends AbstractGraphDecorator<N, E>
     {
 
         /**
          * Create a unmodifiable graph decorator that decorates the specified graph.
          *
          * @param graph graph to decorate, must not be null
          */
         private UnmodifiableGraph(final Graph<N, E> graph)
         {
             super(graph);
         }
 
 
         /** {@inheritDoc} */
         public void clear()
         {
             throw new UnsupportedOperationException("clear operation not supported by this graph");
         }
 
         /** {@inheritDoc} */
         public Node<N, E> createNode(final N value)
         {
             throw new UnsupportedOperationException("createNode operation not supported by this graph");
         }
 
         /** {@inheritDoc} */
         public void remove(final Node<N, E> node)
         {
             throw new UnsupportedOperationException("remove(Node) operation not supported by this graph");
         }
 
         /** {@inheritDoc} */
         public Edge<N, E> createEdge(final Node<N, E> source, final Node<N, E> target, final E value)
         {
             throw new UnsupportedOperationException("createEdge operation not supported by this graph");
         }
 
         /** {@inheritDoc} */
         public void remove(final Edge<N, E> edge)
         {
             throw new UnsupportedOperationException("remove(Edge) operation not supported by this graph");
         }
     }
 }

1		/*
2
3		dsh-graph Directed graph interface and implementation.
4		Copyright (c) 2004-2012 held jointly by the individual authors.
5
6		This library is free software; you can redistribute it and/or modify it
7		under the terms of the GNU Lesser General Public License as published
8		by the Free Software Foundation; either version 3 of the License, or (at
9		your option) any later version.
10
11		This library is distributed in the hope that it will be useful, but WITHOUT
12		ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
13		FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14		License for more details.
15
16		You should have received a copy of the GNU Lesser General Public License
17		along with this library; if not, write to the Free Software Foundation,
18		Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
19
20		> http://www.fsf.org/licensing/licenses/lgpl.html
21		> http://www.opensource.org/licenses/lgpl-license.php
22
23		*/
24		package org.dishevelled.graph.impl;
25
26		import java.util.Collections;
27		import java.util.HashSet;
28		import java.util.Map;
29		import java.util.Queue;
30		import java.util.Set;
31
32		import java.util.concurrent.ArrayBlockingQueue;
33
34		import org.dishevelled.functor.UnaryProcedure;
35
36		import org.dishevelled.graph.Edge;
37		import org.dishevelled.graph.Graph;
38		import org.dishevelled.graph.Node;
39
40		/**
41		* Static utility methods on directed graphs.
42		*
43		* @author Michael Heuer
44		* @version $Revision$ $Date$
45		*/
46		public final class GraphUtils
47		{
48
49		/**
50		* Private no-arg constructor.
51		*/
52		private GraphUtils()
53	0	{
54		// empty
55	0	}
56
57
58		/**
59		* Create and return a new directed graph. The graph will not be null.
60		*
61		* @param <N> node value type
62		* @param <E> edge value type
63		* @return a new directed graph
64		*/
65		public static <N, E> Graph<N, E> createGraph()
66		{
67	9	return new GraphImpl<N, E>();
68		}
69
70		/**
71		* Create and return a new directed graph with the specified initial node
72		* and edge capacities. The graph will not be null.
73		*
74		* @param <N> node value type
75		* @param <E> edge value type
76		* @param nodeCapacity initial node capacity, must be <code>>= 0</code>
77		* @param edgeCapacity initial edge capacity, must be <code>>= 0</code>
78		* @return a new directed graph with the specified initial node and edge capacities
79		*/
80		public static <N, E> Graph<N, E> createGraph(final int nodeCapacity, final int edgeCapacity)
81		{
82	4	return new GraphImpl<N, E>(nodeCapacity, edgeCapacity);
83		}
84
85		/**
86		* Create and return a new directed graph with the same structure and same node
87		* and edge values as the specified graph. The graph will not be null.
88		*
89		* @param <N> node value type
90		* @param <E> edge value type
91		* @param graph graph to copy, must not be null
92		* @return a new directed graph with the same structure and same node
93		* and edge values as the specified graph
94		*/
95		public static <N, E> Graph<N, E> createGraph(final Graph<N, E> graph)
96		{
97	3	return new GraphImpl<N, E>(graph);
98		}
99
100		/**
101		* Find the connected components of the specified graph.
102		*
103		* @param <N> node value type
104		* @param <E> edge value type
105		* @param graph graph, must not be null
106		* @return a set of the connected components of the specified graph
107		*/
108		public static <N, E> Set<Set<Node<N, E>>> connectedComponents(final Graph<N, E> graph)
109		{
110	7	if (graph == null)
111		{
112	1	throw new IllegalArgumentException("graph must not be null");
113		}
114	6	final Set<Node<N, E>> empty = Collections.emptySet();
115	6	final Set<Set<Node<N, E>>> connectedComponents = new HashSet<Set<Node<N, E>>>();
116	6	final Map<Node<N, E>, Set<Node<N, E>>> componentsPerNode = graph.nodeMap(empty);
117
118	6	for (Node<N, E> node : graph.nodes())
119		{
120	13	if (empty.equals(componentsPerNode.get(node)))
121		{
122	7	final Set<Node<N, E>> collect = new HashSet<Node<N, E>>();
123	7	undirectedBreadthFirstSearch(graph, node, new UnaryProcedure<Node<N, E>>()
124	20	{
125		@Override
126		public void run(final Node<N, E> node)
127		{
128	13	collect.add(node);
129	13	}
130		});
131	7	for (Node<N, E> connected : collect)
132		{
133	13	componentsPerNode.put(connected, collect);
134		}
135	7	connectedComponents.add(collect);
136	13	}
137		}
138	6	return connectedComponents;
139		}
140
141		/**
142		* Depth-first search.
143		*
144		* @param <N> node value type
145		* @param <E> edge value type
146		* @param graph graph to search, must not be null
147		* @param node node to start from, must not be null and must be contained in
148		* the specified graph
149		* @param procedure procedure to run when visiting each node, must not be null
150		*/
151		public static <N, E> void depthFirstSearch(final Graph<N, E> graph,
152		final Node<N, E> node,
153		final UnaryProcedure<Node<N, E>> procedure)
154		{
155	5	if (graph == null)
156		{
157	1	throw new IllegalArgumentException("graph must not be null");
158		}
159	4	if (node == null)
160		{
161	1	throw new IllegalArgumentException("node must not be null");
162		}
163	3	if (!graph.nodes().contains(node))
164		{
165	1	throw new IllegalArgumentException("node must be contained in the specified graph");
166		}
167	2	if (procedure == null)
168		{
169	1	throw new IllegalArgumentException("procedure must not be null");
170		}
171	1	Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
172	1	recursiveDepthFirstSearch(node, visited, procedure);
173	1	}
174
175		/**
176		* Recursive depth-first search implementation.
177		*
178		* @param <N> node value type
179		* @param <E> edge value type
180		* @param node node
181		* @param visited map of visited state keyed by node
182		* @param procedure procedure
183		*/
184		private static <N, E> void recursiveDepthFirstSearch(final Node<N, E> node,
185		final Map<Node<N, E>, Boolean> visited,
186		final UnaryProcedure<Node<N, E>> procedure)
187		{
188	2	if (visited.get(node))
189		{
190	0	return;
191		}
192	2	for (Edge<N, E> edge : node.outEdges())
193		{
194	1	recursiveDepthFirstSearch(edge.target(), visited, procedure);
195		}
196	2	procedure.run(node);
197	2	visited.put(node, true);
198	2	}
199
200		/**
201		* Breadth-first search.
202		*
203		* @param <N> node value type
204		* @param <E> edge value type
205		* @param graph graph to search, must not be null
206		* @param node node to start from, must not be null and must be contained in
207		* the specified graph
208		* @param procedure procedure to run when visiting each node, must not be null
209		*/
210		public static <N, E> void breadthFirstSearch(final Graph<N, E> graph,
211		final Node<N, E> node,
212		final UnaryProcedure<Node<N, E>> procedure)
213		{
214	5	if (graph == null)
215		{
216	1	throw new IllegalArgumentException("graph must not be null");
217		}
218	4	if (node == null)
219		{
220	1	throw new IllegalArgumentException("node must not be null");
221		}
222	3	if (!graph.nodes().contains(node))
223		{
224	1	throw new IllegalArgumentException("node must be contained in the specified graph");
225		}
226	2	if (procedure == null)
227		{
228	1	throw new IllegalArgumentException("procedure must not be null");
229		}
230	1	Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
231	1	Queue<Node<N, E>> queue = new ArrayBlockingQueue<Node<N, E>>(graph.nodeCount());
232	1	queue.offer(node);
233	3	while (!queue.isEmpty())
234		{
235	2	Node<N, E> next = queue.poll();
236	2	if (!visited.get(next))
237		{
238	2	procedure.run(next);
239	2	visited.put(next, Boolean.TRUE);
240		}
241	2	for (Edge<N, E> out : next.outEdges())
242		{
243	1	queue.offer(out.target());
244		}
245	2	}
246	1	}
247
248		/**
249		* Undirected breadth-first search.
250		*
251		* @param <N> node value type
252		* @param <E> edge value type
253		* @param graph graph to search, must not be null
254		* @param node node to start from, must not be null and must be contained in
255		* the specified graph
256		* @param procedure procedure to run when visiting each node, must not be null
257		*/
258		public static <N, E> void undirectedBreadthFirstSearch(final Graph<N, E> graph,
259		final Node<N, E> node,
260		final UnaryProcedure<Node<N, E>> procedure)
261		{
262	12	if (graph == null)
263		{
264	1	throw new IllegalArgumentException("graph must not be null");
265		}
266	11	if (node == null)
267		{
268	1	throw new IllegalArgumentException("node must not be null");
269		}
270	10	if (!graph.nodes().contains(node))
271		{
272	1	throw new IllegalArgumentException("node must be contained in the specified graph");
273		}
274	9	if (procedure == null)
275		{
276	1	throw new IllegalArgumentException("procedure must not be null");
277		}
278	8	Map<Node<N, E>, Boolean> visited = graph.nodeMap(Boolean.FALSE);
279	8	Queue<Node<N, E>> queue = new ArrayBlockingQueue<Node<N, E>>(graph.nodeCount());
280	8	queue.offer(node);
281	23	while (!queue.isEmpty())
282		{
283	15	Node<N, E> next = queue.poll();
284	15	if (!visited.get(next))
285		{
286	15	procedure.run(next);
287	15	visited.put(next, Boolean.TRUE);
288		}
289	15	for (Edge<N, E> in : next.inEdges())
290		{
291	7	Node<N, E> source = in.source();
292	7	if (!visited.get(source))
293		{
294	0	queue.offer(source);
295		}
296	7	}
297	15	for (Edge<N, E> out : next.outEdges())
298		{
299	7	Node<N, E> target = out.target();
300	7	if (!visited.get(target))
301		{
302	7	queue.offer(target);
303		}
304	7	}
305	15	}
306	8	}
307
308		/**
309		* Create and return an unmodifiable graph decorator that decorates the specified graph.
310		*
311		* @param <N> node value type
312		* @param <E> edge value type
313		* @param graph graph to decorate, must not be null
314		* @return an unmodifiable graph decorator that decorates the specified graph
315		*/
316		public static <N, E> Graph<N, E> unmodifiableGraph(final Graph<N, E> graph)
317		{
318	58	return new UnmodifiableGraph<N, E>(graph);
319		}
320
321		/**
322		* Unmodifiable graph decorator.
323		*/
324	58	private static final class UnmodifiableGraph<N, E>
325		extends AbstractGraphDecorator<N, E>
326		{
327
328		/**
329		* Create a unmodifiable graph decorator that decorates the specified graph.
330		*
331		* @param graph graph to decorate, must not be null
332		*/
333		private UnmodifiableGraph(final Graph<N, E> graph)
334		{
335	58	super(graph);
336	57	}
337
338
339		/** {@inheritDoc} */
340		public void clear()
341		{
342	2	throw new UnsupportedOperationException("clear operation not supported by this graph");
343		}
344
345		/** {@inheritDoc} */
346		public Node<N, E> createNode(final N value)
347		{
348	8	throw new UnsupportedOperationException("createNode operation not supported by this graph");
349		}
350
351		/** {@inheritDoc} */
352		public void remove(final Node<N, E> node)
353		{
354	3	throw new UnsupportedOperationException("remove(Node) operation not supported by this graph");
355		}
356
357		/** {@inheritDoc} */
358		public Edge<N, E> createEdge(final Node<N, E> source, final Node<N, E> target, final E value)
359		{
360	2	throw new UnsupportedOperationException("createEdge operation not supported by this graph");
361		}
362
363		/** {@inheritDoc} */
364		public void remove(final Edge<N, E> edge)
365		{
366	3	throw new UnsupportedOperationException("remove(Edge) operation not supported by this graph");
367		}
368		}
369		}