Coverage details for edu.uci.ics.jung.io.BipartiteGraphReader

LineHitsSource
1 /*
2  * Created on Apr 13, 2004
3  *
4  * Copyright (c) 2004, 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.io;
13  
14 import java.io.BufferedReader;
15 import java.io.IOException;
16 import java.io.Reader;
17 import java.util.Collection;
18 import java.util.LinkedList;
19 import java.util.List;
20  
21 import org.apache.commons.collections.Predicate;
22  
23 import edu.uci.ics.jung.graph.Edge;
24 import edu.uci.ics.jung.graph.Graph;
25 import edu.uci.ics.jung.graph.KPartiteGraph;
26 import edu.uci.ics.jung.graph.Vertex;
27 import edu.uci.ics.jung.graph.decorators.EdgeWeightLabeller;
28 import edu.uci.ics.jung.graph.decorators.StringLabeller;
29 import edu.uci.ics.jung.graph.decorators.StringLabeller.UniqueLabelException;
30 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
31 import edu.uci.ics.jung.graph.impl.KPartiteSparseGraph;
32 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
33 import edu.uci.ics.jung.graph.predicates.UserDatumVertexPredicate;
34 import edu.uci.ics.jung.utils.TypedVertexGenerator;
35 import edu.uci.ics.jung.utils.UserData;
36 import edu.uci.ics.jung.utils.VertexGenerator;
37  
38  
39 /**
40  *
41  * @author Joshua O'Madadhain
42  */
43 public class BipartiteGraphReader
44 {
45     /**
46      * The user data key for the vertices' partitions.
47      */
48     public final static String PARTITION = "edu.uci.ics.jung.io:Partition";
49     
50     /**
51      * The predicate for the vertices in partitions A and B.
52      */
531    public final static UserDatumVertexPredicate PART_A =
54         new UserDatumVertexPredicate(PARTITION, "vertex_ID_A");
551    public final static UserDatumVertexPredicate PART_B =
56         new UserDatumVertexPredicate(PARTITION, "vertex_ID_B");
57  
58     /**
59      * <p>If <code>true</code>, specifies that each line of input implicitly
60      * represents a list of edges, where the first token specifies one endpoint,
61      * and the subsequent tokens specify a sequence of opposite endpoints.
62      * Otherwise, each line of input represents a single edge.</p>
63      */
64     protected boolean asList;
65  
66     /**
67      * <p>If <code>true</code>, the edges created
68      * will be directed; otherwise, they will be undirected.
69      * In either case, the graph is constrained to accept only the
70      * specified edge type.</p>
71      *
72      * <p>NOTE: Currently, the data format specified only permits
73      * directed edges whose source is in partition A and whose
74      * destination is in partition B.</p>
75      */
76     protected boolean directed;
77     
78     /**
79      * <p>
80      * If <code>true</code>, parallel edges may
81      * be created if the edge is found more than once in the input file.
82      * Otherwise, each edge is labelled with a weight by an
83      * <code>EdgeWeightLabeller</code>, and the graph is created with the
84      * "no parallel edges" constraint.
85      * The weight of each edge in the non-parallel case is the number of times
86      * that the edge is represented in the input file (that is, the edge's multiplicity).
87      * </p>
88      */
89     protected boolean parallel;
90     
91     public BipartiteGraphReader(boolean asList, boolean directed, boolean parallel)
924    {
934        this.asList = asList;
944        this.directed = directed;
954        this.parallel = parallel;
964    }
97  
98     /**
99      * Creates a BipartiteGraphReader with default behavior (one edge per line,
100      * undirected, no parallel edges created).
101      */
102     public BipartiteGraphReader()
103     {
1040        this(false, false, false);
1050    }
106     
107     
108     /**
109      * <p>Creates a <code>KPartiteGraph</code> (where k = 2) based on connection
110      * data gathered from a Reader.
111      * The data must be in one of the two following formats:</p>
112      *
113      * <pre>
114      * a_1 b_1
115      * a_2 b_1
116      * a_2 b_2
117      * a_3 b_3 ...
118      * </pre>
119      *
120      * <p>or</p>
121      *
122      * <pre>
123      * a_1 b_1 b_2 b_3
124      * a_2 b_2 b_3
125      * a_3 b_3 ...
126      * </pre>
127      *
128      * <p>
129      * where <code>x_i</code> is a unique label (ID) for vertex <code>i</code>
130      * in partition <code>x</code>. Each line in the file defines an edge
131      * between the specified vertices. The vertices themselves are defined
132      * implicitly: if a label is read from the file for which no vertex yet
133      * exists, a new vertex is created and that label is attached to it.
134      * </p>
135      *
136      * <p>The first format is the default; the second is assumed if the
137      * <code>asList</code> flag is set to <code>true</code>. In
138      * the default format, everything after the first whitespace is
139      * interpreted as part of the label for the second vertex.</p>
140      *
141      * <p>
142      * Vertex labels are only required to be unique within their
143      * partitions. Each partition has its own <code>StringLabeller</code>,
144      * which is accessed via the key <code>VID_A</code> or <code>VID_B</code>,
145      * as appropriate.
146      * </p>
147      *
148      * <p>
149      * The end of the file may be artificially set by putting the string <code>end_of_file</code>
150      * on a line by itself.
151      * </p>
152      *
153      *
154      *
155      * @return the 2-partite graph loaded with these vertices, and labelled with two StringLabellers
156      * @throws
157      * IOException May occur in the course of reading from a stream.
158      */
159     public KPartiteGraph load(Reader reader) throws IOException
160     {
1617        List predicates = new LinkedList();
1627        predicates.add(PART_A);
1637        predicates.add(PART_B);
164         
1657        KPartiteGraph bg = new KPartiteSparseGraph(predicates, true);
166         
1677        Collection edge_constraints = bg.getEdgeConstraints();
1687        if (directed)
1691            edge_constraints.add(Graph.DIRECTED_EDGE);
170         else
1716            edge_constraints.add(Graph.UNDIRECTED_EDGE);
1727        if (!parallel)
1736            edge_constraints.add(Graph.NOT_PARALLEL_EDGE);
174  
1757        VertexGenerator vg = new TypedVertexGenerator(edge_constraints);
176         
1777        EdgeWeightLabeller ewl = EdgeWeightLabeller.getLabeller(bg);
178  
1797        BufferedReader br = new BufferedReader(reader);
180  
18114        while (br.ready())
182         {
183             // read the line in, break it into 2 parts (one for each
184             // vertex)
18514            String curLine = br.readLine();
18614            if (curLine == null || curLine.equals("end_of_file"))
1870                break;
1887            if (curLine.trim().length() == 0)
1890                continue;
190             String[] parts;
1917            if (asList)
1926                parts = curLine.trim().split("\\s+");
193             else
1941                parts = curLine.trim().split("\\s+", 2);
195  
196             // fetch/create vertices for each part of the string
1977            Vertex v_a = getOrCreateVertexByName(bg, vg, parts[0], PART_A);
198  
1997            int i = 1;
20024            while (i < parts.length)
201             {
20217                Vertex v_b = getOrCreateVertexByName(bg, vg, parts[i++], PART_B);
203  
20417                Edge e = v_a.findEdge(v_b);
20517                boolean absent = (e == null);
20617                if (absent || parallel)
207                 {
20816                    if (directed)
2093                        e = bg.addEdge(new DirectedSparseEdge(v_a, v_b));
210                     else
21113                        e = bg.addEdge(new UndirectedSparseEdge(v_a, v_b));
212                 }
21317                if (!parallel) // weight represents multiplicity of edge
214                 {
21515                    if (absent)
21614                        ewl.setWeight(e, 1);
217                     else
2181                        ewl.setWeight(e, ewl.getWeight(e) + 1);
219                 }
220             }
221         }
2227        br.close();
2237        reader.close();
2247        return bg;
225     }
226  
227     private static Vertex getOrCreateVertexByName(Graph bg, VertexGenerator vg,
228         String label, UserDatumVertexPredicate partition)
229     {
23024        StringLabeller vID_label = StringLabeller.getLabeller(bg, partition);
23124        Vertex v = (Vertex) vID_label.getVertex(label);
23224        if (v == null)
233         {
23422            v = (Vertex)vg.create();
23522            v.addUserDatum(partition.getKey(), partition.getDatum(), UserData.SHARED);
23622            bg.addVertex(v);
237             try
238             {
23922                vID_label.setLabel(v, label);
240             }
24122            catch (UniqueLabelException e1) {}
242         }
24324        return v;
244     }
245  
246     public static Predicate getPartition(Vertex v)
247     {
2480        if (PART_A.evaluate(v))
2490            return PART_A;
2500        else if (PART_B.evaluate(v))
2510            return PART_B;
252         else
2530            throw new IllegalArgumentException("Specified vertex " + v +
254                     "is not in any registered partition");
255     }
256     
257     public void setAsList(boolean asList)
258     {
2591        this.asList = asList;
2601    }
261     
262     public void setDirected(boolean directed)
263     {
2641        this.directed = directed;
2651    }
266     
267     public void setParallel(boolean parallel)
268     {
2691        this.parallel = parallel;
2701    }
271  
272     public boolean isAsList()
273     {
2740        return asList;
275     }
276  
277     public boolean isDirected()
278     {
2790        return directed;
280     }
281  
282     public boolean isParallel()
283     {
2840        return parallel;
285     }
286 }

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.