Coverage Report

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

Classes in this File

Line Coverage

Branch Coverage

Complexity

SetHypergraph

27%

30/108

19%

14/72

2.667

SetHypergraph$1

100%

2/2

N/A

2.667

 /*
  * Created on Feb 4, 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.io.Serializable;
 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;
 
 /**
  * An implementation of <code>Hypergraph</code> that is suitable for sparse graphs and 
  * permits parallel edges.
  */
 @SuppressWarnings("serial")
 public class SetHypergraph<V,H> 
         implements Hypergraph<V,H>, MultiGraph<V,H>, Serializable
 {
     protected Map<V, Set<H>> vertices; // Map of vertices to incident hyperedge sets
     protected Map<H, Set<V>> edges;    // Map of hyperedges to incident vertex sets
  
     /**
      * Returns a <code>Factory</code> which creates instances of this class.
      * @param <V> vertex type of the hypergraph to be created
      * @param <H> edge type of the hypergraph to be created
      * @return a <code>Factory</code> which creates instances of this class
      */
     public static <V,H> Factory<Hypergraph<V,H>> getFactory() {
         return new Factory<Hypergraph<V,H>> () {
             public Hypergraph<V,H> create() {
                 return new SetHypergraph<V,H>();
             }
         };
     }
 
     /**
      * Creates a <code>SetHypergraph</code> and initializes the internal data structures.
      */
     public SetHypergraph()
     {
         vertices = new HashMap<V, Set<H>>();
         edges = new HashMap<H, Set<V>>();
     }
     
     /**
      * Adds <code>hyperedge</code> to this graph and connects them to the vertex collection <code>to_attach</code>.
      * Any vertices in <code>to_attach</code> that appear more than once will only appear once in the
      * incident vertex collection for <code>hyperedge</code>, that is, duplicates will be ignored.
      * 
      * @see Hypergraph#addEdge(Object, Collection)
      */
     public boolean addEdge(H hyperedge, Collection<? extends V> to_attach)
     {
         if (hyperedge == null)
             throw new IllegalArgumentException("input hyperedge may not be null");
         
         if (to_attach == null)
             throw new IllegalArgumentException("endpoints may not be null");
 
         if(to_attach.contains(null)) 
             throw new IllegalArgumentException("cannot add an edge with a null endpoint");
         
         Set<V> new_endpoints = new HashSet<V>(to_attach);
         if (edges.containsKey(hyperedge))
         {
             Collection<V> attached = edges.get(hyperedge);
             if (!attached.equals(new_endpoints))
             {
                 throw new IllegalArgumentException("Edge " + hyperedge + 
                         " exists in this graph with endpoints " + attached);
             }
             else
                 return false;
         }
         edges.put(hyperedge, new_endpoints);
         for (V v : to_attach)
         {
             // add v if it's not already in the graph
             addVertex(v);
             
             // associate v with hyperedge
             vertices.get(v).add(hyperedge);
         }
         return true;
     }
     
     /**
      * @see Hypergraph#addEdge(Object, Collection, EdgeType)
      */
     public boolean addEdge(H hyperedge, Collection<? extends V> to_attach, 
             EdgeType edge_type)
     {
             if (edge_type != EdgeType.UNDIRECTED)
                     throw new IllegalArgumentException("Edge type for this " +
                                     "implementation must be EdgeType.HYPER, not " + 
                                     edge_type);
             return addEdge(hyperedge, to_attach);
     }
     
     /**
      * @see Hypergraph#getEdgeType(Object)
      */
     public EdgeType getEdgeType(H edge)
     {
         if (containsEdge(edge))
             return EdgeType.UNDIRECTED;
         else
             return null;
     }
     
     public boolean containsVertex(V vertex) {
             return vertices.keySet().contains(vertex);
     }
     
     public boolean containsEdge(H edge) {
             return edges.keySet().contains(edge);
     }
 
     public Collection<H> getEdges()
     {
         return edges.keySet();
     }
     
     public Collection<V> getVertices()
     {
         return vertices.keySet();
     }
 
     public int getEdgeCount()
     {
         return edges.size();
     }
     
     public int getVertexCount()
     {
         return vertices.size();
     }
     
     public Collection<V> getNeighbors(V vertex)
     {
         if (!containsVertex(vertex))
             return null;
         
         Set<V> neighbors = new HashSet<V>();
         for (H hyperedge : vertices.get(vertex))
         {
             neighbors.addAll(edges.get(hyperedge));
         }
         return neighbors;
     }
     
     public Collection<H> getIncidentEdges(V vertex)
     {
         return vertices.get(vertex);
     }
     
     public Collection<V> getIncidentVertices(H edge)
     {
         return edges.get(edge);
     }
     
     public H findEdge(V v1, V v2)
     {
         if (!containsVertex(v1) || !containsVertex(v2))
             return null;
         
         for (H h : getIncidentEdges(v1))
         {
             if (isIncident(v2, h))
                 return h;
         }
         return null;
     }
 
     public Collection<H> findEdgeSet(V v1, V v2)
     {
         if (!containsVertex(v1) || !containsVertex(v2))
             return null;
         
         Collection<H> edges = new ArrayList<H>();
         for (H h : getIncidentEdges(v1))
         {
             if (isIncident(v2, h))
                 edges.add(h);
         }
         return Collections.unmodifiableCollection(edges);
     }
     
     public boolean addVertex(V vertex)
     {
             if(vertex == null) 
                 throw new IllegalArgumentException("cannot add a null vertex");
         if (containsVertex(vertex))
             return false;
         vertices.put(vertex, new HashSet<H>());
         return true;
     }
     
     public boolean removeVertex(V vertex)
     {
         if (!containsVertex(vertex))
             return false;
         for (H hyperedge : vertices.get(vertex))
         {
             edges.get(hyperedge).remove(vertex);
         }
         vertices.remove(vertex);
         return true;
     }
     
     public boolean removeEdge(H hyperedge)
     {
         if (!containsEdge(hyperedge))
             return false;
         for (V vertex : edges.get(hyperedge))
         {
             vertices.get(vertex).remove(hyperedge);
         }
         edges.remove(hyperedge);
         return true;
     }
     
     public boolean isNeighbor(V v1, V v2)
     {
         if (!containsVertex(v1) || !containsVertex(v2))
             return false;
         
         if (vertices.get(v2).isEmpty())
             return false;
         for (H hyperedge : vertices.get(v1))
         {
             if (edges.get(hyperedge).contains(v2))
                 return true;
         }
         return false;
     }
     
     public boolean isIncident(V vertex, H edge)
     {
         if (!containsVertex(vertex) || !containsEdge(edge))
             return false;
         
         return vertices.get(vertex).contains(edge);
     }
     
     public int degree(V vertex)
     {
         if (!containsVertex(vertex))
             return 0;
         
         return vertices.get(vertex).size();
     }
     
     public int getNeighborCount(V vertex)
     {
         if (!containsVertex(vertex))
             return 0;
         
         return getNeighbors(vertex).size();
     }
     
     public int getIncidentCount(H edge)
     {
         if (!containsEdge(edge))
             return 0;
         
         return edges.get(edge).size();
     }
 
     public int getEdgeCount(EdgeType edge_type)
     {
         if (edge_type == EdgeType.UNDIRECTED)
             return edges.size();
         return 0;
     }
 
     public Collection<H> getEdges(EdgeType edge_type)
     {
         if (edge_type == EdgeType.UNDIRECTED)
             return edges.keySet();
         return null;
     }
 
         public EdgeType getDefaultEdgeType() 
         {
                 return EdgeType.UNDIRECTED;
         }
 
         public Collection<H> getInEdges(V vertex) 
         {
                 return getIncidentEdges(vertex);
         }
 
         public Collection<H> getOutEdges(V vertex) 
         {
                 return getIncidentEdges(vertex);
         }
 
         public int inDegree(V vertex) 
         {
                 return degree(vertex);
         }
 
         public int outDegree(V vertex) 
         {
                 return degree(vertex);
         }
 
         public V getDest(H directed_edge) 
         {
                 return null;
         }
 
         public V getSource(H directed_edge) 
         {
                 return null;
         }
 
         public Collection<V> getPredecessors(V vertex) 
         {
                 return getNeighbors(vertex);
         }
 
         public Collection<V> getSuccessors(V vertex) 
         {
                 return getNeighbors(vertex);
         }
 }

1		/*
2		* Created on Feb 4, 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.io.Serializable;
15		import java.util.ArrayList;
16		import java.util.Collection;
17		import java.util.Collections;
18		import java.util.HashMap;
19		import java.util.HashSet;
20		import java.util.Map;
21		import java.util.Set;
22
23		import org.apache.commons.collections15.Factory;
24
25		import edu.uci.ics.jung.graph.util.EdgeType;
26
27		/**
28		* An implementation of <code>Hypergraph</code> that is suitable for sparse graphs and
29		* permits parallel edges.
30		*/
31		@SuppressWarnings("serial")
32		public class SetHypergraph<V,H>
33		implements Hypergraph<V,H>, MultiGraph<V,H>, Serializable
34		{
35		protected Map<V, Set<H>> vertices; // Map of vertices to incident hyperedge sets
36		protected Map<H, Set<V>> edges; // Map of hyperedges to incident vertex sets
37
38		/**
39		* Returns a <code>Factory</code> which creates instances of this class.
40		* @param <V> vertex type of the hypergraph to be created
41		* @param <H> edge type of the hypergraph to be created
42		* @return a <code>Factory</code> which creates instances of this class
43		*/
44		public static <V,H> Factory<Hypergraph<V,H>> getFactory() {
45	2	return new Factory<Hypergraph<V,H>> () {
46	6	public Hypergraph<V,H> create() {
47	4	return new SetHypergraph<V,H>();
48		}
49		};
50		}
51
52		/**
53		* Creates a <code>SetHypergraph</code> and initializes the internal data structures.
54		*/
55		public SetHypergraph()
56	4	{
57	4	vertices = new HashMap<V, Set<H>>();
58	4	edges = new HashMap<H, Set<V>>();
59	4	}
60
61		/**
62		* Adds <code>hyperedge</code> to this graph and connects them to the vertex collection <code>to_attach</code>.
63		* Any vertices in <code>to_attach</code> that appear more than once will only appear once in the
64		* incident vertex collection for <code>hyperedge</code>, that is, duplicates will be ignored.
65		*
66		* @see Hypergraph#addEdge(Object, Collection)
67		*/
68		public boolean addEdge(H hyperedge, Collection<? extends V> to_attach)
69		{
70	30	if (hyperedge == null)
71	0	throw new IllegalArgumentException("input hyperedge may not be null");
72
73	30	if (to_attach == null)
74	2	throw new IllegalArgumentException("endpoints may not be null");
75
76	28	if(to_attach.contains(null))
77	0	throw new IllegalArgumentException("cannot add an edge with a null endpoint");
78
79	28	Set<V> new_endpoints = new HashSet<V>(to_attach);
80	28	if (edges.containsKey(hyperedge))
81		{
82	6	Collection<V> attached = edges.get(hyperedge);
83	6	if (!attached.equals(new_endpoints))
84		{
85	2	throw new IllegalArgumentException("Edge " + hyperedge +
86		" exists in this graph with endpoints " + attached);
87		}
88		else
89	4	return false;
90		}
91	22	edges.put(hyperedge, new_endpoints);
92	22	for (V v : to_attach)
93		{
94		// add v if it's not already in the graph
95	94	addVertex(v);
96
97		// associate v with hyperedge
98	94	vertices.get(v).add(hyperedge);
99		}
100	22	return true;
101		}
102
103		/**
104		* @see Hypergraph#addEdge(Object, Collection, EdgeType)
105		*/
106		public boolean addEdge(H hyperedge, Collection<? extends V> to_attach,
107		EdgeType edge_type)
108		{
109	0	if (edge_type != EdgeType.UNDIRECTED)
110	0	throw new IllegalArgumentException("Edge type for this " +
111		"implementation must be EdgeType.HYPER, not " +
112		edge_type);
113	0	return addEdge(hyperedge, to_attach);
114		}
115
116		/**
117		* @see Hypergraph#getEdgeType(Object)
118		*/
119		public EdgeType getEdgeType(H edge)
120		{
121	0	if (containsEdge(edge))
122	0	return EdgeType.UNDIRECTED;
123		else
124	0	return null;
125		}
126
127		public boolean containsVertex(V vertex) {
128	102	return vertices.keySet().contains(vertex);
129		}
130
131		public boolean containsEdge(H edge) {
132	4	return edges.keySet().contains(edge);
133		}
134
135		public Collection<H> getEdges()
136		{
137	0	return edges.keySet();
138		}
139
140		public Collection<V> getVertices()
141		{
142	0	return vertices.keySet();
143		}
144
145		public int getEdgeCount()
146		{
147	6	return edges.size();
148		}
149
150		public int getVertexCount()
151		{
152	10	return vertices.size();
153		}
154
155		public Collection<V> getNeighbors(V vertex)
156		{
157	0	if (!containsVertex(vertex))
158	0	return null;
159
160	0	Set<V> neighbors = new HashSet<V>();
161	0	for (H hyperedge : vertices.get(vertex))
162		{
163	0	neighbors.addAll(edges.get(hyperedge));
164		}
165	0	return neighbors;
166		}
167
168		public Collection<H> getIncidentEdges(V vertex)
169		{
170	0	return vertices.get(vertex);
171		}
172
173		public Collection<V> getIncidentVertices(H edge)
174		{
175	0	return edges.get(edge);
176		}
177
178		public H findEdge(V v1, V v2)
179		{
180	0	if (!containsVertex(v1) \|\| !containsVertex(v2))
181	0	return null;
182
183	0	for (H h : getIncidentEdges(v1))
184		{
185	0	if (isIncident(v2, h))
186	0	return h;
187		}
188	0	return null;
189		}
190
191		public Collection<H> findEdgeSet(V v1, V v2)
192		{
193	0	if (!containsVertex(v1) \|\| !containsVertex(v2))
194	0	return null;
195
196	0	Collection<H> edges = new ArrayList<H>();
197	0	for (H h : getIncidentEdges(v1))
198		{
199	0	if (isIncident(v2, h))
200	0	edges.add(h);
201		}
202	0	return Collections.unmodifiableCollection(edges);
203		}
204
205		public boolean addVertex(V vertex)
206		{
207	100	if(vertex == null)
208	2	throw new IllegalArgumentException("cannot add a null vertex");
209	98	if (containsVertex(vertex))
210	80	return false;
211	18	vertices.put(vertex, new HashSet<H>());
212	18	return true;
213		}
214
215		public boolean removeVertex(V vertex)
216		{
217	0	if (!containsVertex(vertex))
218	0	return false;
219	0	for (H hyperedge : vertices.get(vertex))
220		{
221	0	edges.get(hyperedge).remove(vertex);
222		}
223	0	vertices.remove(vertex);
224	0	return true;
225		}
226
227		public boolean removeEdge(H hyperedge)
228		{
229	0	if (!containsEdge(hyperedge))
230	0	return false;
231	0	for (V vertex : edges.get(hyperedge))
232		{
233	0	vertices.get(vertex).remove(hyperedge);
234		}
235	0	edges.remove(hyperedge);
236	0	return true;
237		}
238
239		public boolean isNeighbor(V v1, V v2)
240		{
241	0	if (!containsVertex(v1) \|\| !containsVertex(v2))
242	0	return false;
243
244	0	if (vertices.get(v2).isEmpty())
245	0	return false;
246	0	for (H hyperedge : vertices.get(v1))
247		{
248	0	if (edges.get(hyperedge).contains(v2))
249	0	return true;
250		}
251	0	return false;
252		}
253
254		public boolean isIncident(V vertex, H edge)
255		{
256	0	if (!containsVertex(vertex) \|\| !containsEdge(edge))
257	0	return false;
258
259	0	return vertices.get(vertex).contains(edge);
260		}
261
262		public int degree(V vertex)
263		{
264	0	if (!containsVertex(vertex))
265	0	return 0;
266
267	0	return vertices.get(vertex).size();
268		}
269
270		public int getNeighborCount(V vertex)
271		{
272	0	if (!containsVertex(vertex))
273	0	return 0;
274
275	0	return getNeighbors(vertex).size();
276		}
277
278		public int getIncidentCount(H edge)
279		{
280	0	if (!containsEdge(edge))
281	0	return 0;
282
283	0	return edges.get(edge).size();
284		}
285
286		public int getEdgeCount(EdgeType edge_type)
287		{
288	0	if (edge_type == EdgeType.UNDIRECTED)
289	0	return edges.size();
290	0	return 0;
291		}
292
293		public Collection<H> getEdges(EdgeType edge_type)
294		{
295	0	if (edge_type == EdgeType.UNDIRECTED)
296	0	return edges.keySet();
297	0	return null;
298		}
299
300		public EdgeType getDefaultEdgeType()
301		{
302	0	return EdgeType.UNDIRECTED;
303		}
304
305		public Collection<H> getInEdges(V vertex)
306		{
307	0	return getIncidentEdges(vertex);
308		}
309
310		public Collection<H> getOutEdges(V vertex)
311		{
312	0	return getIncidentEdges(vertex);
313		}
314
315		public int inDegree(V vertex)
316		{
317	0	return degree(vertex);
318		}
319
320		public int outDegree(V vertex)
321		{
322	0	return degree(vertex);
323		}
324
325		public V getDest(H directed_edge)
326		{
327	0	return null;
328		}
329
330		public V getSource(H directed_edge)
331		{
332	0	return null;
333		}
334
335		public Collection<V> getPredecessors(V vertex)
336		{
337	0	return getNeighbors(vertex);
338		}
339
340		public Collection<V> getSuccessors(V vertex)
341		{
342	0	return getNeighbors(vertex);
343		}
344		}