Line | Hits | Source |
---|---|---|
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 | */ | |
53 | 1 | public final static UserDatumVertexPredicate PART_A = |
54 | new UserDatumVertexPredicate(PARTITION, "vertex_ID_A"); | |
55 | 1 | 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) | |
92 | 4 | { |
93 | 4 | this.asList = asList; |
94 | 4 | this.directed = directed; |
95 | 4 | this.parallel = parallel; |
96 | 4 | } |
97 | ||
98 | /** | |
99 | * Creates a BipartiteGraphReader with default behavior (one edge per line, | |
100 | * undirected, no parallel edges created). | |
101 | */ | |
102 | public BipartiteGraphReader() | |
103 | { | |
104 | 0 | this(false, false, false); |
105 | 0 | } |
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 | { | |
161 | 7 | List predicates = new LinkedList(); |
162 | 7 | predicates.add(PART_A); |
163 | 7 | predicates.add(PART_B); |
164 | ||
165 | 7 | KPartiteGraph bg = new KPartiteSparseGraph(predicates, true); |
166 | ||
167 | 7 | Collection edge_constraints = bg.getEdgeConstraints(); |
168 | 7 | if (directed) |
169 | 1 | edge_constraints.add(Graph.DIRECTED_EDGE); |
170 | else | |
171 | 6 | edge_constraints.add(Graph.UNDIRECTED_EDGE); |
172 | 7 | if (!parallel) |
173 | 6 | edge_constraints.add(Graph.NOT_PARALLEL_EDGE); |
174 | ||
175 | 7 | VertexGenerator vg = new TypedVertexGenerator(edge_constraints); |
176 | ||
177 | 7 | EdgeWeightLabeller ewl = EdgeWeightLabeller.getLabeller(bg); |
178 | ||
179 | 7 | BufferedReader br = new BufferedReader(reader); |
180 | ||
181 | 14 | while (br.ready()) |
182 | { | |
183 | // read the line in, break it into 2 parts (one for each | |
184 | // vertex) | |
185 | 14 | String curLine = br.readLine(); |
186 | 14 | if (curLine == null || curLine.equals("end_of_file")) |
187 | 0 | break; |
188 | 7 | if (curLine.trim().length() == 0) |
189 | 0 | continue; |
190 | String[] parts; | |
191 | 7 | if (asList) |
192 | 6 | parts = curLine.trim().split("\\s+"); |
193 | else | |
194 | 1 | parts = curLine.trim().split("\\s+", 2); |
195 | ||
196 | // fetch/create vertices for each part of the string | |
197 | 7 | Vertex v_a = getOrCreateVertexByName(bg, vg, parts[0], PART_A); |
198 | ||
199 | 7 | int i = 1; |
200 | 24 | while (i < parts.length) |
201 | { | |
202 | 17 | Vertex v_b = getOrCreateVertexByName(bg, vg, parts[i++], PART_B); |
203 | ||
204 | 17 | Edge e = v_a.findEdge(v_b); |
205 | 17 | boolean absent = (e == null); |
206 | 17 | if (absent || parallel) |
207 | { | |
208 | 16 | if (directed) |
209 | 3 | e = bg.addEdge(new DirectedSparseEdge(v_a, v_b)); |
210 | else | |
211 | 13 | e = bg.addEdge(new UndirectedSparseEdge(v_a, v_b)); |
212 | } | |
213 | 17 | if (!parallel) // weight represents multiplicity of edge |
214 | { | |
215 | 15 | if (absent) |
216 | 14 | ewl.setWeight(e, 1); |
217 | else | |
218 | 1 | ewl.setWeight(e, ewl.getWeight(e) + 1); |
219 | } | |
220 | } | |
221 | } | |
222 | 7 | br.close(); |
223 | 7 | reader.close(); |
224 | 7 | return bg; |
225 | } | |
226 | ||
227 | private static Vertex getOrCreateVertexByName(Graph bg, VertexGenerator vg, | |
228 | String label, UserDatumVertexPredicate partition) | |
229 | { | |
230 | 24 | StringLabeller vID_label = StringLabeller.getLabeller(bg, partition); |
231 | 24 | Vertex v = (Vertex) vID_label.getVertex(label); |
232 | 24 | if (v == null) |
233 | { | |
234 | 22 | v = (Vertex)vg.create(); |
235 | 22 | v.addUserDatum(partition.getKey(), partition.getDatum(), UserData.SHARED); |
236 | 22 | bg.addVertex(v); |
237 | try | |
238 | { | |
239 | 22 | vID_label.setLabel(v, label); |
240 | } | |
241 | 22 | catch (UniqueLabelException e1) {} |
242 | } | |
243 | 24 | return v; |
244 | } | |
245 | ||
246 | public static Predicate getPartition(Vertex v) | |
247 | { | |
248 | 0 | if (PART_A.evaluate(v)) |
249 | 0 | return PART_A; |
250 | 0 | else if (PART_B.evaluate(v)) |
251 | 0 | return PART_B; |
252 | else | |
253 | 0 | throw new IllegalArgumentException("Specified vertex " + v + |
254 | "is not in any registered partition"); | |
255 | } | |
256 | ||
257 | public void setAsList(boolean asList) | |
258 | { | |
259 | 1 | this.asList = asList; |
260 | 1 | } |
261 | ||
262 | public void setDirected(boolean directed) | |
263 | { | |
264 | 1 | this.directed = directed; |
265 | 1 | } |
266 | ||
267 | public void setParallel(boolean parallel) | |
268 | { | |
269 | 1 | this.parallel = parallel; |
270 | 1 | } |
271 | ||
272 | public boolean isAsList() | |
273 | { | |
274 | 0 | return asList; |
275 | } | |
276 | ||
277 | public boolean isDirected() | |
278 | { | |
279 | 0 | return directed; |
280 | } | |
281 | ||
282 | public boolean isParallel() | |
283 | { | |
284 | 0 | return parallel; |
285 | } | |
286 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |