Line | Hits | Source |
---|---|---|
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 | package edu.uci.ics.jung.io; | |
11 | ||
12 | import java.io.BufferedReader; | |
13 | import java.io.BufferedWriter; | |
14 | import java.io.FileReader; | |
15 | import java.io.FileWriter; | |
16 | import java.io.IOException; | |
17 | import java.io.Reader; | |
18 | import java.text.ParseException; | |
19 | import java.util.HashSet; | |
20 | import java.util.Iterator; | |
21 | import java.util.Set; | |
22 | import java.util.StringTokenizer; | |
23 | ||
24 | import edu.uci.ics.jung.exceptions.FatalException; | |
25 | import edu.uci.ics.jung.graph.DirectedEdge; | |
26 | import edu.uci.ics.jung.graph.Edge; | |
27 | import edu.uci.ics.jung.graph.Graph; | |
28 | import edu.uci.ics.jung.graph.UndirectedEdge; | |
29 | import edu.uci.ics.jung.graph.Vertex; | |
30 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
31 | import edu.uci.ics.jung.graph.decorators.StringLabeller; | |
32 | import edu.uci.ics.jung.graph.impl.DirectedSparseGraph; | |
33 | import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph; | |
34 | import edu.uci.ics.jung.utils.GraphUtils; | |
35 | import edu.uci.ics.jung.utils.MutableDouble; | |
36 | import edu.uci.ics.jung.utils.Pair; | |
37 | import edu.uci.ics.jung.utils.PredicateUtils; | |
38 | import edu.uci.ics.jung.utils.UserData; | |
39 | ||
40 | /** | |
41 | * A file reader for Pajek .net files. At the moment, only supports the | |
42 | * part of the specification that defines: | |
43 | * <ul> | |
44 | * <li> node ids (must be ordered from 1 to n) | |
45 | * <li> node labels (must be in quotes) | |
46 | * <li> directed edge connections (single or list) | |
47 | * <li> undirected edge connections (single or list) | |
48 | * <li> edge weights (1 or more can be specified; not compatible with | |
49 | * edges specified in list form) | |
50 | * </ul> <p> | |
51 | * | |
52 | * Here is an example format for a directed graph without edge weights | |
53 | * and edges specified in list form: <br> | |
54 | * <pre> | |
55 | * *vertices <# of vertices> | |
56 | * 1 "a" | |
57 | * 2 "b" | |
58 | * 3 "c" | |
59 | * *arcslist | |
60 | * 1 2 3 | |
61 | * 2 3 | |
62 | * </pre> | |
63 | * | |
64 | * Here is an example format for an undirected graph with edge weights | |
65 | * and edges specified in non-list form: <br> | |
66 | * <pre> | |
67 | * *vertices <# of vertices> | |
68 | * 1 "a" | |
69 | * 2 "b" | |
70 | * 3 "c" | |
71 | * *edges | |
72 | * 1 2 0.1 | |
73 | * 1 3 0.9 | |
74 | * 2 3 1.0 | |
75 | * </pre> | |
76 | * @author Scott White, Joshua O'Madadhain | |
77 | * @deprecated As of version 1.4, replaced by {@link PajekNetReader} and {@link PajekNetWriter} | |
78 | * @see "'Pajek - Program for Large Network Analysis', Vladimir Batagelj and Andrej Mrvar, www.ucm.es/info/pecar/pajek.pdf" | |
79 | */ | |
80 | public class PajekNetFile implements GraphFile { | |
81 | public final static String EDGE_WEIGHT = "jung.io.PajekNetFile.EdgeWeight"; | |
82 | private String[] mEdgeKeys; | |
83 | private boolean mCreateDirectedOnly; | |
84 | ||
85 | /** | |
86 | * Default constructor for pajek graph reader | |
87 | */ | |
88 | 4 | public PajekNetFile() { |
89 | 4 | mCreateDirectedOnly = false; |
90 | 4 | } |
91 | ||
92 | /** | |
93 | * Constructor which takes in the user datum keys for the edge weights | |
94 | * @param edgeKeys the user datum keys the algorithm should use to store the edge weights (as MutableDoubles) | |
95 | */ | |
96 | 0 | public PajekNetFile(String[] edgeKeys) { |
97 | 0 | mEdgeKeys = edgeKeys; |
98 | 0 | mCreateDirectedOnly = false; |
99 | 0 | } |
100 | ||
101 | /** | |
102 | * retrieves the set of edge keys the algorithm will use to store the edge weights | |
103 | * @return the user datum keys the algorithm should is using to store the edge weights (as MutableDoubles) | |
104 | */ | |
105 | public String[] getEdgeKeys() { | |
106 | 30 | return mEdgeKeys; |
107 | } | |
108 | ||
109 | /** | |
110 | * set the edge the algorithm will use to store the edge weights | |
111 | * @param edgeKeys the user datum keys the algorithm should use to store the edge weights (as MutableDoubles) | |
112 | */ | |
113 | public void setEdgeKeys(String[] edgeKeys) { | |
114 | 0 | this.mEdgeKeys = edgeKeys; |
115 | 0 | } |
116 | ||
117 | /** | |
118 | * Loads a graph from disk for the given .net file | |
119 | * If the edges are directed then a directed graph will be created, otherwise an undirected graph will be created | |
120 | * @param filename the fully specified file name of the pajek .net file | |
121 | * @return the corresponding graph | |
122 | */ | |
123 | public Graph load(String filename) { | |
124 | try { | |
125 | 6 | Reader reader = new FileReader(filename); |
126 | 5 | Graph graph = load(reader); |
127 | 5 | reader.close(); |
128 | 5 | return graph; |
129 | 1 | } catch (IOException ioe) { |
130 | 1 | throw new FatalException("Error in loading file " + filename, ioe); |
131 | } | |
132 | } | |
133 | ||
134 | /** | |
135 | * Forces a graph that is normally undirected to be loaded in as its directed equivalent | |
136 | * @param createDirectedOnly if true, force graph to be directed, false to not force this constraint | |
137 | */ | |
138 | public void setCreateDirectedOnly(boolean createDirectedOnly) { | |
139 | 0 | mCreateDirectedOnly = createDirectedOnly; |
140 | 0 | } |
141 | ||
142 | /** | |
143 | * Loads a graph for the given BufferedReader (where the data is assumed to be in Pajek NET format). | |
144 | * If the edges are directed then a directed graph will be created, otherwise an undirected | |
145 | * graph will be created. | |
146 | * @param read the data stream that contains the graph data in .net format | |
147 | * @return the corresponding graph | |
148 | */ | |
149 | public Graph load(Reader read) { | |
150 | ||
151 | /* | |
152 | * Current running buglist: | |
153 | * * Crashes on *Network tag | |
154 | * * unique label exception is possible | |
155 | * * doesn't handle *PArtition, e.g. | |
156 | // * * only one tag of "arc" or "edge" | |
157 | */ | |
158 | 5 | BufferedReader reader = new BufferedReader( read ); |
159 | 5 | int currentSourceId = -1; |
160 | 5 | String currentLine = null; |
161 | try { | |
162 | 5 | StringTokenizer tokenizer = null; |
163 | 5 | currentLine = reader.readLine(); |
164 | 5 | tokenizer = new StringTokenizer(currentLine); |
165 | 5 | if (!tokenizer.nextToken().toLowerCase().startsWith("*vertices")) { |
166 | 0 | throw new ParseException("Pajek file parse error: '*vertices' not first token", 0); |
167 | } | |
168 | 5 | int numVertices = Integer.parseInt(tokenizer.nextToken()); |
169 | 5 | Graph directedGraph = new DirectedSparseGraph(); |
170 | 5 | GraphUtils.addVertices( directedGraph, numVertices ); |
171 | 5 | Indexer directedGraphIndexer = Indexer.newIndexer( directedGraph , 1); |
172 | ||
173 | 5 | Graph undirectedGraph = null; |
174 | 5 | Indexer undirectedGraphIndexer = null; |
175 | 5 | StringLabeller undirectedLabeler = null; |
176 | ||
177 | 5 | if (!mCreateDirectedOnly) { |
178 | 5 | undirectedGraph = new UndirectedSparseGraph(); |
179 | 5 | GraphUtils.addVertices(undirectedGraph,numVertices); |
180 | 5 | undirectedGraphIndexer = Indexer.newIndexer( undirectedGraph , 1); |
181 | 5 | undirectedLabeler = StringLabeller.getLabeller(undirectedGraph); |
182 | } | |
183 | ||
184 | 5 | StringLabeller directedLabeler = StringLabeller.getLabeller(directedGraph); |
185 | ||
186 | 5 | String currentVertexLabel = null; |
187 | 5 | Vertex currentVertex = null; |
188 | ||
189 | // currentLine = reader.readLine().trim(); | |
190 | 30 | while (!(currentLine = reader.readLine().trim()).startsWith("*")) { |
191 | 25 | tokenizer = new StringTokenizer(currentLine); |
192 | 25 | currentSourceId = Integer.parseInt(tokenizer.nextToken()); |
193 | ||
194 | 25 | int openQuotePos = currentLine.indexOf("\""); |
195 | 25 | int closeQuotePos = currentLine.lastIndexOf("\""); |
196 | ||
197 | 25 | if ((openQuotePos > 0) && (openQuotePos != closeQuotePos)) { |
198 | 0 | currentVertexLabel = currentLine.substring(openQuotePos+1,closeQuotePos); |
199 | 0 | currentVertex = (Vertex)directedGraphIndexer.getVertex(currentSourceId); |
200 | 0 | directedLabeler.setLabel(currentVertex,currentVertexLabel); |
201 | ||
202 | 0 | if (!mCreateDirectedOnly) { |
203 | 0 | currentVertex = (Vertex)undirectedGraphIndexer.getVertex(currentSourceId); |
204 | 0 | undirectedLabeler.setLabel(currentVertex,currentVertexLabel); |
205 | } | |
206 | 25 | continue; |
207 | } | |
208 | } | |
209 | ||
210 | 5 | int currentTargetId = -1; |
211 | 5 | boolean directed = false; |
212 | 5 | boolean isList = false; |
213 | 5 | Graph graph = null; |
214 | 5 | Indexer id = null; |
215 | 5 | if (currentLine.toLowerCase().indexOf("list") >= 0) { |
216 | 0 | isList = true; |
217 | } | |
218 | 5 | if (currentLine.toLowerCase().indexOf("arc") >= 0) { |
219 | 3 | directed = true; |
220 | 3 | graph = directedGraph; |
221 | 3 | undirectedGraph = null; |
222 | 3 | undirectedLabeler = null; |
223 | 3 | id = directedGraphIndexer; |
224 | } else { | |
225 | 2 | if (mCreateDirectedOnly) { |
226 | 0 | graph = directedGraph; |
227 | 0 | undirectedGraph = null; |
228 | 0 | undirectedGraphIndexer = null; |
229 | 0 | directedLabeler = null; |
230 | 0 | id = directedGraphIndexer; |
231 | } else { | |
232 | 2 | graph = undirectedGraph; |
233 | 2 | directedGraph = null; |
234 | 2 | directedGraphIndexer = null; |
235 | 2 | id = undirectedGraphIndexer; |
236 | } | |
237 | } | |
238 | ||
239 | 36 | while ((currentLine = reader.readLine()) != null) |
240 | { | |
241 | 31 | currentLine = currentLine.trim(); |
242 | 31 | if (currentLine.length() == 0) { |
243 | 0 | break; |
244 | } | |
245 | // right now we only support strictly directed or strictly undirected graphs | |
246 | ||
247 | 31 | if (currentLine.startsWith("*" )) |
248 | 1 | continue; |
249 | // else if (currentLine.startsWith("*")) { | |
250 | // throw new FatalException("*edge/arcs(list) can only appear once."); | |
251 | // } | |
252 | 30 | tokenizer = new StringTokenizer(currentLine); |
253 | 30 | currentSourceId = Integer.parseInt(tokenizer.nextToken()); |
254 | 30 | Edge currentEdge1 = null; |
255 | 30 | Edge currentEdge2 = null; |
256 | ||
257 | 30 | while (tokenizer.hasMoreTokens()) { |
258 | 30 | currentTargetId = Integer.parseInt(tokenizer.nextToken()); |
259 | ||
260 | 30 | if (currentSourceId == currentTargetId) { |
261 | 0 | break; |
262 | } | |
263 | ||
264 | 30 | Vertex source = (Vertex)id.getVertex(currentSourceId); |
265 | 30 | Vertex target = (Vertex)id.getVertex(currentTargetId); |
266 | 30 | if(!source.isPredecessorOf(target)) { |
267 | 30 | currentEdge1 = GraphUtils.addEdge( graph, source,target); |
268 | } | |
269 | ||
270 | 30 | if (mCreateDirectedOnly && !directed) { |
271 | 0 | if(!target.isPredecessorOf(source)) { |
272 | 0 | currentEdge2 = GraphUtils.addEdge( graph, target,source); |
273 | } | |
274 | } | |
275 | ||
276 | 30 | String[] edgeKeys = getEdgeKeys(); |
277 | 30 | if (!isList && edgeKeys != null) { |
278 | 0 | int numTokens = tokenizer.countTokens(); |
279 | 0 | numTokens = Math.min(numTokens,edgeKeys.length); |
280 | 0 | for (int edgeDescIdx=0;edgeDescIdx<numTokens;edgeDescIdx++) { |
281 | 0 | double val = Double.parseDouble(tokenizer.nextToken()); |
282 | 0 | currentEdge1.setUserDatum(edgeKeys[edgeDescIdx],new MutableDouble(val),UserData.SHARED); |
283 | 0 | if (currentEdge2 != null) { |
284 | 0 | currentEdge2.setUserDatum(edgeKeys[edgeDescIdx],new MutableDouble(val),UserData.SHARED); |
285 | } | |
286 | ||
287 | } | |
288 | 30 | } else if (isList) { |
289 | 0 | continue; |
290 | } | |
291 | break; | |
292 | } | |
293 | } | |
294 | 5 | return graph; |
295 | } | |
296 | 0 | catch (IOException ioe) |
297 | { | |
298 | 0 | throw new FatalException("I/O error in reading file: ", ioe); |
299 | } | |
300 | 0 | catch (ParseException pe) |
301 | { | |
302 | 0 | throw new FatalException("Parse exception in reading graph", pe); |
303 | } | |
304 | 0 | catch (StringLabeller.UniqueLabelException sle) |
305 | { | |
306 | 0 | throw new FatalException("Repeated vertex label in graph", sle); |
307 | } | |
308 | // catch (Exception re) { | |
309 | // throw new FatalException("Fatal exception calling PajekNetFile.load(...)", re); | |
310 | // } | |
311 | } | |
312 | ||
313 | /** | |
314 | * Writes <code>graph</code> to the file specified by <code>filename</code> | |
315 | * in the Pajek NET format. | |
316 | * @param graph the graph to save | |
317 | * @param filename the fully specified file name where the graph is to be saved to disk | |
318 | */ | |
319 | public void save(Graph graph,String filename) { | |
320 | ||
321 | /* | |
322 | * TODO: Changes we might want to make: | |
323 | * - convert to writing out with a Writer, not a String filename spec | |
324 | * - optionally writing out in list form | |
325 | */ | |
326 | ||
327 | try { | |
328 | 5 | BufferedWriter writer = new BufferedWriter( new FileWriter(filename)); |
329 | 5 | writer.write("*Vertices " + graph.getVertices().size() + "\n"); |
330 | 5 | Vertex currentVertex = null; |
331 | ||
332 | 5 | Indexer id = Indexer.newIndexer( graph ,1 ) ; |
333 | 5 | StringLabeller labeller = StringLabeller.getLabeller(graph); |
334 | 5 | for (Iterator i = graph.getVertices().iterator(); i.hasNext();) { |
335 | 25 | currentVertex = (Vertex) i.next(); |
336 | 25 | if (labeller.getLabel(currentVertex) != null) { |
337 | 0 | writer.write(id.getIndex(currentVertex) + " \"" + labeller.getLabel(currentVertex) + "\"\n"); |
338 | } else { | |
339 | 25 | writer.write(id.getIndex(currentVertex) + "\n"); |
340 | } | |
341 | } | |
342 | ||
343 | 5 | Set d_set = new HashSet(); |
344 | 5 | Set u_set = new HashSet(); |
345 | ||
346 | 5 | boolean directed = PredicateUtils.enforcesDirected(graph); |
347 | 5 | boolean undirected = PredicateUtils.enforcesUndirected(graph); |
348 | // if it's strictly one or the other, no need to create extra sets | |
349 | 5 | if (directed) |
350 | 2 | d_set = graph.getEdges(); |
351 | 5 | if (undirected) |
352 | 2 | u_set = graph.getEdges(); |
353 | 5 | if (!directed && !undirected) // mixed-mode graph |
354 | { | |
355 | 1 | d_set = PredicateUtils.getEdges(graph, Graph.DIRECTED_EDGE); |
356 | 1 | u_set = PredicateUtils.getEdges(graph, Graph.UNDIRECTED_EDGE); |
357 | } | |
358 | ||
359 | // write out directed edges | |
360 | 5 | if (! d_set.isEmpty()) |
361 | 3 | writer.write("*Arcs\n"); |
362 | 5 | for (Iterator eIt = d_set.iterator(); eIt.hasNext();) |
363 | { | |
364 | 15 | DirectedEdge currentEdge = (DirectedEdge) eIt.next(); |
365 | 15 | Vertex source = currentEdge.getSource(); |
366 | 15 | Vertex target = currentEdge.getDest(); |
367 | 15 | writer.write(id.getIndex(source) + " " + id.getIndex(target) + "\n"); |
368 | } | |
369 | ||
370 | // write out undirected edges | |
371 | 5 | if (! u_set.isEmpty()) |
372 | 3 | writer.write("*Edges\n"); |
373 | 5 | for (Iterator eIt = u_set.iterator(); eIt.hasNext();) |
374 | { | |
375 | 15 | UndirectedEdge e = (UndirectedEdge)eIt.next(); |
376 | 15 | Pair endpoints = e.getEndpoints(); |
377 | 15 | Vertex v1 = (Vertex)endpoints.getFirst(); |
378 | 15 | Vertex v2 = (Vertex)endpoints.getSecond(); |
379 | 15 | writer.write(id.getIndex(v1) + " " + id.getIndex(v2) + "\n"); |
380 | } | |
381 | ||
382 | 5 | writer.close(); |
383 | ||
384 | 0 | } catch (Exception e) { |
385 | 0 | throw new FatalException("Error saving file: " + filename,e); |
386 | 5 | } |
387 | 5 | } |
388 | ||
389 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |