Coverage Report

 /*
 
     dsh-graph  Directed graph interface and implementation.
     Copyright (c) 2004-2013 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.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import org.dishevelled.functor.UnaryPredicate;
 import org.dishevelled.functor.UnaryProcedure;
 
 import org.dishevelled.graph.Edge;
 import org.dishevelled.graph.Graph;
 import org.dishevelled.graph.Node;
 
 /**
  * Directed graph implementation based on two HashSets.
  *
  * @param <N> node value type
  * @param <E> edge value type
  * @author  Michael Heuer
  * @version $Revision$ $Date$
  */
 public final class GraphImpl<N, E>
     implements Graph<N, E>
 {
     /** Set of nodes. */
     private final Set<Node<N, E>> nodes;
 
     /** Set of edges. */
     private final Set<Edge<N, E>> edges;
 
 
     /**
      * Create a new directed graph.
      */
     public GraphImpl()
     {
         nodes = new HashSet<Node<N, E>>();
         edges = new HashSet<Edge<N, E>>();
     }
 
     /**
      * Create a new directed graph with the specified initial node
      * and edge capacities.
      *
      * @param nodeCapacity initial node capacity, must be <code>&gt;= 0</code>
      * @param edgeCapacity initial edge capacity, must be <code>&gt;= 0</code>
      */
     public GraphImpl(final int nodeCapacity, final int edgeCapacity)
     {
         nodes = new HashSet<Node<N, E>>(nodeCapacity);
         edges = new HashSet<Edge<N, E>>(edgeCapacity);
     }
 
     /**
      * Create a new directed graph with the same structure and same node
      * and edge values as the specified graph (copy constructor).
      *
      * @param graph graph to copy, must not be null
      */
     public GraphImpl(final Graph<N, E> graph)
     {
         if (graph == null)
         {
             throw new IllegalArgumentException("graph must not be null");
         }
         if (graph.isEmpty())
         {
             nodes = new HashSet<Node<N, E>>();
             edges = new HashSet<Edge<N, E>>();
         }
         else
         {
             nodes = new HashSet<Node<N, E>>(graph.nodeCount());
             edges = new HashSet<Edge<N, E>>(graph.edgeCount());
             Map<Node<N, E>, Node<N, E>> nodeMap = graph.nodeMap(null);
             for (Map.Entry<Node<N, E>, Node<N, E>> entry : nodeMap.entrySet())
             {
                 Node<N, E> node = createNode(entry.getKey().getValue());
                 entry.setValue(node);
             }
             for (Edge<? extends N, ? extends E> edge : graph.edges())
             {
                 Node<N, E> source = nodeMap.get(edge.source());
                 Node<N, E> target = nodeMap.get(edge.target());
                 createEdge(source, target, edge.getValue());
             }
         }
     }
 
     /** {@inheritDoc} */
     public boolean isEmpty()
     {
         return (nodes.isEmpty() && edges.isEmpty());
     }
 
     /** {@inheritDoc} */
     public int nodeCount()
     {
         return nodes.size();
     }
 
     /** {@inheritDoc} */
     public Set<Node<N, E>> nodes()
     {
         return Collections.unmodifiableSet(nodes);
     }
 
     /** {@inheritDoc} */
     public Collection<N> nodeValues()
     {
         List<N> values = new ArrayList<N>(nodeCount());
         for (Node<N, E> node : nodes)
         {
             values.add(node.getValue());
         }
         return Collections.unmodifiableList(values);
     }
 
     /** {@inheritDoc} */
     public <T> Map<Node<N, E>, T> nodeMap(final T defaultValue)
     {
         Map<Node<N, E>, T> map = new HashMap<Node<N, E>, T>(nodeCount());
         for (Node<N, E> node : nodes)
         {
             map.put(node, defaultValue);
         }
         return new MapDecorator<Node<N, E>, T>(map);
     }
 
     /** {@inheritDoc} */
     public void forEachNode(final UnaryProcedure<Node<N, E>> procedure)
     {
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (Node<N, E> node : nodes)
         {
             procedure.run(node);
         }
     }
 
     /** {@inheritDoc} */
     public void forEachNode(final UnaryPredicate<Node<N, E>> predicate,
                             final UnaryProcedure<Node<N, E>> procedure)
     {
         if (predicate == null)
         {
             throw new IllegalArgumentException("predicate must not be null");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (Node<N, E> node : nodes)
         {
             if (predicate.test(node))
             {
                 procedure.run(node);
             }
         }
     }
 
     /** {@inheritDoc} */
     public void forEachNodeValue(final UnaryProcedure<? super N> procedure)
     {
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (N value : nodeValues())
         {
             procedure.run(value);
         }
     }
 
     /** {@inheritDoc} */
     public void forEachNodeValue(final UnaryPredicate<N> predicate, final UnaryProcedure<N> procedure)
     {
         if (predicate == null)
         {
             throw new IllegalArgumentException("predicate must not be null");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (N value : nodeValues())
         {
             if (predicate.test(value))
             {
                 procedure.run(value);
             }
         }
     }
 
     /** {@inheritDoc} */
     public int edgeCount()
     {
         return edges.size();
     }
 
     /** {@inheritDoc} */
     public Set<Edge<N, E>> edges()
     {
         return Collections.unmodifiableSet(edges);
     }
 
     /** {@inheritDoc} */
     public Collection<E> edgeValues()
     {
         List<E> values = new ArrayList<E>(edgeCount());
         for (Edge<N, E> edge : edges())
         {
             values.add(edge.getValue());
         }
         return Collections.unmodifiableList(values);
     }
 
     /** {@inheritDoc} */
     public <T> Map<Edge<N, E>, T> edgeMap(final T defaultValue)
     {
         Map<Edge<N, E>, T> map = new HashMap<Edge<N, E>, T>(edgeCount());
         for (Edge<N, E> edge : edges())
         {
             map.put(edge, defaultValue);
         }
         return new MapDecorator<Edge<N, E>, T>(map);
     }
 
     /** {@inheritDoc} */
     public void forEachEdge(final UnaryProcedure<Edge<N, E>> procedure)
     {
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (Edge<N, E> edge : edges)
         {
             procedure.run(edge);
         }
     }
 
     /** {@inheritDoc} */
     public void forEachEdge(final UnaryPredicate<Edge<N, E>> predicate,
                             final UnaryProcedure<Edge<N, E>> procedure)
     {
         if (predicate == null)
         {
             throw new IllegalArgumentException("predicate must not be null");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (Edge<N, E> edge : edges)
         {
             if (predicate.test(edge))
             {
                 procedure.run(edge);
             }
         }
     }
 
     /** {@inheritDoc} */
     public void forEachEdgeValue(final UnaryProcedure<? super E> procedure)
     {
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (E value : edgeValues())
         {
             procedure.run(value);
         }
     }
 
     /** {@inheritDoc} */
     public void forEachEdgeValue(final UnaryPredicate<E> predicate, final UnaryProcedure<E> procedure)
     {
         if (predicate == null)
         {
             throw new IllegalArgumentException("predicate must not be null");
         }
         if (procedure == null)
         {
             throw new IllegalArgumentException("procedure must not be null");
         }
         for (E value : edgeValues())
         {
             if (predicate.test(value))
             {
                 procedure.run(value);
             }
         }
     }
 
     /** {@inheritDoc} */
     public void clear()
     {
         nodes.clear();
         edges.clear();
     }
 
     /** {@inheritDoc} */
     public Node<N, E> createNode(final N value)
     {
         Node<N, E> node = new NodeImpl(value);
         nodes.add(node);
         return node;
     }
 
     /** {@inheritDoc} */
     public void remove(final Node<N, E> node)
     {
         if (node == null)
         {
             throw new IllegalArgumentException("node must not be null");
         }
         if (!nodes.contains(node))
         {
             throw new IllegalArgumentException("node must be contained in this graph");
         }
         nodes.remove(node);
         for (Edge<N, E> edge : edges)
         {
             if (edge.source().equals(node) || edge.target().equals(node))
             {
                 remove(edge);
             }
         }
     }
 
     /** {@inheritDoc} */
     public Edge<N, E> createEdge(final Node<N, E> source, final Node<N, E> target, final E value)
     {
         Edge<N, E> edge = new EdgeImpl(source, target, value);
         edges.add(edge);
         // safe cast since nodes must be created by this graph impl
         ((NodeImpl) source).addOutEdge(edge);
         ((NodeImpl) target).addInEdge(edge);
         return edge;
     }
 
     /** {@inheritDoc} */
     public void remove(final Edge<N, E> edge)
     {
         if (edge == null)
         {
             throw new IllegalArgumentException("edge must not be null");
         }
         if (!edges.contains(edge))
         {
             throw new IllegalArgumentException("edge must be contained in this graph");
         }
         edges.remove(edge);
         for (Node<N, E> node : nodes)
         {
             if (node.inEdges().contains(edge))
             {
                 // safe cast since nodes must be created by this graph impl
                 ((NodeImpl) node).removeInEdge(edge);
             }
             if (node.outEdges().contains(edge))
             {
                 // safe cast since nodes must be created by this graph impl
                 ((NodeImpl) node).removeOutEdge(edge);
             }
         }
     }
 
     /**
      * Node implementation.
      */
     private final class NodeImpl
         implements Node<N, E>
     {
         /** Value for this node. */
         private N value;
 
         /** Set of in edges. */
         private final Set<Edge<N, E>> inEdges = new HashSet<Edge<N, E>>();
 
         /** Set of out edges. */
         private final Set<Edge<N, E>> outEdges = new HashSet<Edge<N, E>>();
 
 
         /**
          * Create a new node with the specified value.
          *
          * @param value value
          */
         private NodeImpl(final N value)
         {
             this.value = value;
         }
 
 
         /** {@inheritDoc} */
         public N getValue()
         {
             return value;
         }
 
         /** {@inheritDoc} */
         public void setValue(final N value)
         {
             this.value = value;
         }
 
         /** {@inheritDoc} */
         public int degree()
         {
             return (inEdges.size() + outEdges.size());
         }
 
         /** {@inheritDoc} */
         public Set<Edge<N, E>> inEdges()
         {
             return Collections.unmodifiableSet(inEdges);
         }
 
         /** {@inheritDoc} */
         public Set<Edge<N, E>> outEdges()
         {
             return Collections.unmodifiableSet(outEdges);
         }
 
         /**
          * Add the specified edge to the set of in edges for this node.
          *
          * @param edge edge to add
          */
         private void addInEdge(final Edge<N, E> edge)
         {
             inEdges.add(edge);
         }
 
         /**
          * Remove the specified edge from the set of in edges for this node.
          *
          * @param edge edge to remove
          */
         private void removeInEdge(final Edge<N, E> edge)
         {
             inEdges.remove(edge);
         }
 
         /**
          * Add the specified edge to the set of out edges for this node.
          *
          * @param edge edge to add
          */
         private void addOutEdge(final Edge<N, E> edge)
         {
             outEdges.add(edge);
         }
 
         /**
          * Remove the specified edge from the set of out edges for this node.
          *
          * @param edge edge to remove
          */
         private void removeOutEdge(final Edge<N, E> edge)
         {
             outEdges.remove(edge);
         }
     }
 
     /**
      * Edge implementation.
      */
     private final class EdgeImpl
         implements Edge<N, E>
     {
         /** Value for this edge. */
         private E value;
 
         /** Source node. */
         private final Node<N, E> source;
 
         /** Target node. */
         private final Node<N, E> target;
 
 
         /**
          * Create a new edge with the specified source and target nodes and
          * the specified value.
          *
          * @param source source node, must not be null
          * @param target target node, must not be null
          * @param value value for this edge
          */
         private EdgeImpl(final Node<N, E> source, final Node<N, E> target, final E value)
         {
             if (source == null)
             {
                 throw new IllegalArgumentException("source must not be null");
             }
             if (target == null)
             {
                 throw new IllegalArgumentException("target must not be null");
             }
             if (!nodes.contains(source))
             {
                 throw new IllegalArgumentException("source must be contained in this graph");
             }
             if (!nodes.contains(target))
             {
                 throw new IllegalArgumentException("target must be contained in this graph");
             }
             this.value = value;
             this.source = source;
             this.target = target;
         }
 
 
         /** {@inheritDoc} */
         public E getValue()
         {
             return value;
         }
 
         /** {@inheritDoc} */
         public void setValue(final E value)
         {
             this.value = value;
         }
 
         /** {@inheritDoc} */
         public Node<N, E> source()
         {
             return source;
         }
 
         /** {@inheritDoc} */
         public Node<N, E> target()
         {
             return target;
         }
     }
 
     /**
      * Map decorator.
      */
     private static class MapDecorator<K, V>
         extends AbstractMapDecorator<K, V>
     {
 
         /**
          * Create a new map that decorates the specified map.
          *
          * @param map map to decorate, must not be null
          */
         MapDecorator(final Map<K, V> map)
         {
             super(map);
         }
 
 
         /** {@inheritDoc} */
         public Set<K> keySet()
         {
             return Collections.unmodifiableSet(super.keySet());
         }
     }
 }

1		/*
2
3		dsh-graph Directed graph interface and implementation.
4		Copyright (c) 2004-2013 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.ArrayList;
27		import java.util.Collection;
28		import java.util.Collections;
29		import java.util.HashMap;
30		import java.util.HashSet;
31		import java.util.List;
32		import java.util.Map;
33		import java.util.Set;
34
35		import org.dishevelled.functor.UnaryPredicate;
36		import org.dishevelled.functor.UnaryProcedure;
37
38		import org.dishevelled.graph.Edge;
39		import org.dishevelled.graph.Graph;
40		import org.dishevelled.graph.Node;
41
42		/**
43		* Directed graph implementation based on two HashSets.
44		*
45		* @param <N> node value type
46		* @param <E> edge value type
47		* @author Michael Heuer
48		* @version $Revision$ $Date$
49		*/
50	296	public final class GraphImpl<N, E>
51		implements Graph<N, E>
52		{
53		/** Set of nodes. */
54		private final Set<Node<N, E>> nodes;
55
56		/** Set of edges. */
57		private final Set<Edge<N, E>> edges;
58
59
60		/**
61		* Create a new directed graph.
62		*/
63		public GraphImpl()
64	189	{
65	189	nodes = new HashSet<Node<N, E>>();
66	189	edges = new HashSet<Edge<N, E>>();
67	189	}
68
69		/**
70		* Create a new directed graph with the specified initial node
71		* and edge capacities.
72		*
73		* @param nodeCapacity initial node capacity, must be <code>>= 0</code>
74		* @param edgeCapacity initial edge capacity, must be <code>>= 0</code>
75		*/
76		public GraphImpl(final int nodeCapacity, final int edgeCapacity)
77	8	{
78	8	nodes = new HashSet<Node<N, E>>(nodeCapacity);
79	4	edges = new HashSet<Edge<N, E>>(edgeCapacity);
80	2	}
81
82		/**
83		* Create a new directed graph with the same structure and same node
84		* and edge values as the specified graph (copy constructor).
85		*
86		* @param graph graph to copy, must not be null
87		*/
88		public GraphImpl(final Graph<N, E> graph)
89	6	{
90	6	if (graph == null)
91		{
92	2	throw new IllegalArgumentException("graph must not be null");
93		}
94	4	if (graph.isEmpty())
95		{
96	2	nodes = new HashSet<Node<N, E>>();
97	2	edges = new HashSet<Edge<N, E>>();
98		}
99		else
100		{
101	2	nodes = new HashSet<Node<N, E>>(graph.nodeCount());
102	2	edges = new HashSet<Edge<N, E>>(graph.edgeCount());
103	2	Map<Node<N, E>, Node<N, E>> nodeMap = graph.nodeMap(null);
104	2	for (Map.Entry<Node<N, E>, Node<N, E>> entry : nodeMap.entrySet())
105		{
106	6	Node<N, E> node = createNode(entry.getKey().getValue());
107	6	entry.setValue(node);
108	6	}
109	2	for (Edge<? extends N, ? extends E> edge : graph.edges())
110		{
111	13	Node<N, E> source = nodeMap.get(edge.source());
112	13	Node<N, E> target = nodeMap.get(edge.target());
113	13	createEdge(source, target, edge.getValue());
114	13	}
115		}
116	4	}
117
118		/** {@inheritDoc} */
119		public boolean isEmpty()
120		{
121	8	return (nodes.isEmpty() && edges.isEmpty());
122		}
123
124		/** {@inheritDoc} */
125		public int nodeCount()
126		{
127	208	return nodes.size();
128		}
129
130		/** {@inheritDoc} */
131		public Set<Node<N, E>> nodes()
132		{
133	97	return Collections.unmodifiableSet(nodes);
134		}
135
136		/** {@inheritDoc} */
137		public Collection<N> nodeValues()
138		{
139	60	List<N> values = new ArrayList<N>(nodeCount());
140	60	for (Node<N, E> node : nodes)
141		{
142	84	values.add(node.getValue());
143	84	}
144	60	return Collections.unmodifiableList(values);
145		}
146
147		/** {@inheritDoc} */
148		public <T> Map<Node<N, E>, T> nodeMap(final T defaultValue)
149		{
150	78	Map<Node<N, E>, T> map = new HashMap<Node<N, E>, T>(nodeCount());
151	78	for (Node<N, E> node : nodes)
152		{
153	122	map.put(node, defaultValue);
154	122	}
155	78	return new MapDecorator<Node<N, E>, T>(map);
156		}
157
158		/** {@inheritDoc} */
159		public void forEachNode(final UnaryProcedure<Node<N, E>> procedure)
160		{
161	12	if (procedure == null)
162		{
163	6	throw new IllegalArgumentException("procedure must not be null");
164		}
165	6	for (Node<N, E> node : nodes)
166		{
167	6	procedure.run(node);
168	6	}
169	6	}
170
171		/** {@inheritDoc} */
172		public void forEachNode(final UnaryPredicate<Node<N, E>> predicate,
173		final UnaryProcedure<Node<N, E>> procedure)
174		{
175	24	if (predicate == null)
176		{
177	12	throw new IllegalArgumentException("predicate must not be null");
178		}
179	12	if (procedure == null)
180		{
181	6	throw new IllegalArgumentException("procedure must not be null");
182		}
183	6	for (Node<N, E> node : nodes)
184		{
185	6	if (predicate.test(node))
186		{
187	6	procedure.run(node);
188		}
189	6	}
190	6	}
191
192		/** {@inheritDoc} */
193		public void forEachNodeValue(final UnaryProcedure<? super N> procedure)
194		{
195	18	if (procedure == null)
196		{
197	6	throw new IllegalArgumentException("procedure must not be null");
198		}
199	12	for (N value : nodeValues())
200		{
201	12	procedure.run(value);
202	12	}
203	12	}
204
205		/** {@inheritDoc} */
206		public void forEachNodeValue(final UnaryPredicate<N> predicate, final UnaryProcedure<N> procedure)
207		{
208	24	if (predicate == null)
209		{
210	12	throw new IllegalArgumentException("predicate must not be null");
211		}
212	12	if (procedure == null)
213		{
214	6	throw new IllegalArgumentException("procedure must not be null");
215		}
216	6	for (N value : nodeValues())
217		{
218	6	if (predicate.test(value))
219		{
220	6	procedure.run(value);
221		}
222	6	}
223	6	}
224
225		/** {@inheritDoc} */
226		public int edgeCount()
227		{
228	178	return edges.size();
229		}
230
231		/** {@inheritDoc} */
232		public Set<Edge<N, E>> edges()
233		{
234	191	return Collections.unmodifiableSet(edges);
235		}
236
237		/** {@inheritDoc} */
238		public Collection<E> edgeValues()
239		{
240	60	List<E> values = new ArrayList<E>(edgeCount());
241	60	for (Edge<N, E> edge : edges())
242		{
243	42	values.add(edge.getValue());
244	42	}
245	60	return Collections.unmodifiableList(values);
246		}
247
248		/** {@inheritDoc} */
249		public <T> Map<Edge<N, E>, T> edgeMap(final T defaultValue)
250		{
251	57	Map<Edge<N, E>, T> map = new HashMap<Edge<N, E>, T>(edgeCount());
252	57	for (Edge<N, E> edge : edges())
253		{
254	36	map.put(edge, defaultValue);
255	36	}
256	57	return new MapDecorator<Edge<N, E>, T>(map);
257		}
258
259		/** {@inheritDoc} */
260		public void forEachEdge(final UnaryProcedure<Edge<N, E>> procedure)
261		{
262	12	if (procedure == null)
263		{
264	6	throw new IllegalArgumentException("procedure must not be null");
265		}
266	6	for (Edge<N, E> edge : edges)
267		{
268	3	procedure.run(edge);
269	3	}
270	6	}
271
272		/** {@inheritDoc} */
273		public void forEachEdge(final UnaryPredicate<Edge<N, E>> predicate,
274		final UnaryProcedure<Edge<N, E>> procedure)
275		{
276	24	if (predicate == null)
277		{
278	12	throw new IllegalArgumentException("predicate must not be null");
279		}
280	12	if (procedure == null)
281		{
282	6	throw new IllegalArgumentException("procedure must not be null");
283		}
284	6	for (Edge<N, E> edge : edges)
285		{
286	3	if (predicate.test(edge))
287		{
288	3	procedure.run(edge);
289		}
290	3	}
291	6	}
292
293		/** {@inheritDoc} */
294		public void forEachEdgeValue(final UnaryProcedure<? super E> procedure)
295		{
296	18	if (procedure == null)
297		{
298	6	throw new IllegalArgumentException("procedure must not be null");
299		}
300	12	for (E value : edgeValues())
301		{
302	6	procedure.run(value);
303	6	}
304	12	}
305
306		/** {@inheritDoc} */
307		public void forEachEdgeValue(final UnaryPredicate<E> predicate, final UnaryProcedure<E> procedure)
308		{
309	24	if (predicate == null)
310		{
311	12	throw new IllegalArgumentException("predicate must not be null");
312		}
313	12	if (procedure == null)
314		{
315	6	throw new IllegalArgumentException("procedure must not be null");
316		}
317	6	for (E value : edgeValues())
318		{
319	3	if (predicate.test(value))
320		{
321	3	procedure.run(value);
322		}
323	3	}
324	6	}
325
326		/** {@inheritDoc} */
327		public void clear()
328		{
329	8	nodes.clear();
330	8	edges.clear();
331	8	}
332
333		/** {@inheritDoc} */
334		public Node<N, E> createNode(final N value)
335		{
336	264	Node<N, E> node = new NodeImpl(value);
337	264	nodes.add(node);
338	264	return node;
339		}
340
341		/** {@inheritDoc} */
342		public void remove(final Node<N, E> node)
343		{
344	6	if (node == null)
345		{
346	2	throw new IllegalArgumentException("node must not be null");
347		}
348	4	if (!nodes.contains(node))
349		{
350	2	throw new IllegalArgumentException("node must be contained in this graph");
351		}
352	2	nodes.remove(node);
353	2	for (Edge<N, E> edge : edges)
354		{
355	2	if (edge.source().equals(node) \|\| edge.target().equals(node))
356		{
357	2	remove(edge);
358		}
359	2	}
360	2	}
361
362		/** {@inheritDoc} */
363		public Edge<N, E> createEdge(final Node<N, E> source, final Node<N, E> target, final E value)
364		{
365	156	Edge<N, E> edge = new EdgeImpl(source, target, value);
366	144	edges.add(edge);
367		// safe cast since nodes must be created by this graph impl
368	144	((NodeImpl) source).addOutEdge(edge);
369	144	((NodeImpl) target).addInEdge(edge);
370	144	return edge;
371		}
372
373		/** {@inheritDoc} */
374		public void remove(final Edge<N, E> edge)
375		{
376	8	if (edge == null)
377		{
378	2	throw new IllegalArgumentException("edge must not be null");
379		}
380	6	if (!edges.contains(edge))
381		{
382	2	throw new IllegalArgumentException("edge must be contained in this graph");
383		}
384	4	edges.remove(edge);
385	4	for (Node<N, E> node : nodes)
386		{
387	6	if (node.inEdges().contains(edge))
388		{
389		// safe cast since nodes must be created by this graph impl
390	3	((NodeImpl) node).removeInEdge(edge);
391		}
392	6	if (node.outEdges().contains(edge))
393		{
394		// safe cast since nodes must be created by this graph impl
395	3	((NodeImpl) node).removeOutEdge(edge);
396		}
397	6	}
398	4	}
399
400		/**
401		* Node implementation.
402		*/
403	558	private final class NodeImpl
404		implements Node<N, E>
405		{
406		/** Value for this node. */
407		private N value;
408
409		/** Set of in edges. */
410	264	private final Set<Edge<N, E>> inEdges = new HashSet<Edge<N, E>>();
411
412		/** Set of out edges. */
413	264	private final Set<Edge<N, E>> outEdges = new HashSet<Edge<N, E>>();
414
415
416		/**
417		* Create a new node with the specified value.
418		*
419		* @param value value
420		*/
421		private NodeImpl(final N value)
422	264	{
423	264	this.value = value;
424	264	}
425
426
427		/** {@inheritDoc} */
428		public N getValue()
429		{
430	106	return value;
431		}
432
433		/** {@inheritDoc} */
434		public void setValue(final N value)
435		{
436	12	this.value = value;
437	12	}
438
439		/** {@inheritDoc} */
440		public int degree()
441		{
442	6	return (inEdges.size() + outEdges.size());
443		}
444
445		/** {@inheritDoc} */
446		public Set<Edge<N, E>> inEdges()
447		{
448	33	return Collections.unmodifiableSet(inEdges);
449		}
450
451		/** {@inheritDoc} */
452		public Set<Edge<N, E>> outEdges()
453		{
454	37	return Collections.unmodifiableSet(outEdges);
455		}
456
457		/**
458		* Add the specified edge to the set of in edges for this node.
459		*
460		* @param edge edge to add
461		*/
462		private void addInEdge(final Edge<N, E> edge)
463		{
464	144	inEdges.add(edge);
465	144	}
466
467		/**
468		* Remove the specified edge from the set of in edges for this node.
469		*
470		* @param edge edge to remove
471		*/
472		private void removeInEdge(final Edge<N, E> edge)
473		{
474	3	inEdges.remove(edge);
475	3	}
476
477		/**
478		* Add the specified edge to the set of out edges for this node.
479		*
480		* @param edge edge to add
481		*/
482		private void addOutEdge(final Edge<N, E> edge)
483		{
484	144	outEdges.add(edge);
485	144	}
486
487		/**
488		* Remove the specified edge from the set of out edges for this node.
489		*
490		* @param edge edge to remove
491		*/
492		private void removeOutEdge(final Edge<N, E> edge)
493		{
494	3	outEdges.remove(edge);
495	3	}
496		}
497
498		/**
499		* Edge implementation.
500		*/
501	156	private final class EdgeImpl
502		implements Edge<N, E>
503		{
504		/** Value for this edge. */
505		private E value;
506
507		/** Source node. */
508		private final Node<N, E> source;
509
510		/** Target node. */
511		private final Node<N, E> target;
512
513
514		/**
515		* Create a new edge with the specified source and target nodes and
516		* the specified value.
517		*
518		* @param source source node, must not be null
519		* @param target target node, must not be null
520		* @param value value for this edge
521		*/
522		private EdgeImpl(final Node<N, E> source, final Node<N, E> target, final E value)
523	156	{
524	156	if (source == null)
525		{
526	4	throw new IllegalArgumentException("source must not be null");
527		}
528	152	if (target == null)
529		{
530	2	throw new IllegalArgumentException("target must not be null");
531		}
532	150	if (!nodes.contains(source))
533		{
534	4	throw new IllegalArgumentException("source must be contained in this graph");
535		}
536	146	if (!nodes.contains(target))
537		{
538	2	throw new IllegalArgumentException("target must be contained in this graph");
539		}
540	144	this.value = value;
541	144	this.source = source;
542	144	this.target = target;
543	144	}
544
545
546		/** {@inheritDoc} */
547		public E getValue()
548		{
549	65	return value;
550		}
551
552		/** {@inheritDoc} */
553		public void setValue(final E value)
554		{
555	6	this.value = value;
556	6	}
557
558		/** {@inheritDoc} */
559		public Node<N, E> source()
560		{
561	26	return source;
562		}
563
564		/** {@inheritDoc} */
565		public Node<N, E> target()
566		{
567	27	return target;
568		}
569		}
570
571		/**
572		* Map decorator.
573		*/
574		private static class MapDecorator<K, V>
575		extends AbstractMapDecorator<K, V>
576		{
577
578		/**
579		* Create a new map that decorates the specified map.
580		*
581		* @param map map to decorate, must not be null
582		*/
583		MapDecorator(final Map<K, V> map)
584		{
585	135	super(map);
586	135	}
587
588
589		/** {@inheritDoc} */
590		public Set<K> keySet()
591		{
592	24	return Collections.unmodifiableSet(super.keySet());
593		}
594		}
595		}