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

LineHitsSource
1 /*
2  * Created on May 3, 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.awt.geom.Point2D;
15 import java.io.BufferedReader;
16 import java.io.FileReader;
17 import java.io.IOException;
18 import java.io.Reader;
19 import java.util.StringTokenizer;
20  
21 import org.apache.commons.collections.Predicate;
22 import org.apache.commons.collections.functors.OrPredicate;
23  
24 import edu.uci.ics.jung.exceptions.FatalException;
25 import edu.uci.ics.jung.graph.Edge;
26 import edu.uci.ics.jung.graph.Graph;
27 import edu.uci.ics.jung.graph.Vertex;
28 import edu.uci.ics.jung.graph.decorators.Indexer;
29 import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;
30 import edu.uci.ics.jung.graph.decorators.StringLabeller;
31 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
32 import edu.uci.ics.jung.graph.impl.SparseGraph;
33 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
34 import edu.uci.ics.jung.graph.predicates.ParallelEdgePredicate;
35 import edu.uci.ics.jung.utils.PredicateUtils;
36 import edu.uci.ics.jung.utils.TypedVertexGenerator;
37 import edu.uci.ics.jung.utils.UserData;
38 import edu.uci.ics.jung.utils.VertexGenerator;
39 import edu.uci.ics.jung.visualization.DefaultSettableVertexLocationFunction;
40 import edu.uci.ics.jung.visualization.SettableVertexLocationFunction;
41  
42  
43 /**
44  * Reads a <code>Graph</code> from a Pajek NET formatted source.
45  *
46  * <p>If the edge constraints specify that the graph is strictly undirected,
47  * and an "*Arcs" section is encountered, or if the edge constraints specify that the
48  * graph is strictly directed, and an "*Edges" section is encountered,
49  * an <code>IllegalArgumentException</code> is thrown.</p>
50  *
51  * <p>If the edge constraints do not permit parallel edges, only the first encountered
52  * of a set of parallel edges will be read; subsequent edges in that set will be ignored.</p>
53  *
54  * <p>More restrictive edge constraints will cause vertices to be generated
55  * that are more time- and space-efficient.</p>
56  *
57  * At the moment, only supports the
58  * part of the specification that defines:
59  * <ul>
60  * <li> vertex ids (each must have a value from 1 to n, where n is the number of vertices)
61  * <li> vertex labels (must be in quotes if interrupted by whitespace)
62  * <li> directed edge connections (single or list)
63  * <li> undirected edge connections (single or list)
64  * <li> edge weights (not compatible with edges specified in list form)
65  * <br><b>note</b>: this version of PajekNetReader does not support multiple edge
66  * weights, as PajekNetFile does; this behavior is consistent with the NET format.
67  * <li/> vertex locations (x and y; z coordinate is ignored)
68  * </ul> <p>
69  *
70  * Here is an example format for a directed graph without edge weights
71  * and edges specified in list form: <br>
72  * <pre>
73  * *vertices <# of vertices>
74  * 1 "a"
75  * 2 "b"
76  * 3 "c"
77  * *arcslist
78  * 1 2 3
79  * 2 3
80  * </pre>
81  *
82  * Here is an example format for an undirected graph with edge weights
83  * and edges specified in non-list form: <br>
84  * <pre>
85  * *vertices <# of vertices>
86  * 1 "a"
87  * 2 "b"
88  * 3 "c"
89  * *edges
90  * 1 2 0.1
91  * 1 3 0.9
92  * 2 3 1.0
93  * </pre>
94  *
95  * @author Joshua O'Madadhain
96  * @see "'Pajek - Program for Analysis and Visualization of Large Networks', Vladimir Batagelj and Andrej Mrvar, http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf"
97  */
98 public class PajekNetReader
99 {
100     protected boolean unique_labels;
101  
102     /**
103      * The key used to identify the vertex labels (if any) created by this class.
104      */
105     public static final String LABEL = "jung.io.PajekNetReader.LABEL";
106  
107     /**
108      * The user data key used to retrieve the vertex locations (if any) defined by this class.
109      */
110     public static final String LOCATIONS = "jung.io.PajekNetReader.LOCATIONS";
111     
112     protected SettableVertexLocationFunction v_locations;
1135    protected boolean get_locations = false;
114     
115     /**
116      * Used to specify whether the most recently read line is a
117      * Pajek-specific tag.
118      */
1191    private static final Predicate v_pred = new TagPred("*vertices");
1201    private static final Predicate a_pred = new TagPred("*arcs");
1211    private static final Predicate e_pred = new TagPred("*edges");
1221    private static final Predicate t_pred = new TagPred("*");
1231    private static final Predicate c_pred = OrPredicate.getInstance(a_pred, e_pred);
1241    protected static final Predicate l_pred = ListTagPred.getInstance();
1251    protected static final Predicate p_pred = ParallelEdgePredicate.getInstance();
126     
127     /**
128      * Creates a PajekNetReader with the specified labeling behavior, which does not
129      * read location information (if any).
130      *
131      * @see #PajekNetReader(boolean, boolean)
132      */
133     public PajekNetReader(boolean unique_labels)
134     {
1350        this(unique_labels, false);
1360    }
137     
138     /**
139      * Creates a PajekNetReader with the specified labeling behavior and
140      * location assignment behavior.
141      *
142      * <p>If <code>unique_labels</code> is true, vertices will be labelled
143      * using a <code>StringLabeller</code> with key <code>jung.io.PajekNetReader.LABEL</code>.
144      * Otherwise, they will be labeled with a user data <code>String</code> with key
145      * <code>PajekNetReader.LABEL</code>. (Vertices that have no apparent label
146      * information will not be labelled.)</p>
147      *
148      * <p>If <code>get_locations</code> is true, each vertex line in the file
149      * will be assumed to contain (x,y) coordinates in the range [0,1]; if any line
150      * lacks this data, an <code>IllegalArgumentException</code> will be thrown. (The Pajek
151      * format assumes coordinates are (x,y,z) but we ignore the z-coordinate.) Location
152      * data will be stored in a <code>SettabelVertexLocationDecorator</code> instance
153      * in the graph's user data with key<code>jung.io.PajekNetReader.LOCATIONS</code>.</p>
154      */
155     public PajekNetReader(boolean unique_labels, boolean get_locations)
1565    {
1575        this.unique_labels = unique_labels;
1585        this.get_locations = get_locations;
1595        if (get_locations)
1601            this.v_locations = new DefaultSettableVertexLocationFunction();
1615    }
162     
163     /**
164      * Creates a PajekNetReader with the specified labeling behavior and
165      * location assignment behavior.
166      *
167      * <p>If <code>unique_labels</code> is true, vertices will be labelled
168      * using a <code>StringLabeller</code> with key <code>jung.io.PajekNetReader.LABEL</code>.
169      * Otherwise, they will be labeled with a user data <code>String</code> with key
170      * <code>PajekNetReader.LABEL</code>. (Vertices that have no apparent label
171      * information will not be labelled.)</p>
172      *
173      * <p>If <code>get_locations</code> is true, each vertex line in the file
174      * will be assumed to contain (x,y) coordinates in the range [0,1]; if any line
175      * lacks this data, an <code>IllegalArgumentException</code> will be thrown. (The Pajek
176      * format assumes coordinates are (x,y,z) but we ignore the z-coordinate.) Location
177      * data will be stored in <code>v_locations</code>, a reference to which will be
178      * stored in the graph's user data with key <code>jung.io.PajekNetReader.LOCATIONS</code>.</p>
179      */
180     public PajekNetReader(boolean unique_labels, SettableVertexLocationFunction v_locations)
1810    {
1820        this.unique_labels = unique_labels;
1830        this.get_locations = true;
1840        this.v_locations = v_locations;
1850    }
186     
187     /**
188      * Creates a PajekNetReader whose labels are not required to be unique.
189      */
190     public PajekNetReader()
191     {
1924        this(false, false);
1934    }
194     
195     /**
196      * Returns <code>load(filename, new SparseGraph(), null)</code>.
197      * @throws IOException
198      */
199     public Graph load(String filename) throws IOException
200     {
2016        return load(filename, new SparseGraph(), null);
202     }
203  
204     /**
205      * Returns <code>load(filename, new SparseGraph(), nev)</code>.
206      * @throws IOException
207      */
208     public Graph load(String filename, NumberEdgeValue nev) throws IOException
209     {
2101        return load(filename, new SparseGraph(), nev);
211     }
212     
213     /**
214      * Returns <code>load(filename, g, null)</code>.
215      * @throws IOException
216      */
217     public Graph load(String filename, Graph g) throws IOException
218     {
2190        return load(filename, g, null);
220     }
221     
222     /**
223      * Creates a <code>FileReader</code> from <code>filename</code>, calls
224      * <code>load(reader, g, nev)</code>, closes the reader, and returns
225      * the resultant graph.
226      * @throws IOException
227      */
228     public Graph load(String filename, Graph g, NumberEdgeValue nev) throws IOException
229     {
2307        Reader reader = new FileReader(filename);
2316        Graph graph = load(reader, g, nev);
2326        reader.close();
2336        return graph;
234     }
235     
236     /**
237      * Returns <code>load(reader, g, null)</code>.
238      * @throws IOException
239      */
240     public Graph load(Reader reader, Graph g) throws IOException
241     {
2420        return load(reader, g, null);
243     }
244     
245     /**
246      * Returns <code>load(reader, new SparseGraph(), nev)</code>.
247      * @throws IOException
248      */
249     public Graph load(Reader reader, NumberEdgeValue nev) throws IOException
250     {
2510        return load(reader, new SparseGraph(), nev);
252     }
253     
254     /**
255      * Returns <code>load(reader, new SparseGraph(), null)</code>.
256      * @throws IOException
257      */
258     public Graph load(Reader reader) throws IOException
259     {
2601        return load(reader, new SparseGraph(), null);
261     }
262     
263     /**
264      * Returns <code>load(reader, g, nev, new TypedVertexGenerator(g))</code>.
265      * @throws IOException
266      * @see edu.uci.ics.jung.utils.TypedVertexGenerator
267      */
268     public Graph load(Reader reader, Graph g, NumberEdgeValue nev) throws IOException
269     {
2707        return load(reader, g, nev, new TypedVertexGenerator(g));
271     }
272     
273     /**
274      * Populates the graph <code>g</code> with the graph represented by the
275      * Pajek-format data supplied by <code>reader</code>. Stores edge weights,
276      * if any, according to <code>nev</code> (if non-null).
277      * Any existing vertices/edges of <code>g</code>, if any, are unaffected.
278      * The edge data are filtered according to <code>g</code>'s constraints, if any; thus, if
279      * <code>g</code> only accepts directed edges, any undirected edges in the
280      * input are ignored.
281      * Vertices are created with the generator <code>vg</code>. The user is responsible
282      * for supplying a generator whose output is compatible with this graph and its contents;
283      * users that don't want to deal with this issue may use a <code>TypedVertexGenerator</code>
284      * or call <code>load(reader, g, nev)</code> for a default generator.
285      * @throws IOException
286      */
287     public Graph load(Reader reader, Graph g, NumberEdgeValue nev, VertexGenerator vg) throws IOException
288     {
2897        BufferedReader br = new BufferedReader(reader);
290                 
291         // ignore everything until we see '*Vertices'
2927        String curLine = skip(br, v_pred);
293         
2947        if (curLine == null) // no vertices in the graph; return empty graph
2950            return g;
296         
2977        if (get_locations)
2981            g.addUserDatum(LOCATIONS, v_locations, UserData.SHARED);
299         
300         // create appropriate number of vertices
3017        StringTokenizer st = new StringTokenizer(curLine);
3027        st.nextToken(); // skip past "*vertices";
3037        int num_vertices = Integer.parseInt(st.nextToken());
30440        for (int i = 1; i <= num_vertices; i++)
30533            g.addVertex(vg.create());
3067        Indexer id = Indexer.getIndexer(g);
307  
308         // read vertices until we see any Pajek format tag ('*...')
3097        curLine = null;
31040        while (br.ready())
311         {
31240            curLine = br.readLine();
31340            if (curLine == null || t_pred.evaluate(curLine))
3147                break;
31533            if (curLine == "") // skip blank lines
3160                continue;
317             
318             try
319             {
32033                readVertex(curLine, id, num_vertices);
321             }
3220            catch (IllegalArgumentException iae)
323             {
3240                br.close();
3250                reader.close();
3260                throw iae;
32733            }
328         }
329  
330         // skip over the intermediate stuff (if any)
331         // and read the next arcs/edges section that we find
3327        curLine = readArcsOrEdges(curLine, br, g, nev);
333  
334         // ditto
3357        readArcsOrEdges(curLine, br, g, nev);
336         
3377        br.close();
3387        reader.close();
339         
3407        return g;
341     }
342  
343     /**
344      * Parses <code>curLine</code> as a reference to a vertex, and optionally assigns
345      * label and location information.
346      * @throws IOException
347      */
348     private void readVertex(String curLine, Indexer id, int num_vertices) throws IOException
349     {
350         Vertex v;
35133        String[] parts = null;
35233        int coord_idx = -1; // index of first coordinate in parts; -1 indicates no coordinates found
353         String index;
35433        String label = null;
355         // if there are quote marks on this line, split on them; label is surrounded by them
35633        if (curLine.indexOf('"') != -1)
357         {
35830            String[] initial_split = curLine.trim().split("\"");
359             // if there are any quote marks, there should be exactly 2
36030            if (initial_split.length < 2 || initial_split.length > 3)
3610                throw new IllegalArgumentException("Unbalanced (or too many) quote marks in " + curLine);
36230            index = initial_split[0].trim();
36330            label = initial_split[1].trim();
36430            if (initial_split.length == 3)
36510                parts = initial_split[2].trim().split("\\s+", -1);
36630            coord_idx = 0;
367         }
368         else // no quote marks, but are there coordinates?
369         {
3703            parts = curLine.trim().split("\\s+", -1);
3713            index = parts[0];
3723            switch (parts.length)
373             {
374                 case 1: // just the ID; nothing to do, continue
3753                    break;
376                 case 2: // just the ID and a label
3770                    label = parts[1];
3780                    break;
379                 case 3: // ID, no label, coordinates
3800                    coord_idx = 1;
3810                    break;
382                 case 4: // ID, label, (x,y) coordinates
3830                    coord_idx = 2;
384                     break;
385             }
386         }
38733        int v_id = Integer.parseInt(index) - 1; // go from 1-based to 0-based index
38833        if (v_id >= num_vertices || v_id < 0)
3890            throw new IllegalArgumentException("Vertex number " + v_id +
390                     "is not in the range [1," + num_vertices + "]");
39133        v = (Vertex) id.getVertex(v_id);
392         // only attach the label if there's one to attach
39333        if (label != null && label.length() > 0)
39430            attachLabel(v, label);
395         // parse the rest of the line
39633        if (get_locations)
397         {
3985            if (coord_idx == -1 || parts == null || parts.length < coord_idx+2)
3990                throw new IllegalArgumentException("Coordinates requested, but" +
400                         curLine + " does not include coordinates");
4015            double x = Double.parseDouble(parts[coord_idx]);
4025            double y = Double.parseDouble(parts[coord_idx+1]);
403 // if (x < 0 || x > 1 || y < 0 || y > 1)
404 // throw new IllegalArgumentException("Coordinates in line " +
405 // curLine + " are not all in the range [0,1]");
406                 
4075            v_locations.setLocation(v, new Point2D.Double(x,y));
408         }
40933    }
410  
411     
412     
413     private String readArcsOrEdges(String curLine, BufferedReader br, Graph g,
414             NumberEdgeValue nev)
415         throws IOException
416     {
41714        String nextLine = curLine;
418         
41914        Indexer id = Indexer.getIndexer(g);
420         
421         // in case we're not there yet (i.e., format tag isn't arcs or edges)
42214        if (! c_pred.evaluate(curLine))
423 // nextLine = skip(br, e_pred);
4245            nextLine = skip(br, c_pred);
425  
426         // in "*Arcs" and this graph is not strictly undirected
427 // boolean reading_arcs = a_pred.evaluate(nextLine) &&
428 // !PredicateUtils.enforcesUndirected(g);
429 // // in "*Edges" and this graph is not strictly directed
430 // boolean reading_edges = e_pred.evaluate(nextLine) &&
431 // !PredicateUtils.enforcesDirected(g);
432  
43314        boolean reading_arcs = false;
43414        boolean reading_edges = false;
43514        if (a_pred.evaluate(nextLine))
436         {
4374            if (PredicateUtils.enforcesUndirected(g))
4380                throw new IllegalArgumentException("Supplied undirected-only graph cannot be populated with directed edges");
439             else
4404                reading_arcs = true;
441         }
44214        if (e_pred.evaluate(nextLine))
443         {
4445            if (PredicateUtils.enforcesDirected(g))
4450                throw new IllegalArgumentException("Supplied directed-only graph cannot be populated with undirected edges");
446             else
4475                reading_edges = true;
448         }
449         
45014        if (!(reading_arcs || reading_edges))
4515            return nextLine;
452         
4539        boolean is_list = l_pred.evaluate(nextLine);
454  
4559        boolean parallel_ok = !PredicateUtils.enforcesNotParallel(g);
456  
45747        while (br.ready())
458         {
45941            nextLine = br.readLine();
46041            if (nextLine == null || t_pred.evaluate(nextLine))
4612                break;
46238            if (curLine == "") // skip blank lines
4630                continue;
464             
46538            StringTokenizer st = new StringTokenizer(nextLine.trim());
466             
46738            int vid1 = Integer.parseInt(st.nextToken()) - 1;
46838            Vertex v1 = (Vertex) id.getVertex(vid1);
469             
47038            if (is_list) // one source, multiple destinations
471             {
472                 do
473                 {
4740                    createAddEdge(st, v1, reading_arcs, g, id, parallel_ok);
4750                } while (st.hasMoreTokens());
476             }
477             else // one source, one destination, at most one weight
478             {
47938                Edge e = createAddEdge(st, v1, reading_arcs, g, id, parallel_ok);
480                 // get the edge weight if we care
48138                if (nev != null)
4826                    nev.setNumber(e, new Float(st.nextToken()));
483             }
484         }
4859        return nextLine;
486     }
487  
488     protected Edge createAddEdge(StringTokenizer st, Vertex v1,
489             boolean directed, Graph g, Indexer id, boolean parallel_ok)
490     {
49138        int vid2 = Integer.parseInt(st.nextToken()) - 1;
49238        Vertex v2 = (Vertex) id.getVertex(vid2);
49338        Edge e = null;
49438        if (directed)
49518            e = new DirectedSparseEdge(v1, v2);
496         else
49720            e = new UndirectedSparseEdge(v1, v2);
498  
499         // add this edge if parallel edges are OK,
500         // or if this isn't one; otherwise ignore it
50138        if (parallel_ok || !p_pred.evaluate(e))
50238            g.addEdge(e);
503  
50438        return e;
505     }
506     
507     /**
508      * Returns the first line read from <code>br</code> for which <code>p</code>
509      * returns <code>true</code>, or <code>null</code> if there is no
510      * such line.
511      * @throws IOException
512      */
513     protected String skip(BufferedReader br, Predicate p) throws IOException
514     {
51512        while (br.ready())
516         {
5178            String curLine = br.readLine();
5188            if (curLine == null)
5191                break;
5207            curLine = curLine.trim();
5217            if (p.evaluate(curLine))
5227                return curLine;
523         }
5245        return null;
525     }
526     
527     /**
528      * Labels <code>v</code> with <code>string</code>, according to the
529      * labeling mechanism specified by <code>unique_labels</code>.
530      * Removes quotation marks from the string if present.
531      */
532     private void attachLabel(Vertex v, String string) throws IOException
533     {
53430        if (string == null || string.length() == 0)
5350            return;
53630        String label = string.trim();
537 // String label = trimQuotes(string).trim();
538 // if (label.length() == 0)
539 // return;
54030        if (unique_labels)
541         {
542             try
543             {
5440                StringLabeller sl = StringLabeller.getLabeller((Graph)v.getGraph(), LABEL);
5450                sl.setLabel(v, label);
546             }
5470            catch (StringLabeller.UniqueLabelException slule)
548             {
5490                throw new FatalException("Non-unique label found: " + slule);
5500            }
551         }
552         else
553         {
55430            v.addUserDatum(LABEL, label, UserData.SHARED);
555         }
55630    }
557  
558     /**
559      * Sets or clears the <code>unique_labels</code> boolean.
560      * @see #PajekNetReader(boolean, boolean)
561      */
562     public void setUniqueLabels(boolean unique_labels)
563     {
5640        this.unique_labels = unique_labels;
5650    }
566  
567     /**
568      * Sets or clears the <code>get_locations</code> boolean.
569      * @see #PajekNetReader(boolean, boolean)
570      */
571     public void setGetLocations(boolean get_locations)
572     {
5731        this.get_locations = get_locations;
5741    }
575     
576     /**
577      * A Predicate which evaluates to <code>true</code> if the
578      * argument starts with the constructor-specified String.
579      *
580      * @author Joshua O'Madadhain
581      */
582     protected static class TagPred implements Predicate
583     {
584         private String tag;
585         
586         public TagPred(String s)
587         {
588             this.tag = s;
589         }
590         
591         public boolean evaluate(Object arg0)
592         {
593             String s = (String)arg0;
594             return (s != null && s.toLowerCase().startsWith(tag));
595         }
596     }
597     
598     /**
599      * A Predicate which evaluates to <code>true</code> if the
600      * argument ends with the string "list".
601      *
602      * @author Joshua O'Madadhain
603      */
604     protected static class ListTagPred implements Predicate
605     {
606         protected static ListTagPred instance;
607         
608         protected ListTagPred() {}
609         
610         public static ListTagPred getInstance()
611         {
612             if (instance == null)
613                 instance = new ListTagPred();
614             return instance;
615         }
616         
617         public boolean evaluate(Object arg0)
618         {
619             String s = (String)arg0;
620             return (s != null && s.toLowerCase().endsWith("list"));
621         }
622     }
623     
624  
625 }

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.