Coverage details for edu.uci.ics.jung.graph.impl.BipartiteGraph

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University
3  * of California
4  * All rights reserved.
5  *
6  * This software is open-source under the BSD license; see either
7  * "license.txt" or
8  * http://jung.sourceforge.net/license.txt for a description.
9  */
10 /*
11  * Created on Aug 6, 2003
12  */
13 package edu.uci.ics.jung.graph.impl;
14  
15 import java.util.Collections;
16 import java.util.HashSet;
17 import java.util.Iterator;
18 import java.util.Set;
19  
20 import org.apache.commons.collections.MultiHashMap;
21 import org.apache.commons.collections.MultiMap;
22  
23 import edu.uci.ics.jung.exceptions.FatalException;
24 import edu.uci.ics.jung.graph.Edge;
25 import edu.uci.ics.jung.graph.Graph;
26 import edu.uci.ics.jung.graph.Vertex;
27 import edu.uci.ics.jung.utils.GraphUtils;
28 import edu.uci.ics.jung.utils.UserData;
29  
30 /**
31  * A Bipartite graph is divided into A vertices and B vertices. Edges
32  * only connect A vertices to B vertices, and vice versa. This class
33  * extends <i>UndirectedSparseGraph</i>; thus, the Graph is made up of
34  * <i>UndirectedSparseVertices</i>. <p>
35  * Vertices can only be added to the graph with a flag that says
36  * which class they will be added to (using <i>BipartiteGraph.Choice</i> );
37  * edges must be of type <i>BipartiteGraph</i>, which must consist of two
38  * vertices, one each from CLASSA and CLASSB.
39  * <pre>
40  * BipartiteGraph bpg = new BipartiteGraph;
41  * Vertex va = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSA );
42  * Vertex vb = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSB );
43  * bpg.addBipartiteEdge( new BipartiteEdge( va, vb ));
44  * </pre>
45  * Note that the traditional <i>addVertex()</i> and <i>addEdge()</i> will
46  * both throw a <i>FatalException</i>.<p>
47  * The function <i>fold</i> creates an <i>UndirectedGraph</i>
48  * based on finding vertices that share a common neighbor.
49  *
50  * @author danyelf
51  * @since 1.0.1
52  */
5321public class BipartiteGraph extends UndirectedSparseGraph {
54  
5521    private Set aSet = new HashSet();
5621    private Set bSet = new HashSet();
57  
58     public void initialize() {
5924        super.initialize();
6024        aSet = new HashSet();
6124        bSet = new HashSet();
6224    }
63  
64     /**
65      * Returns the set of all vertices from that class.
66      * All vertices in the return set will be of class
67      * A or class B, depending on the parameter.
68      */
69     public Set getAllVertices( Choice choice ) {
70141        if (choice == CLASSA ) {
7171            return Collections.unmodifiableSet(aSet);
7270        } else if (choice == CLASSB ) {
7370            return Collections.unmodifiableSet(bSet);
74         } else
750            throw new IllegalArgumentException("Invalid partition specification " + choice);
76     }
77  
78 // public ArchetypeGraph copy() {
79 // System.out.println( this.getClass() );
80 // ArchetypeGraph c = newInstance();
81 // for (Iterator iter = getVertices().iterator(); iter.hasNext();) {
82 // ArchetypeVertex av = (ArchetypeVertex) iter.next();
83 // ArchetypeVertex avNew = av.copy(c);
84 // }
85 // for (Iterator iter = getEdges().iterator(); iter.hasNext();) {
86 // ArchetypeEdge ae = (ArchetypeEdge) iter.next();
87 // ae.copy(c);
88 // }
89 // c.importUserData(this);
90 // return c;
91 //
92 // }
93  
94     /**
95      * Returns the partition for vertex <code>v</code>.
96      * @param v
97      */
98     public Choice getPartition(BipartiteVertex v)
99     {
10029        if (aSet.contains(v))
10119            return CLASSA;
10210        else if (bSet.contains(v))
1039            return CLASSB;
104         else {
1051            if ( v.getGraph() == this )
1060                throw new IllegalArgumentException("Inconsistent state in graph!");
1071            throw new IllegalArgumentException("Vertex " + v + " is not part of this graph");
108         }
109     }
110     
111     /**
112      * Adds a single vertex to the graph in the specified partition.
113      * Note that the vertex must be compatible with BipartiteVertex.
114      *
115      * <p>Throws an <code>IllegalArgumentException</code>
116      * if <code>v</code> is not an element of either partition.</p>
117      *
118      * @param v the vertex to be added to the class
119      * @param choice the class to which the vertex should be added
120      * @return the input vertex
121      */
122     public BipartiteVertex addVertex(BipartiteVertex v, Choice choice) {
12394        String exists = "Specified partition already contains vertex ";
12494        String dup = "Another partition already contains vertex ";
12594        if (choice == CLASSA )
126         {
12761            if (aSet.contains(v))
1281                throw new IllegalArgumentException(exists + v);
12960            if (bSet.contains(v))
1300                throw new IllegalArgumentException(dup + v);
13160            aSet.add(v);
132         }
13333        else if (choice == CLASSB )
134         {
13533            if (bSet.contains(v))
1360                throw new IllegalArgumentException(exists + v);
13733            if (aSet.contains(v))
1380                throw new IllegalArgumentException(dup + v);
13933            bSet.add(v);
140         }
141         else
1420            throw new IllegalArgumentException("Invalid partition specification for vertex " + v + ": " + choice);
14393        super.addVertex(v);
14493        return v;
145     }
146     
147     /**
148      * Adds a BipartiteEdge to the Graph. This function is simply a
149      * typed version of addEdge
150      * @param bpe a BipartiteEdge
151      * @return the edge, now a member of the graph.
152      */
153     public BipartiteEdge addBipartiteEdge(BipartiteEdge bpe) {
15475        return (BipartiteEdge) super.addEdge(bpe);
155     }
156  
157     /**
158      * DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.
159      * @see edu.uci.ics.jung.graph.impl.UndirectedSparseGraph#addEdge(edu.uci.ics.jung.graph.Edge)
160      * @deprecated Use addBipartiteEdge
161      */
162     public Edge addEdge(Edge ae) {
1631        throw new FatalException("Only add BipartiteEdges");
164     }
165  
166     /**
167      * DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.
168      * @see edu.uci.ics.jung.graph.impl.UndirectedSparseGraph#addVertex(edu.uci.ics.jung.graph.Vertex)
169      * @deprecated Use addBipartiteVertex
170      */
171     public Vertex addVertex(Vertex av) {
1722        throw new FatalException("Use addVertexX to add vertices to a BipartiteGraph ");
173     }
174     
175     /**
176      * This small enumerated type merely forces a user to pick class "A"
177      * or "B" when adding a Vertex to a BipartiteGraph.
178      */
17921    public static final class Choice {
180     }
1813    public static final Choice CLASSA = new Choice();
1823    public static final Choice CLASSB = new Choice();
183  
184     /**
185      * Creates a one-part graph from a bipartite graph by folding
186      * Vertices from one class into a second class. This function
187      * creates a new UndirectedGraph (with vertex set V') in which: <br>
188      * <ul>
189      * <li> each vertex in V' has an equivalent V in bpg.getAllVertices( class ) </li>
190      * <li> an edge E' joins V'1 and V'2 iff there is a path of length 2 from
191      * V1 to V2 (by way of some third vertex in the other class, VXs) </li>
192      * <li> each edge E' is annotated with the set of vertices VXs </li>
193      * </ul>
194      *
195      * In social network analysis and related fields, this operation transforms
196      * an actor-by-event chart into an actor-by-actor chart.
197      *
198      * @param bpg The bipartite graph to be folded
199      * @param vertexSet Chooses the set of vertices to be brought into
200      * the new Graph.
201      * @return an UndirectedSparseGraph.
202      */
203     public static Graph fold(BipartiteGraph bpg, Choice vertexSet) {
2041        Graph newGraph = new UndirectedSparseGraph();
2051        Set vertices = bpg.getAllVertices( vertexSet );
2061        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
2073            BipartiteVertex v = (BipartiteVertex) iter.next();
2083            v.copy(newGraph);
209         }
210         
2111        Set coveredNodes = new HashSet();
212         
2131        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
2143            BipartiteVertex v = (BipartiteVertex) iter.next();
2153            coveredNodes.add( v );
216  
217             // the set of all Bs that touch this A
2183            Set hyperEdges = v.getNeighbors();
219  
220             // this will ultimately contain a mapping from
221             // the next adjacent "A" to the list of "B"s that support that
222             // connection (that is, all Bs that run between this A and its neighbor
2233            MultiMap mm = new MultiHashMap();
2243            for (Iterator iterator = hyperEdges.iterator();
2258                iterator.hasNext();
226                 ) {
2275                Vertex hyperEdge = (Vertex) iterator.next();
2285                addAll(mm, hyperEdge.getNeighbors(), hyperEdge);
229             }
2303            for (Iterator iterator = mm.keySet().iterator();
2317                iterator.hasNext();
232                 ) {
2334                Vertex aVertex = (Vertex) iterator.next();
234  
2354                if ( coveredNodes.contains( aVertex )) continue;
236  
2371                Edge newEdge = GraphUtils.addEdge(
238                     newGraph,
239                     (Vertex)v.getEqualVertex(newGraph),
240                     (Vertex)aVertex.getEqualVertex(newGraph));
2411                newEdge.addUserDatum(BIPARTITE_USER_TAG, mm.get(aVertex), UserData.SHARED);
242             }
243         }
2441        return newGraph;
245     }
246  
247     /**
248      * The tag for the UserData attached to a single Edge.
249      */
2503    public static final Object BIPARTITE_USER_TAG = "BipartiteUserTag";
251  
252     /**
253      * Adds all pairs (key, value) to the multimap from
254      * the initial set keySet.
255      * @param set
256      * @param hyperEdge
257      */
258     private static void addAll(MultiMap mm, Set keyset, Object value) {
2595        for (Iterator iter = keyset.iterator(); iter.hasNext();) {
2609            Object key = iter.next();
2619            mm.put(key, value);
262         }
2635    }
264  
265     /* (non-Javadoc)
266      * @see edu.uci.ics.jung.graph.Graph#removeVertex(edu.uci.ics.jung.graph.Vertex)
267      */
268     public void removeVertex(Vertex v) {
2695        super.removeVertex(v);
2705        if ( aSet.contains(v)) {
2715            aSet.remove( v);
272         } else {
2730            bSet.remove( v);
274         }
2755    }
276  
277 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.