| 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. |