Coverage Report

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

Classes in this File

Line Coverage

Branch Coverage

Complexity

UndirectedSparseMultigraph

85%

70/82

71%

27/38

2.037

UndirectedSparseMultigraph$1

100%

2/2

N/A

2.037

 /*
  * Created on Mar 6, 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.
  */
 /*
  * 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.ArrayList;
 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>UndirectedGraph</code> that is suitable for 
  * sparse graphs and permits parallel edges.
  */
 @SuppressWarnings("serial")
 public class UndirectedSparseMultigraph<V,E> 
     extends AbstractTypedGraph<V,E>
     implements UndirectedGraph<V,E>, 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<UndirectedGraph<V,E>> getFactory() {
         return new Factory<UndirectedGraph<V,E>> () {
 
             public UndirectedGraph<V,E> create() {
                 return new UndirectedSparseMultigraph<V,E>();
             }
         };
     }
 
     protected Map<V, Set<E>> vertices; // Map of vertices to adjacency sets
     protected Map<E, Pair<V>> edges;    // Map of edges to incident vertex sets
 
     /**
      * Creates a new instance.
      */
     public UndirectedSparseMultigraph() {
             super(EdgeType.UNDIRECTED);
         vertices = new HashMap<V, Set<E>>();
         edges = new HashMap<E, Pair<V>>();
     }
 
     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> getIncident_internal(V vertex)
     {
         return vertices.get(vertex);
     }
     
     public boolean addVertex(V vertex) {
         if(vertex == null) {
             throw new IllegalArgumentException("vertex may not be null");
         }
         if (!containsVertex(vertex))
         {
             vertices.put(vertex, new HashSet<E>());
             return true;
         } else {
             return false;
         }
     }
 
     public boolean removeVertex(V vertex) {
         if (!containsVertex(vertex))
             return false;
         
         for (E edge : new ArrayList<E>(getIncident_internal(vertex)))
             removeEdge(edge);
         
         vertices.remove(vertex);
         return true;
     }
     
     @Override
     public boolean addEdge(E edge, V v1, V v2, EdgeType edgeType) {
         return addEdge(edge, new Pair<V>(v1, v2), edgeType);
     }
     
     @Override
     public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edge_type) 
     {
             validateEdgeType(edge_type);
             
         Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
         if (new_endpoints == null)
             return false;
         
         V v1 = endpoints.getFirst();
         V v2 = endpoints.getSecond();
 
         edges.put(edge, new_endpoints);
         
         if (!containsVertex(v1))
             this.addVertex(v1);
         
         if (!containsVertex(v2))
             this.addVertex(v2);
 
         vertices.get(v1).add(edge);
         vertices.get(v2).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).remove(edge);
         vertices.get(v2).remove(edge);
 
         edges.remove(edge);
         return true;
     }
     
     public Collection<E> getInEdges(V vertex) {
         return this.getIncidentEdges(vertex);
     }
 
     public Collection<E> getOutEdges(V vertex) {
         return this.getIncidentEdges(vertex);
     }
 
     public Collection<V> getPredecessors(V vertex) {
         return this.getNeighbors(vertex);
     }
 
     public Collection<V> getSuccessors(V vertex) {
         return this.getNeighbors(vertex);
     }
 
     public Collection<V> getNeighbors(V vertex) {
         if (!containsVertex(vertex))
             return null;
         
         Set<V> neighbors = new HashSet<V>();
         for (E edge : getIncident_internal(vertex))
         {
             Pair<V> endpoints = this.getEndpoints(edge);
             V e_a = endpoints.getFirst();
             V e_b = endpoints.getSecond();
             if (vertex.equals(e_a))
                 neighbors.add(e_b);
             else
                 neighbors.add(e_a);
         }
         
         return Collections.unmodifiableCollection(neighbors);
     }
 
     public Collection<E> getIncidentEdges(V vertex) {
         if (!containsVertex(vertex))
             return null;
         
         return Collections.unmodifiableCollection(getIncident_internal(vertex));
     }
 
     @Override
     public E findEdge(V v1, V v2) {
         if (!containsVertex(v1) || !containsVertex(v2))
             return null;
         for (E edge : getIncident_internal(v1)) {
             Pair<V> endpoints = this.getEndpoints(edge);
             V e_a = endpoints.getFirst();
             V e_b = endpoints.getSecond();
             if ((v1.equals(e_a) && v2.equals(e_b)) || (v1.equals(e_b) && v2.equals(e_a)))
                 return edge;
         }
         return null;
     }
 
     public Pair<V> getEndpoints(E edge) {
         return edges.get(edge);
     }
 
     public V getDest(E directed_edge) {
         return null;
     }
 
     public V getSource(E directed_edge) {
         return null;
     }
 
     public boolean isDest(V vertex, E edge) {
         return false;
     }
 
     public boolean isSource(V vertex, E edge) {
         return false;
     }
 
     public int getEdgeCount() {
         return edges.size();
     }
 
     public int getVertexCount() {
         return vertices.size();
     }
 
 }

1		/*
2		* Created on Mar 6, 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		/*
13		* Created on Oct 18, 2005
14		*
15		* Copyright (c) 2005, the JUNG Project and the Regents of the University
16		* of California
17		* All rights reserved.
18		*
19		* This software is open-source under the BSD license; see either
20		* "license.txt" or
21		* http://jung.sourceforge.net/license.txt for a description.
22		*/
23		package edu.uci.ics.jung.graph;
24
25		import java.util.ArrayList;
26		import java.util.Collection;
27		import java.util.Collections;
28		import java.util.HashMap;
29		import java.util.HashSet;
30		import java.util.Map;
31		import java.util.Set;
32
33		import org.apache.commons.collections15.Factory;
34
35		import edu.uci.ics.jung.graph.util.EdgeType;
36		import edu.uci.ics.jung.graph.util.Pair;
37
38		/**
39		* An implementation of <code>UndirectedGraph</code> that is suitable for
40		* sparse graphs and permits parallel edges.
41		*/
42		@SuppressWarnings("serial")
43		public class UndirectedSparseMultigraph<V,E>
44		extends AbstractTypedGraph<V,E>
45		implements UndirectedGraph<V,E>, MultiGraph<V,E>
46		{
47		/**
48		* Returns a {@code Factory} that creates an instance of this graph type.
49		* @param <V> the vertex type for the graph factory
50		* @param <E> the edge type for the graph factory
51		*/
52		public static <V,E> Factory<UndirectedGraph<V,E>> getFactory() {
53	2	return new Factory<UndirectedGraph<V,E>> () {
54
55	6	public UndirectedGraph<V,E> create() {
56	4	return new UndirectedSparseMultigraph<V,E>();
57		}
58		};
59		}
60
61		protected Map<V, Set<E>> vertices; // Map of vertices to adjacency sets
62		protected Map<E, Pair<V>> edges; // Map of edges to incident vertex sets
63
64		/**
65		* Creates a new instance.
66		*/
67		public UndirectedSparseMultigraph() {
68	44	super(EdgeType.UNDIRECTED);
69	44	vertices = new HashMap<V, Set<E>>();
70	44	edges = new HashMap<E, Pair<V>>();
71	44	}
72
73		public Collection<E> getEdges() {
74	2	return Collections.unmodifiableCollection(edges.keySet());
75		}
76
77		public Collection<V> getVertices() {
78	0	return Collections.unmodifiableCollection(vertices.keySet());
79		}
80
81		public boolean containsVertex(V vertex) {
82	456	return vertices.keySet().contains(vertex);
83		}
84
85		public boolean containsEdge(E edge) {
86	184	return edges.keySet().contains(edge);
87		}
88
89		protected Collection<E> getIncident_internal(V vertex)
90		{
91	20	return vertices.get(vertex);
92		}
93
94		public boolean addVertex(V vertex) {
95	120	if(vertex == null) {
96	2	throw new IllegalArgumentException("vertex may not be null");
97		}
98	118	if (!containsVertex(vertex))
99		{
100	116	vertices.put(vertex, new HashSet<E>());
101	116	return true;
102		} else {
103	2	return false;
104		}
105		}
106
107		public boolean removeVertex(V vertex) {
108	4	if (!containsVertex(vertex))
109	0	return false;
110
111	4	for (E edge : new ArrayList<E>(getIncident_internal(vertex)))
112	12	removeEdge(edge);
113
114	4	vertices.remove(vertex);
115	4	return true;
116		}
117
118		@Override
119		public boolean addEdge(E edge, V v1, V v2, EdgeType edgeType) {
120	148	return addEdge(edge, new Pair<V>(v1, v2), edgeType);
121		}
122
123		@Override
124		public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edge_type)
125		{
126	164	validateEdgeType(edge_type);
127
128	162	Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
129	158	if (new_endpoints == null)
130	8	return false;
131
132	150	V v1 = endpoints.getFirst();
133	150	V v2 = endpoints.getSecond();
134
135	150	edges.put(edge, new_endpoints);
136
137	150	if (!containsVertex(v1))
138	40	this.addVertex(v1);
139
140	150	if (!containsVertex(v2))
141	76	this.addVertex(v2);
142
143	150	vertices.get(v1).add(edge);
144	150	vertices.get(v2).add(edge);
145
146	150	return true;
147		}
148
149		public boolean removeEdge(E edge) {
150	14	if (!containsEdge(edge))
151	0	return false;
152
153	14	Pair<V> endpoints = getEndpoints(edge);
154	14	V v1 = endpoints.getFirst();
155	14	V v2 = endpoints.getSecond();
156
157		// remove edge from incident vertices' adjacency sets
158	14	vertices.get(v1).remove(edge);
159	14	vertices.get(v2).remove(edge);
160
161	14	edges.remove(edge);
162	14	return true;
163		}
164
165		public Collection<E> getInEdges(V vertex) {
166	2	return this.getIncidentEdges(vertex);
167		}
168
169		public Collection<E> getOutEdges(V vertex) {
170	2	return this.getIncidentEdges(vertex);
171		}
172
173		public Collection<V> getPredecessors(V vertex) {
174	6	return this.getNeighbors(vertex);
175		}
176
177		public Collection<V> getSuccessors(V vertex) {
178	0	return this.getNeighbors(vertex);
179		}
180
181		public Collection<V> getNeighbors(V vertex) {
182	8	if (!containsVertex(vertex))
183	0	return null;
184
185	8	Set<V> neighbors = new HashSet<V>();
186	8	for (E edge : getIncident_internal(vertex))
187		{
188	28	Pair<V> endpoints = this.getEndpoints(edge);
189	28	V e_a = endpoints.getFirst();
190	28	V e_b = endpoints.getSecond();
191	28	if (vertex.equals(e_a))
192	14	neighbors.add(e_b);
193		else
194	14	neighbors.add(e_a);
195	28	}
196
197	8	return Collections.unmodifiableCollection(neighbors);
198		}
199
200		public Collection<E> getIncidentEdges(V vertex) {
201	6	if (!containsVertex(vertex))
202	0	return null;
203
204	6	return Collections.unmodifiableCollection(getIncident_internal(vertex));
205		}
206
207		@Override
208		public E findEdge(V v1, V v2) {
209	2	if (!containsVertex(v1) \|\| !containsVertex(v2))
210	0	return null;
211	2	for (E edge : getIncident_internal(v1)) {
212	4	Pair<V> endpoints = this.getEndpoints(edge);
213	4	V e_a = endpoints.getFirst();
214	4	V e_b = endpoints.getSecond();
215	4	if ((v1.equals(e_a) && v2.equals(e_b)) \|\| (v1.equals(e_b) && v2.equals(e_a)))
216	2	return edge;
217	2	}
218	0	return null;
219		}
220
221		public Pair<V> getEndpoints(E edge) {
222	60	return edges.get(edge);
223		}
224
225		public V getDest(E directed_edge) {
226	0	return null;
227		}
228
229		public V getSource(E directed_edge) {
230	0	return null;
231		}
232
233		public boolean isDest(V vertex, E edge) {
234	0	return false;
235		}
236
237		public boolean isSource(V vertex, E edge) {
238	0	return false;
239		}
240
241		public int getEdgeCount() {
242	26	return edges.size();
243		}
244
245		public int getVertexCount() {
246	34	return vertices.size();
247		}
248
249		}