Coverage Report

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

Classes in this File

Line Coverage

Branch Coverage

Complexity

SparseMultigraph

75%

91/120

59%

39/66

2.677

SparseMultigraph$1

100%

2/2

N/A

2.677

 /*
  * Created on Oct 18, 2005
  *
  * Copyright (c) 2005, 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.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
 
 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 directed, undirected, and parallel edges.
  */
 @SuppressWarnings("serial")
 public class SparseMultigraph<V,E> 
     extends AbstractGraph<V,E>
     implements MultiGraph<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 SparseMultigraph<V,E>();
                         }
                 };
         }
     
     // TODO: refactor internal representation: right now directed edges each have two references (in vertices and directedEdges)
     // and undirected also have two (incoming and outgoing).  
     protected Map<V, Pair<Set<E>>> vertices; // Map of vertices to Pair of adjacency sets {incoming, outgoing}
     protected Map<E, Pair<V>> edges;            // Map of edges to incident vertex pairs
     protected Set<E> directedEdges;
 
     /**
      * Creates a new instance.
      */
     public SparseMultigraph()
     {
         vertices = new HashMap<V, Pair<Set<E>>>();
         edges = new HashMap<E, Pair<V>>();
         directedEdges = new HashSet<E>();
     }
 
     public Collection<E> getEdges()
     {
         return Collections.unmodifiableCollection(edges.keySet());
     }
 
     public Collection<V> getVertices()
     {
         return Collections.unmodifiableCollection(vertices.keySet());
     }
     
     public boolean containsVertex(V vertex) {
             return vertices.keySet().contains(vertex);
     }
     
     public boolean containsEdge(E edge) {
             return edges.keySet().contains(edge);
     }
 
     protected Collection<E> getIncoming_internal(V vertex)
     {
         return vertices.get(vertex).getFirst();
     }
     
     protected Collection<E> getOutgoing_internal(V vertex)
     {
         return vertices.get(vertex).getSecond();
     }
     
     public boolean addVertex(V vertex) {
         if(vertex == null) {
             throw new IllegalArgumentException("vertex may not be null");
         }
         if (!vertices.containsKey(vertex)) {
             vertices.put(vertex, new Pair<Set<E>>(new HashSet<E>(), new HashSet<E>()));
             return true;
         } else {
                 return false;
         }
     }
 
     public boolean removeVertex(V vertex) {
         if (!containsVertex(vertex))
             return false;
         
         // copy to avoid concurrent modification in removeEdge
         Set<E> incident = new HashSet<E>(getIncoming_internal(vertex));
         incident.addAll(getOutgoing_internal(vertex));
         
         for (E edge : incident)
             removeEdge(edge);
         
         vertices.remove(vertex);
         
         return true;
     }
     
     @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();
         
         if (!vertices.containsKey(v1))
             this.addVertex(v1);
         
         if (!vertices.containsKey(v2))
             this.addVertex(v2);
         
 
         vertices.get(v1).getSecond().add(edge);        
         vertices.get(v2).getFirst().add(edge);        
         edges.put(edge, new_endpoints);
         if(edgeType == EdgeType.DIRECTED) {
                 directedEdges.add(edge);
         } else {
           vertices.get(v1).getFirst().add(edge);        
           vertices.get(v2).getSecond().add(edge);        
         }
         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 sets
         vertices.get(v1).getSecond().remove(edge);
         vertices.get(v2).getFirst().remove(edge);
 
         if(directedEdges.remove(edge) == false) {
                 
                 // its an undirected edge, remove the other ends
             vertices.get(v2).getSecond().remove(edge);
             vertices.get(v1).getFirst().remove(edge);
         }
         edges.remove(edge);
         return true;
     }
     
     public Collection<E> getInEdges(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
         return Collections.unmodifiableCollection(vertices.get(vertex).getFirst());
     }
 
     public Collection<E> getOutEdges(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
         return Collections.unmodifiableCollection(vertices.get(vertex).getSecond());
     }
 
     // TODO: this will need to get changed if we modify the internal representation
     public Collection<V> getPredecessors(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
 
         Set<V> preds = new HashSet<V>();
         for (E edge : getIncoming_internal(vertex)) {
                 if(getEdgeType(edge) == EdgeType.DIRECTED) {
                         preds.add(this.getSource(edge));
                 } else {
                         preds.add(getOpposite(vertex, edge));
                 }
         }
         return Collections.unmodifiableCollection(preds);
     }
 
     // TODO: this will need to get changed if we modify the internal representation
     public Collection<V> getSuccessors(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
         Set<V> succs = new HashSet<V>();
         for (E edge : getOutgoing_internal(vertex)) {
                 if(getEdgeType(edge) == EdgeType.DIRECTED) {
                         succs.add(this.getDest(edge));
                 } else {
                         succs.add(getOpposite(vertex, edge));
                 }
         }
         return Collections.unmodifiableCollection(succs);
     }
 
     public Collection<V> getNeighbors(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
         Collection<V> out = new HashSet<V>();
         out.addAll(this.getPredecessors(vertex));
         out.addAll(this.getSuccessors(vertex));
         return out;
     }
 
     public Collection<E> getIncidentEdges(V vertex)
     {
             if (!containsVertex(vertex))
                     return null;
         Collection<E> out = new HashSet<E>();
         out.addAll(this.getInEdges(vertex));
         out.addAll(this.getOutEdges(vertex));
         return out;
     }
 
     @Override
     public E findEdge(V v1, V v2)
     {
             if (!containsVertex(v1) || !containsVertex(v2))
                     return null;
         for (E edge : getOutgoing_internal(v1))
             if (this.getOpposite(v1, edge).equals(v2))
                 return edge;
         
         return null;
     }
 
     public Pair<V> getEndpoints(E edge)
     {
         return edges.get(edge);
     }
 
     public V getSource(E edge) {
             if(directedEdges.contains(edge)) {
                     return this.getEndpoints(edge).getFirst();
             }
             return null;
     }
 
     public V getDest(E edge) {
             if(directedEdges.contains(edge)) {
                     return this.getEndpoints(edge).getSecond();
             }
             return null;
     }
 
     public boolean isSource(V vertex, E edge) {
             if (!containsEdge(edge) || !containsVertex(vertex))
                     return false;
         return getSource(edge).equals(vertex);
     }
 
     public boolean isDest(V vertex, E edge) {
             if (!containsEdge(edge) || !containsVertex(vertex))
                     return false;
         return getDest(edge).equals(vertex);
     }
 
     public EdgeType getEdgeType(E edge) {
             return directedEdges.contains(edge) ?
                     EdgeType.DIRECTED :
                             EdgeType.UNDIRECTED;
     }
 
         @SuppressWarnings("unchecked")
         public Collection<E> getEdges(EdgeType edgeType) {
                 if(edgeType == EdgeType.DIRECTED) {
                         return Collections.unmodifiableSet(this.directedEdges);
                 } else if(edgeType == EdgeType.UNDIRECTED) {
                         Collection<E> edges = new HashSet<E>(getEdges());
                         edges.removeAll(directedEdges);
                         return edges;
                 } else {
                         return Collections.EMPTY_SET;
                 }
                 
         }
 
         public int getEdgeCount() {
                 return edges.keySet().size();
         }
 
         public int getVertexCount() {
                 return vertices.keySet().size();
         }
 
     public int getEdgeCount(EdgeType edge_type)
     {
         return getEdges(edge_type).size();
     }
 
         public EdgeType getDefaultEdgeType() 
         {
                 return EdgeType.UNDIRECTED;
         }
 }

1		/*
2		* Created on Oct 18, 2005
3		*
4		* Copyright (c) 2005, 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.Collection;
15		import java.util.Collections;
16		import java.util.HashMap;
17		import java.util.HashSet;
18		import java.util.Map;
19		import java.util.Set;
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
28		* and permits directed, undirected, and parallel edges.
29		*/
30		@SuppressWarnings("serial")
31		public class SparseMultigraph<V,E>
32		extends AbstractGraph<V,E>
33		implements MultiGraph<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	2	return new Factory<Graph<V,E>> () {
42	6	public Graph<V,E> create() {
43	4	return new SparseMultigraph<V,E>();
44		}
45		};
46		}
47
48		// TODO: refactor internal representation: right now directed edges each have two references (in vertices and directedEdges)
49		// and undirected also have two (incoming and outgoing).
50		protected Map<V, Pair<Set<E>>> vertices; // Map of vertices to Pair of adjacency sets {incoming, outgoing}
51		protected Map<E, Pair<V>> edges; // Map of edges to incident vertex pairs
52		protected Set<E> directedEdges;
53
54		/**
55		* Creates a new instance.
56		*/
57		public SparseMultigraph()
58	236	{
59	236	vertices = new HashMap<V, Pair<Set<E>>>();
60	236	edges = new HashMap<E, Pair<V>>();
61	236	directedEdges = new HashSet<E>();
62	236	}
63
64		public Collection<E> getEdges()
65		{
66	12	return Collections.unmodifiableCollection(edges.keySet());
67		}
68
69		public Collection<V> getVertices()
70		{
71	6	return Collections.unmodifiableCollection(vertices.keySet());
72		}
73
74		public boolean containsVertex(V vertex) {
75	1074	return vertices.keySet().contains(vertex);
76		}
77
78		public boolean containsEdge(E edge) {
79	2094	return edges.keySet().contains(edge);
80		}
81
82		protected Collection<E> getIncoming_internal(V vertex)
83		{
84	36	return vertices.get(vertex).getFirst();
85		}
86
87		protected Collection<E> getOutgoing_internal(V vertex)
88		{
89	24	return vertices.get(vertex).getSecond();
90		}
91
92		public boolean addVertex(V vertex) {
93	588	if(vertex == null) {
94	2	throw new IllegalArgumentException("vertex may not be null");
95		}
96	586	if (!vertices.containsKey(vertex)) {
97	584	vertices.put(vertex, new Pair<Set<E>>(new HashSet<E>(), new HashSet<E>()));
98	584	return true;
99		} else {
100	2	return false;
101		}
102		}
103
104		public boolean removeVertex(V vertex) {
105	12	if (!containsVertex(vertex))
106	0	return false;
107
108		// copy to avoid concurrent modification in removeEdge
109	12	Set<E> incident = new HashSet<E>(getIncoming_internal(vertex));
110	12	incident.addAll(getOutgoing_internal(vertex));
111
112	12	for (E edge : incident)
113	30	removeEdge(edge);
114
115	12	vertices.remove(vertex);
116
117	12	return true;
118		}
119
120		@Override
121		public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType) {
122
123	2046	Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
124	2040	if (new_endpoints == null)
125	12	return false;
126
127	2028	V v1 = new_endpoints.getFirst();
128	2028	V v2 = new_endpoints.getSecond();
129
130	2028	if (!vertices.containsKey(v1))
131	422	this.addVertex(v1);
132
133	2028	if (!vertices.containsKey(v2))
134	454	this.addVertex(v2);
135
136
137	2028	vertices.get(v1).getSecond().add(edge);
138	2028	vertices.get(v2).getFirst().add(edge);
139	2028	edges.put(edge, new_endpoints);
140	2028	if(edgeType == EdgeType.DIRECTED) {
141	576	directedEdges.add(edge);
142		} else {
143	1452	vertices.get(v1).getFirst().add(edge);
144	1452	vertices.get(v2).getSecond().add(edge);
145		}
146	2028	return true;
147		}
148
149		public boolean removeEdge(E edge)
150		{
151	36	if (!containsEdge(edge)) {
152	0	return false;
153		}
154
155	36	Pair<V> endpoints = getEndpoints(edge);
156	36	V v1 = endpoints.getFirst();
157	36	V v2 = endpoints.getSecond();
158
159		// remove edge from incident vertices' adjacency sets
160	36	vertices.get(v1).getSecond().remove(edge);
161	36	vertices.get(v2).getFirst().remove(edge);
162
163	36	if(directedEdges.remove(edge) == false) {
164
165		// its an undirected edge, remove the other ends
166	20	vertices.get(v2).getSecond().remove(edge);
167	20	vertices.get(v1).getFirst().remove(edge);
168		}
169	36	edges.remove(edge);
170	36	return true;
171		}
172
173		public Collection<E> getInEdges(V vertex)
174		{
175	132	if (!containsVertex(vertex))
176	0	return null;
177	132	return Collections.unmodifiableCollection(vertices.get(vertex).getFirst());
178		}
179
180		public Collection<E> getOutEdges(V vertex)
181		{
182	138	if (!containsVertex(vertex))
183	0	return null;
184	138	return Collections.unmodifiableCollection(vertices.get(vertex).getSecond());
185		}
186
187		// TODO: this will need to get changed if we modify the internal representation
188		public Collection<V> getPredecessors(V vertex)
189		{
190	24	if (!containsVertex(vertex))
191	0	return null;
192
193	24	Set<V> preds = new HashSet<V>();
194	24	for (E edge : getIncoming_internal(vertex)) {
195	84	if(getEdgeType(edge) == EdgeType.DIRECTED) {
196	18	preds.add(this.getSource(edge));
197		} else {
198	66	preds.add(getOpposite(vertex, edge));
199		}
200		}
201	24	return Collections.unmodifiableCollection(preds);
202		}
203
204		// TODO: this will need to get changed if we modify the internal representation
205		public Collection<V> getSuccessors(V vertex)
206		{
207	6	if (!containsVertex(vertex))
208	0	return null;
209	6	Set<V> succs = new HashSet<V>();
210	6	for (E edge : getOutgoing_internal(vertex)) {
211	18	if(getEdgeType(edge) == EdgeType.DIRECTED) {
212	0	succs.add(this.getDest(edge));
213		} else {
214	18	succs.add(getOpposite(vertex, edge));
215		}
216		}
217	6	return Collections.unmodifiableCollection(succs);
218		}
219
220		public Collection<V> getNeighbors(V vertex)
221		{
222	6	if (!containsVertex(vertex))
223	0	return null;
224	6	Collection<V> out = new HashSet<V>();
225	6	out.addAll(this.getPredecessors(vertex));
226	6	out.addAll(this.getSuccessors(vertex));
227	6	return out;
228		}
229
230		public Collection<E> getIncidentEdges(V vertex)
231		{
232	28	if (!containsVertex(vertex))
233	0	return null;
234	28	Collection<E> out = new HashSet<E>();
235	28	out.addAll(this.getInEdges(vertex));
236	28	out.addAll(this.getOutEdges(vertex));
237	28	return out;
238		}
239
240		@Override
241		public E findEdge(V v1, V v2)
242		{
243	6	if (!containsVertex(v1) \|\| !containsVertex(v2))
244	0	return null;
245	6	for (E edge : getOutgoing_internal(v1))
246	18	if (this.getOpposite(v1, edge).equals(v2))
247	6	return edge;
248
249	0	return null;
250		}
251
252		public Pair<V> getEndpoints(E edge)
253		{
254	180	return edges.get(edge);
255		}
256
257		public V getSource(E edge) {
258	18	if(directedEdges.contains(edge)) {
259	18	return this.getEndpoints(edge).getFirst();
260		}
261	0	return null;
262		}
263
264		public V getDest(E edge) {
265	0	if(directedEdges.contains(edge)) {
266	0	return this.getEndpoints(edge).getSecond();
267		}
268	0	return null;
269		}
270
271		public boolean isSource(V vertex, E edge) {
272	0	if (!containsEdge(edge) \|\| !containsVertex(vertex))
273	0	return false;
274	0	return getSource(edge).equals(vertex);
275		}
276
277		public boolean isDest(V vertex, E edge) {
278	0	if (!containsEdge(edge) \|\| !containsVertex(vertex))
279	0	return false;
280	0	return getDest(edge).equals(vertex);
281		}
282
283		public EdgeType getEdgeType(E edge) {
284	414	return directedEdges.contains(edge) ?
285		EdgeType.DIRECTED :
286		EdgeType.UNDIRECTED;
287		}
288
289		@SuppressWarnings("unchecked")
290		public Collection<E> getEdges(EdgeType edgeType) {
291	0	if(edgeType == EdgeType.DIRECTED) {
292	0	return Collections.unmodifiableSet(this.directedEdges);
293	0	} else if(edgeType == EdgeType.UNDIRECTED) {
294	0	Collection<E> edges = new HashSet<E>(getEdges());
295	0	edges.removeAll(directedEdges);
296	0	return edges;
297		} else {
298	0	return Collections.EMPTY_SET;
299		}
300
301		}
302
303		public int getEdgeCount() {
304	72	return edges.keySet().size();
305		}
306
307		public int getVertexCount() {
308	72	return vertices.keySet().size();
309		}
310
311		public int getEdgeCount(EdgeType edge_type)
312		{
313	0	return getEdges(edge_type).size();
314		}
315
316		public EdgeType getDefaultEdgeType()
317		{
318	1536	return EdgeType.UNDIRECTED;
319		}
320		}