Coverage Report

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

Classes in this File

Line Coverage

Branch Coverage

Complexity

SparseGraph

36%

54/146

28%

24/84

SparseGraph$1

100%

2/2

N/A

 /*
  * Created on Apr 15, 2007
  *
  * Copyright (c) 2007, the JUNG Project and the Regents of the University 
  * of California
  * All rights reserved.
  *
  * This software is open-source under the BSD license; see either
  * "license.txt" or
  * http://jung.sourceforge.net/license.txt for a description.
  */
 package edu.uci.ics.jung.graph;
 
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 
 import org.apache.commons.collections15.Factory;
 
 import edu.uci.ics.jung.graph.util.EdgeType;
 import edu.uci.ics.jung.graph.util.Pair;
 
 /**
  * An implementation of <code>Graph</code> that is suitable for sparse graphs and
  * permits both directed and undirected edges.
  */
 @SuppressWarnings("serial")
 public class SparseGraph<V,E> 
     extends AbstractGraph<V,E> 
     implements Graph<V,E>
 {
     /**
      * Returns a {@code Factory} that creates an instance of this graph type.
      * @param <V> the vertex type for the graph factory
      * @param <E> the edge type for the graph factory
      */
     public static <V,E> Factory<Graph<V,E>> getFactory() 
     { 
         return new Factory<Graph<V,E>> () 
         {
             public Graph<V,E> create() 
             {
                 return new SparseGraph<V,E>();
             }
         };
     }
 
     protected static final int INCOMING = 0;
     protected static final int OUTGOING = 1;
     protected static final int INCIDENT = 2;
     
     protected Map<V, Map<V,E>[]> vertex_maps; // Map of vertices to adjacency maps of vertices to {incoming, outgoing, incident} edges
     protected Map<E, Pair<V>> directed_edges;    // Map of directed edges to incident vertex sets
     protected Map<E, Pair<V>> undirected_edges;    // Map of undirected edges to incident vertex sets
     
     /**
      * Creates an instance.
      */
     public SparseGraph()
     {
         vertex_maps = new HashMap<V, Map<V,E>[]>();
         directed_edges = new HashMap<E, Pair<V>>();
         undirected_edges = new HashMap<E, Pair<V>>();
     }
     
     @Override
     public E findEdge(V v1, V v2)
     {
         if (!containsVertex(v1) || !containsVertex(v2))
             return null;
         E edge = vertex_maps.get(v1)[OUTGOING].get(v2);
         if (edge == null)
             edge = vertex_maps.get(v1)[INCIDENT].get(v2);
         return edge;
     }
 
     @Override
     public Collection<E> findEdgeSet(V v1, V v2)
     {
         if (!containsVertex(v1) || !containsVertex(v2))
             return null;
         Collection<E> edges = new ArrayList<E>(2);
         E e1 = vertex_maps.get(v1)[OUTGOING].get(v2);
         if (e1 != null)
             edges.add(e1);
         E e2 = vertex_maps.get(v1)[INCIDENT].get(v2);
         if (e1 != null)
             edges.add(e2);
         return edges;
     }
     
     @Override
     public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
     {
         Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
         if (new_endpoints == null)
             return false;
         
         V v1 = new_endpoints.getFirst();
         V v2 = new_endpoints.getSecond();
         
         // undirected edges and directed edges are not considered to be parallel to each other,
         // so as long as anything that's returned by findEdge is not of the same type as
         // edge, we're fine
         E connection = findEdge(v1, v2);
         if (connection != null && getEdgeType(connection) == edgeType)
             return false;
 
         if (!containsVertex(v1))
             this.addVertex(v1);
         
         if (!containsVertex(v2))
             this.addVertex(v2);
         
         // map v1 to <v2, edge> and vice versa
         if (edgeType == EdgeType.DIRECTED)
         {
             vertex_maps.get(v1)[OUTGOING].put(v2, edge);
             vertex_maps.get(v2)[INCOMING].put(v1, edge);
             directed_edges.put(edge, new_endpoints);
         }
         else
         {
             vertex_maps.get(v1)[INCIDENT].put(v2, edge);
             vertex_maps.get(v2)[INCIDENT].put(v1, edge);
             undirected_edges.put(edge, new_endpoints);
         }
         
         return true;
     }
 
     
     
     public Collection<E> getInEdges(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         
         // combine directed inedges and undirected
         Collection<E> in = new HashSet<E>(vertex_maps.get(vertex)[INCOMING].values());
         in.addAll(vertex_maps.get(vertex)[INCIDENT].values());
         return Collections.unmodifiableCollection(in);
     }
 
     public Collection<E> getOutEdges(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         
         // combine directed outedges and undirected
         Collection<E> out = new HashSet<E>(vertex_maps.get(vertex)[OUTGOING].values());
         out.addAll(vertex_maps.get(vertex)[INCIDENT].values());
         return Collections.unmodifiableCollection(out);
     }
 
     public Collection<V> getPredecessors(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         
         // consider directed inedges and undirected
         Collection<V> preds = new HashSet<V>(vertex_maps.get(vertex)[INCOMING].keySet());
         preds.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
         return Collections.unmodifiableCollection(preds);
     }
 
     public Collection<V> getSuccessors(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         
         // consider directed outedges and undirected
         Collection<V> succs = new HashSet<V>(vertex_maps.get(vertex)[OUTGOING].keySet());
         succs.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
         return Collections.unmodifiableCollection(succs);
     }
 
     public Collection<E> getEdges(EdgeType edgeType)
     {
         if (edgeType == EdgeType.DIRECTED)
             return Collections.unmodifiableCollection(directed_edges.keySet());
         else if (edgeType == EdgeType.UNDIRECTED)
             return Collections.unmodifiableCollection(undirected_edges.keySet());
         else
             return null;
     }
 
     public Pair<V> getEndpoints(E edge)
     {
         Pair<V> endpoints;
         endpoints = directed_edges.get(edge);
         if (endpoints == null)
             return undirected_edges.get(edge);
         else
             return endpoints;
     }
 
     public EdgeType getEdgeType(E edge)
     {
         if (directed_edges.containsKey(edge))
             return EdgeType.DIRECTED;
         else if (undirected_edges.containsKey(edge))
             return EdgeType.UNDIRECTED;
         else
             return null;
     }
 
     public V getSource(E directed_edge)
     {
         if (getEdgeType(directed_edge) == EdgeType.DIRECTED)
             return directed_edges.get(directed_edge).getFirst();
         else
             return null;
     }
 
     public V getDest(E directed_edge)
     {
         if (getEdgeType(directed_edge) == EdgeType.DIRECTED)
             return directed_edges.get(directed_edge).getSecond();
         else
             return null;
     }
 
     public boolean isSource(V vertex, E edge)
     {
         if (!containsVertex(vertex) || !containsEdge(edge))
             return false;
         
         V source = getSource(edge);
         if (source != null)
             return source.equals(vertex);
         else
             return false;
     }
 
     public boolean isDest(V vertex, E edge)
     {
         if (!containsVertex(vertex) || !containsEdge(edge))
             return false;
         
         V dest = getDest(edge);
         if (dest != null)
             return dest.equals(vertex);
         else
             return false;
     }
 
     public Collection<E> getEdges()
     {
         Collection<E> edges = new ArrayList<E>(directed_edges.keySet());
         edges.addAll(undirected_edges.keySet());
         return Collections.unmodifiableCollection(edges);
     }
 
     public Collection<V> getVertices()
     {
         return Collections.unmodifiableCollection(vertex_maps.keySet());
     }
 
     public boolean containsVertex(V vertex)
     {
         return vertex_maps.containsKey(vertex);
     }
 
     public boolean containsEdge(E edge)
     {
         return directed_edges.containsKey(edge) || undirected_edges.containsKey(edge);
     }
 
     public int getEdgeCount()
     {
         return directed_edges.size() + undirected_edges.size();
     }
 
     public int getVertexCount()
     {
         return vertex_maps.size();
     }
 
     public Collection<V> getNeighbors(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         // consider directed edges and undirected edges
         Collection<V> neighbors = new HashSet<V>(vertex_maps.get(vertex)[INCOMING].keySet());
         neighbors.addAll(vertex_maps.get(vertex)[OUTGOING].keySet());
         neighbors.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
         return Collections.unmodifiableCollection(neighbors);
     }
 
     public Collection<E> getIncidentEdges(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         Collection<E> incident = new HashSet<E>(vertex_maps.get(vertex)[INCOMING].values());
         incident.addAll(vertex_maps.get(vertex)[OUTGOING].values());
         incident.addAll(vertex_maps.get(vertex)[INCIDENT].values());
         return Collections.unmodifiableCollection(incident);
     }
 
     @SuppressWarnings("unchecked")
     public boolean addVertex(V vertex)
     {
         if(vertex == null) {
             throw new IllegalArgumentException("vertex may not be null");
         }
         if (!containsVertex(vertex)) {
             vertex_maps.put(vertex, new HashMap[]{new HashMap<V,E>(), new HashMap<V,E>(), new HashMap<V,E>()});
             return true;
         } else {
             return false;
         }
     }
 
     public boolean removeVertex(V vertex)
     {
         if (!containsVertex(vertex))
             return false;
         
         // copy to avoid concurrent modification in removeEdge
         Collection<E> incident = new ArrayList<E>(getIncidentEdges(vertex));
         
         for (E edge : incident)
             removeEdge(edge);
         
         vertex_maps.remove(vertex);
         
         return true;
     }
 
     public boolean removeEdge(E edge)
     {
         if (!containsEdge(edge)) 
             return false;
         
         Pair<V> endpoints = getEndpoints(edge);
         V v1 = endpoints.getFirst();
         V v2 = endpoints.getSecond();
         
         // remove edge from incident vertices' adjacency maps
         if (getEdgeType(edge) == EdgeType.DIRECTED)
         {
             vertex_maps.get(v1)[OUTGOING].remove(v2);
             vertex_maps.get(v2)[INCOMING].remove(v1);
             directed_edges.remove(edge);
         }
         else
         {
             vertex_maps.get(v1)[INCIDENT].remove(v2);
             vertex_maps.get(v2)[INCIDENT].remove(v1);
             undirected_edges.remove(edge);
         }
 
         return true;
     }
     
     public int getEdgeCount(EdgeType edge_type)
     {
         if (edge_type == EdgeType.DIRECTED)
             return directed_edges.size();
         if (edge_type == EdgeType.UNDIRECTED)
             return undirected_edges.size();
         return 0;
     }
 
         public EdgeType getDefaultEdgeType() 
         {
                 return EdgeType.UNDIRECTED;
         }
 }

1		/*
2		* Created on Apr 15, 2007
3		*
4		* Copyright (c) 2007, 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.HashSet;
19		import java.util.Map;
20
21		import org.apache.commons.collections15.Factory;
22
23		import edu.uci.ics.jung.graph.util.EdgeType;
24		import edu.uci.ics.jung.graph.util.Pair;
25
26		/**
27		* An implementation of <code>Graph</code> that is suitable for sparse graphs and
28		* permits both directed and undirected edges.
29		*/
30		@SuppressWarnings("serial")
31		public class SparseGraph<V,E>
32		extends AbstractGraph<V,E>
33		implements Graph<V,E>
34		{
35		/**
36		* Returns a {@code Factory} that creates an instance of this graph type.
37		* @param <V> the vertex type for the graph factory
38		* @param <E> the edge type for the graph factory
39		*/
40		public static <V,E> Factory<Graph<V,E>> getFactory()
41		{
42	2	return new Factory<Graph<V,E>> ()
43		{
44	6	public Graph<V,E> create()
45		{
46	4	return new SparseGraph<V,E>();
47		}
48		};
49		}
50
51		protected static final int INCOMING = 0;
52		protected static final int OUTGOING = 1;
53		protected static final int INCIDENT = 2;
54
55		protected Map<V, Map<V,E>[]> vertex_maps; // Map of vertices to adjacency maps of vertices to {incoming, outgoing, incident} edges
56		protected Map<E, Pair<V>> directed_edges; // Map of directed edges to incident vertex sets
57		protected Map<E, Pair<V>> undirected_edges; // Map of undirected edges to incident vertex sets
58
59		/**
60		* Creates an instance.
61		*/
62		public SparseGraph()
63	6	{
64	6	vertex_maps = new HashMap<V, Map<V,E>[]>();
65	6	directed_edges = new HashMap<E, Pair<V>>();
66	6	undirected_edges = new HashMap<E, Pair<V>>();
67	6	}
68
69		@Override
70		public E findEdge(V v1, V v2)
71		{
72	6	if (!containsVertex(v1) \|\| !containsVertex(v2))
73	2	return null;
74	4	E edge = vertex_maps.get(v1)[OUTGOING].get(v2);
75	4	if (edge == null)
76	4	edge = vertex_maps.get(v1)[INCIDENT].get(v2);
77	4	return edge;
78		}
79
80		@Override
81		public Collection<E> findEdgeSet(V v1, V v2)
82		{
83	0	if (!containsVertex(v1) \|\| !containsVertex(v2))
84	0	return null;
85	0	Collection<E> edges = new ArrayList<E>(2);
86	0	E e1 = vertex_maps.get(v1)[OUTGOING].get(v2);
87	0	if (e1 != null)
88	0	edges.add(e1);
89	0	E e2 = vertex_maps.get(v1)[INCIDENT].get(v2);
90	0	if (e1 != null)
91	0	edges.add(e2);
92	0	return edges;
93		}
94
95		@Override
96		public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
97		{
98	12	Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
99	10	if (new_endpoints == null)
100	4	return false;
101
102	6	V v1 = new_endpoints.getFirst();
103	6	V v2 = new_endpoints.getSecond();
104
105		// undirected edges and directed edges are not considered to be parallel to each other,
106		// so as long as anything that's returned by findEdge is not of the same type as
107		// edge, we're fine
108	6	E connection = findEdge(v1, v2);
109	6	if (connection != null && getEdgeType(connection) == edgeType)
110	0	return false;
111
112	6	if (!containsVertex(v1))
113	2	this.addVertex(v1);
114
115	6	if (!containsVertex(v2))
116	2	this.addVertex(v2);
117
118		// map v1 to <v2, edge> and vice versa
119	6	if (edgeType == EdgeType.DIRECTED)
120		{
121	0	vertex_maps.get(v1)[OUTGOING].put(v2, edge);
122	0	vertex_maps.get(v2)[INCOMING].put(v1, edge);
123	0	directed_edges.put(edge, new_endpoints);
124		}
125		else
126		{
127	6	vertex_maps.get(v1)[INCIDENT].put(v2, edge);
128	6	vertex_maps.get(v2)[INCIDENT].put(v1, edge);
129	6	undirected_edges.put(edge, new_endpoints);
130		}
131
132	6	return true;
133		}
134
135
136
137		public Collection<E> getInEdges(V vertex)
138		{
139	0	if (!containsVertex(vertex))
140	0	return null;
141
142		// combine directed inedges and undirected
143	0	Collection<E> in = new HashSet<E>(vertex_maps.get(vertex)[INCOMING].values());
144	0	in.addAll(vertex_maps.get(vertex)[INCIDENT].values());
145	0	return Collections.unmodifiableCollection(in);
146		}
147
148		public Collection<E> getOutEdges(V vertex)
149		{
150	0	if (!containsVertex(vertex))
151	0	return null;
152
153		// combine directed outedges and undirected
154	0	Collection<E> out = new HashSet<E>(vertex_maps.get(vertex)[OUTGOING].values());
155	0	out.addAll(vertex_maps.get(vertex)[INCIDENT].values());
156	0	return Collections.unmodifiableCollection(out);
157		}
158
159		public Collection<V> getPredecessors(V vertex)
160		{
161	0	if (!containsVertex(vertex))
162	0	return null;
163
164		// consider directed inedges and undirected
165	0	Collection<V> preds = new HashSet<V>(vertex_maps.get(vertex)[INCOMING].keySet());
166	0	preds.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
167	0	return Collections.unmodifiableCollection(preds);
168		}
169
170		public Collection<V> getSuccessors(V vertex)
171		{
172	0	if (!containsVertex(vertex))
173	0	return null;
174
175		// consider directed outedges and undirected
176	0	Collection<V> succs = new HashSet<V>(vertex_maps.get(vertex)[OUTGOING].keySet());
177	0	succs.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
178	0	return Collections.unmodifiableCollection(succs);
179		}
180
181		public Collection<E> getEdges(EdgeType edgeType)
182		{
183	0	if (edgeType == EdgeType.DIRECTED)
184	0	return Collections.unmodifiableCollection(directed_edges.keySet());
185	0	else if (edgeType == EdgeType.UNDIRECTED)
186	0	return Collections.unmodifiableCollection(undirected_edges.keySet());
187		else
188	0	return null;
189		}
190
191		public Pair<V> getEndpoints(E edge)
192		{
193		Pair<V> endpoints;
194	8	endpoints = directed_edges.get(edge);
195	8	if (endpoints == null)
196	8	return undirected_edges.get(edge);
197		else
198	0	return endpoints;
199		}
200
201		public EdgeType getEdgeType(E edge)
202		{
203	2	if (directed_edges.containsKey(edge))
204	0	return EdgeType.DIRECTED;
205	2	else if (undirected_edges.containsKey(edge))
206	2	return EdgeType.UNDIRECTED;
207		else
208	0	return null;
209		}
210
211		public V getSource(E directed_edge)
212		{
213	0	if (getEdgeType(directed_edge) == EdgeType.DIRECTED)
214	0	return directed_edges.get(directed_edge).getFirst();
215		else
216	0	return null;
217		}
218
219		public V getDest(E directed_edge)
220		{
221	0	if (getEdgeType(directed_edge) == EdgeType.DIRECTED)
222	0	return directed_edges.get(directed_edge).getSecond();
223		else
224	0	return null;
225		}
226
227		public boolean isSource(V vertex, E edge)
228		{
229	0	if (!containsVertex(vertex) \|\| !containsEdge(edge))
230	0	return false;
231
232	0	V source = getSource(edge);
233	0	if (source != null)
234	0	return source.equals(vertex);
235		else
236	0	return false;
237		}
238
239		public boolean isDest(V vertex, E edge)
240		{
241	0	if (!containsVertex(vertex) \|\| !containsEdge(edge))
242	0	return false;
243
244	0	V dest = getDest(edge);
245	0	if (dest != null)
246	0	return dest.equals(vertex);
247		else
248	0	return false;
249		}
250
251		public Collection<E> getEdges()
252		{
253	0	Collection<E> edges = new ArrayList<E>(directed_edges.keySet());
254	0	edges.addAll(undirected_edges.keySet());
255	0	return Collections.unmodifiableCollection(edges);
256		}
257
258		public Collection<V> getVertices()
259		{
260	0	return Collections.unmodifiableCollection(vertex_maps.keySet());
261		}
262
263		public boolean containsVertex(V vertex)
264		{
265	38	return vertex_maps.containsKey(vertex);
266		}
267
268		public boolean containsEdge(E edge)
269		{
270	18	return directed_edges.containsKey(edge) \|\| undirected_edges.containsKey(edge);
271		}
272
273		public int getEdgeCount()
274		{
275	6	return directed_edges.size() + undirected_edges.size();
276		}
277
278		public int getVertexCount()
279		{
280	10	return vertex_maps.size();
281		}
282
283		public Collection<V> getNeighbors(V vertex)
284		{
285	0	if (!containsVertex(vertex))
286	0	return null;
287		// consider directed edges and undirected edges
288	0	Collection<V> neighbors = new HashSet<V>(vertex_maps.get(vertex)[INCOMING].keySet());
289	0	neighbors.addAll(vertex_maps.get(vertex)[OUTGOING].keySet());
290	0	neighbors.addAll(vertex_maps.get(vertex)[INCIDENT].keySet());
291	0	return Collections.unmodifiableCollection(neighbors);
292		}
293
294		public Collection<E> getIncidentEdges(V vertex)
295		{
296	0	if (!containsVertex(vertex))
297	0	return null;
298	0	Collection<E> incident = new HashSet<E>(vertex_maps.get(vertex)[INCOMING].values());
299	0	incident.addAll(vertex_maps.get(vertex)[OUTGOING].values());
300	0	incident.addAll(vertex_maps.get(vertex)[INCIDENT].values());
301	0	return Collections.unmodifiableCollection(incident);
302		}
303
304		@SuppressWarnings("unchecked")
305		public boolean addVertex(V vertex)
306		{
307	14	if(vertex == null) {
308	2	throw new IllegalArgumentException("vertex may not be null");
309		}
310	12	if (!containsVertex(vertex)) {
311	10	vertex_maps.put(vertex, new HashMap[]{new HashMap<V,E>(), new HashMap<V,E>(), new HashMap<V,E>()});
312	10	return true;
313		} else {
314	2	return false;
315		}
316		}
317
318		public boolean removeVertex(V vertex)
319		{
320	0	if (!containsVertex(vertex))
321	0	return false;
322
323		// copy to avoid concurrent modification in removeEdge
324	0	Collection<E> incident = new ArrayList<E>(getIncidentEdges(vertex));
325
326	0	for (E edge : incident)
327	0	removeEdge(edge);
328
329	0	vertex_maps.remove(vertex);
330
331	0	return true;
332		}
333
334		public boolean removeEdge(E edge)
335		{
336	2	if (!containsEdge(edge))
337	0	return false;
338
339	2	Pair<V> endpoints = getEndpoints(edge);
340	2	V v1 = endpoints.getFirst();
341	2	V v2 = endpoints.getSecond();
342
343		// remove edge from incident vertices' adjacency maps
344	2	if (getEdgeType(edge) == EdgeType.DIRECTED)
345		{
346	0	vertex_maps.get(v1)[OUTGOING].remove(v2);
347	0	vertex_maps.get(v2)[INCOMING].remove(v1);
348	0	directed_edges.remove(edge);
349		}
350		else
351		{
352	2	vertex_maps.get(v1)[INCIDENT].remove(v2);
353	2	vertex_maps.get(v2)[INCIDENT].remove(v1);
354	2	undirected_edges.remove(edge);
355		}
356
357	2	return true;
358		}
359
360		public int getEdgeCount(EdgeType edge_type)
361		{
362	0	if (edge_type == EdgeType.DIRECTED)
363	0	return directed_edges.size();
364	0	if (edge_type == EdgeType.UNDIRECTED)
365	0	return undirected_edges.size();
366	0	return 0;
367		}
368
369		public EdgeType getDefaultEdgeType()
370		{
371	34	return EdgeType.UNDIRECTED;
372		}
373		}