Coverage details for edu.uci.ics.jung.utils.GraphUtils

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3  * California All rights reserved.
4  *
5  * This software is open-source under the BSD license; see either "license.txt"
6  * or http://jung.sourceforge.net/license.txt for a description.
7  */
8 /*
9  * Created on Jun 25, 2003
10  */
11 package edu.uci.ics.jung.utils;
12  
13 import java.util.Collection;
14 import java.util.HashSet;
15 import java.util.Iterator;
16 import java.util.LinkedList;
17 import java.util.Map;
18 import java.util.Set;
19  
20 import org.apache.commons.collections.CollectionUtils;
21  
22 import cern.colt.list.DoubleArrayList;
23 import edu.uci.ics.jung.algorithms.transformation.DirectionTransformer;
24 import edu.uci.ics.jung.graph.ArchetypeEdge;
25 import edu.uci.ics.jung.graph.ArchetypeGraph;
26 import edu.uci.ics.jung.graph.ArchetypeVertex;
27 import edu.uci.ics.jung.graph.DirectedGraph;
28 import edu.uci.ics.jung.graph.Edge;
29 import edu.uci.ics.jung.graph.Graph;
30 import edu.uci.ics.jung.graph.Hyperedge;
31 import edu.uci.ics.jung.graph.Hypergraph;
32 import edu.uci.ics.jung.graph.Hypervertex;
33 import edu.uci.ics.jung.graph.UndirectedGraph;
34 import edu.uci.ics.jung.graph.Vertex;
35 import edu.uci.ics.jung.graph.decorators.Indexer;
36 import edu.uci.ics.jung.graph.decorators.NumberVertexValue;
37 import edu.uci.ics.jung.graph.decorators.StringLabeller;
38 import edu.uci.ics.jung.graph.decorators.StringLabeller.UniqueLabelException;
39 import edu.uci.ics.jung.graph.filters.UnassembledGraph;
40 import edu.uci.ics.jung.graph.filters.impl.DropSoloNodesFilter;
41 import edu.uci.ics.jung.graph.impl.AbstractSparseEdge;
42 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
43 import edu.uci.ics.jung.graph.impl.DirectedSparseVertex;
44 import edu.uci.ics.jung.graph.impl.SparseVertex;
45 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
46 import edu.uci.ics.jung.graph.impl.UndirectedSparseVertex;
47  
48 /**
49  *
50  * A series of helpful utility methods. All methods in GraphUtils can be
51  * accomplished with public members of other code; these are simply
52  * combinations that we found useful.
53  *
54  * @author Danyel Fisher, Scott White, Joshua O'Madadhain
55  */
560public class GraphUtils
57 {
58  
59     /**
60      * Adds an appropriate edge between two vertices. Specifically, this method
61      * confirms that both vertices are from the same graph, and then checks
62      * whether the Graph is directed or not. If
63      * so, it creates a new
64      * {@link edu.uci.ics.jung.graph.impl.DirectedSparseEdge DirectedSparseEdge},
65      * otherwise a new
66      * {@link edu.uci.ics.jung.graph.impl.UndirectedSparseEdge UndirectedSparseEdge}.
67      * This is a convenience method; one might instead just call <code> g.addEdge( new XXSparseEdge(v1, v2))) </code>.
68      * <p>
69      * The input vertices must be of type {@link edu.uci.ics.jung.graph.Vertex},
70      * or the method will throw a <code>ClassCastException</code>.
71      *
72      * @throws ClassCastException
73      * if the input aren't Vertices
74      * @throws IllegalArgumentException
75      * if the vertices don't belong to the same graph
76      *
77      * @return the edge that was added
78      *
79      * @see edu.uci.ics.jung.graph.Graph#addEdge
80      * @see edu.uci.ics.jung.graph.impl.AbstractSparseGraph#addEdge
81      */
82     public static Edge addEdge(Graph g, Vertex v1, Vertex v2)
83     {
84135547        if (v1.getGraph() != g || v2.getGraph() != g)
851            throw new IllegalArgumentException("Vertices not in this graph!");
86135546        if (PredicateUtils.enforcesEdgeConstraint(g, Graph.DIRECTED_EDGE))
87         {
882734            return (AbstractSparseEdge) g.addEdge(
89                 new DirectedSparseEdge(v1, v2));
90         }
91132812        else if (PredicateUtils.enforcesEdgeConstraint(g, Graph.UNDIRECTED_EDGE))
92         {
93132812            return (AbstractSparseEdge) g.addEdge(
94                 new UndirectedSparseEdge(v1, v2));
95         }
96         else
970            throw new IllegalArgumentException("Behavior not specified " +
98                     "for mixed (directed/undirected) graphs");
99     }
100  
101     /**
102      * Adds <code>count</code> vertices into a graph. This is a convenience
103      * method; one might instead just call <code> g.addVertex( new SparseVertex())) </code>
104      * <code>count</code>
105      * times.
106      * <p>
107      * The input graph must be one that can accept a series of
108      * {@link edu.uci.ics.jung.graph.impl.SparseVertex directed vertices}.
109      *
110      * @param g
111      * A graph to add the vertices to
112      * @param count
113      * how many vertices to add
114      *
115      * @see edu.uci.ics.jung.graph.impl.AbstractSparseGraph#addVertex
116      */
117     public static void addVertices(Graph g, int count)
118     {
11930907        for (int i = 0; i < count; i++)
12030609            g.addVertex(new SparseVertex());
121298    }
122  
123     /**
124      * Adds <code>count</code> directed vertices into a graph. This is a
125      * convenience method; one might instead just call <code> g.addVertex( new DirectedSparseVertex())) </code>
126      * <code>count</code>
127      * times.
128      * <p>
129      * The input graph must be one that can accept a series of
130      * {@link edu.uci.ics.jung.graph.impl.DirectedSparseVertex directed vertices}.
131      *
132      * @param g
133      * A graph to add the vertices to
134      * @param count
135      * how many vertices to add
136      *
137      * @see edu.uci.ics.jung.graph.impl.AbstractSparseGraph#addVertex
138      * @deprecated As of version 1.2, replaced by {@link #addVertices}.
139      */
140     public static void addDirectedVertices(Graph g, int count)
141     {
1420        for (int i = 0; i < count; i++)
143         {
1440            g.addVertex(new DirectedSparseVertex());
145         }
1460    }
147  
148     /**
149      * Adds <code>count</code> undirected vertices into a graph. This is a
150      * convenience method; one might instead just call <code> g.addVertex( new UndirectedSparseVertex())) </code>
151      * <code>count</code>
152      * times.
153      * <p>
154      * The input graph must be one that can accept a series of
155      * {@link edu.uci.ics.jung.graph.impl.UndirectedSparseVertex undirected vertices}.
156      *
157      * @param g
158      * A graph to add the vertices to
159      * @param count
160      * how many vertices to add
161      *
162      * @see edu.uci.ics.jung.graph.impl.AbstractSparseGraph#addVertex
163      * @deprecated As of version 1.2, replaced by {@link #addVertices}.
164      */
165     public static void addUndirectedVertices(Graph g, int count)
166     {
1670        for (int i = 0; i < count; i++)
168         {
1690            g.addVertex(new UndirectedSparseVertex());
170         }
1710    }
172  
173     /**
174      * Translates every vertex from the input <code>set</code> into the graph
175      * given. For each vertex, then, it gets the equivalent vertex in <code>g</code>,
176      * and returns the collated set.
177      *
178      * @param s
179      * The set of input vertices, not from g
180      * @param g
181      * The graph which has the corresponding vertices
182      *
183      * @return a resulting set
184      *
185      * @see edu.uci.ics.jung.graph.ArchetypeVertex#getEqualVertex
186      * @deprecated As of version 1.4, replaced by {@link GraphUtils#getEqualVertices(Set, ArchetypeGraph)}
187      */
188     public static Set translateAll(Set s, Graph g)
189     {
1900        return getEqualVertices(s, g);
191     }
192  
193     /**
194      * Returns the set of vertices in <code>g</code> which are equal
195      * to the vertices in <code>g</code>.
196      * @since 1.4
197      */
198     public static Set getEqualVertices(Set s, ArchetypeGraph g)
199     {
2006        Set rv = new HashSet();
2016        for (Iterator iter = s.iterator(); iter.hasNext();)
202         {
20358            ArchetypeVertex v = (ArchetypeVertex) iter.next();
20458            ArchetypeVertex v_g = v.getEqualVertex(g);
20558            if (v_g != null)
20654                rv.add(v_g);
207         }
2086        return rv;
209     }
210     
211     /**
212      * Translates every edge from the input <code>set</code> into the graph
213      * given. For each edge, then, it gets the equivalent edge in <code>g</code>,
214      * and returns the collated set.
215      *
216      * @param s
217      * The set of input edges, not from g
218      * @param g
219      * The graph which has the corresponding edges
220      *
221      * @return a resulting set
222      *
223      * @see edu.uci.ics.jung.graph.ArchetypeEdge#getEqualEdge
224      * @deprecated As of version 1.4, replaced by {@link GraphUtils#getEqualEdges(Set, ArchetypeGraph)}
225      */
226     public static Set translateAllEdges(Set s, Graph g)
227     {
2280        return getEqualEdges(s, g);
229     }
230  
231     /**
232      * Returns the set of edges in <code>g</code> which are equal
233      * to the edges in <code>g</code>.
234      * @since 1.4
235      */
236     public static Set getEqualEdges(Set s, ArchetypeGraph g)
237     {
2386        Set rv = new HashSet();
2396        for (Iterator iter = s.iterator(); iter.hasNext();)
240         {
241266            ArchetypeEdge e = (ArchetypeEdge) iter.next();
242266            ArchetypeEdge e_g = e.getEqualEdge(g);
243266            if (e_g != null)
244262                rv.add(e_g);
245         }
2466        return rv;
247     }
248  
249     /**
250      * Given a set of vertices, creates a new <tt>Graph</tt> that contains
251      * all of those vertices, and all the edges that connect them. Uses the
252      * <tt>{@link edu.uci.ics.jung.graph.filters.UnassembledGraph UnassembledGraph}</tt>
253      * mechanism to create the graph.
254      *
255      * @param s
256      * A set of <tt>Vertex</tt> s that want to be a part of a new
257      * Graph
258      * @return A graph, created with <tt>{@link edu.uci.ics.jung.graph.Graph#newInstance Graph.newInstance}</tt>,
259      * containing vertices equivalent to (and that are copies of!) all
260      * the vertices in the input set. Note that if the input is an
261      * empty set, <tt>null</tt> is returned.
262      */
263     public static Graph vertexSetToGraph(Set s)
264     {
2650        if (s.isEmpty())
2660            return null;
2670        Vertex v = (Vertex) s.iterator().next();
2680        Graph g = (Graph) v.getGraph();
2690        return new UnassembledGraph("vertexSetToGraph", s, g.getEdges(), g)
270             .assemble();
271     }
272  
273     /**
274      * Given a set of edges, creates a new <tt>Graph</tt> that contains all
275      * of those edges, and at least all the vertices that are attached to them.
276      * Uses <tt>{@link edu.uci.ics.jung.graph.filters.UnassembledGraph UnassembledGraph}</tt>
277      * mechanism to create the graph. The parameter decides what to do with
278      * disconnected vertices: <tt>true</tt> says that they should be
279      * retained, <tt>false</tt> says that they should be discarded (with a
280      * {@link edu.uci.ics.jung.graph.filters.impl.DropSoloNodesFilter DropSoloNodesFilter}).
281      *
282      * @param edges
283      * A set of <tt>Edge</tt> s that want to be a part of a new
284      * <tt>Graph</tt>
285      * @param retain
286      * Is true if all isolated vertices should be retained; is false if they
287      * should be discarded.
288      * @return A graph, created with <tt>{@link edu.uci.ics.jung.graph.Graph#newInstance Graph.newInstance}</tt>,
289      * containing edges equivalent to (and that are copies of!) all the
290      * edges in the input set. Note that if the input is an empty set,
291      * <tt>null</tt> is returned.
292      */
293     public static Graph edgeSetToGraph(Set edges, boolean retain)
294     {
2950        if (edges.isEmpty())
2960            return null;
2970        Edge e = (Edge) edges.iterator().next();
2980        Graph g = (Graph) e.getGraph();
2990        Graph retval =
300             new UnassembledGraph("edgeSetToGraph", g.getVertices(), edges, g)
301                 .assemble();
3020        if (retain)
3030            return retval;
304         else
305         {
3060            return DropSoloNodesFilter.getInstance().filter(retval).assemble();
307         }
308     }
309  
310     /**
311      * Returns a graph which consists of the union of the two input graphs.
312      * Assumes that both graphs are of a type that can accept the vertices
313      * and edges found in both graphs.
314      * The resultant graph contains all constraints that are common to both graphs.
315      */
316     public static ArchetypeGraph union(ArchetypeGraph g1, ArchetypeGraph g2)
317     {
3180        ArchetypeGraph g = g1.newInstance();
319 // g.getEdgeConstraints().clear();
3200        g.getEdgeConstraints().addAll(CollectionUtils.intersection(
321                 g1.getEdgeConstraints(), g2.getEdgeConstraints()));
322         
3230        Collection vertices = CollectionUtils.union(g1.getVertices(), g2.getVertices());
3240        Collection edges = CollectionUtils.union(g1.getEdges(), g2.getEdges());
325         
3260        for (Iterator v_iter = vertices.iterator(); v_iter.hasNext(); )
327         {
3280            ArchetypeVertex v = (ArchetypeVertex)v_iter.next();
3290            v.copy(g);
330         }
331         
3320        for (Iterator e_iter = edges.iterator(); e_iter.hasNext(); )
333         {
3340            ArchetypeEdge e = (ArchetypeEdge)e_iter.next();
3350            e.copy(g);
336         }
3370        return g;
338     }
339     
340     /**
341      * Transforms an (possibly undirected) graph into a directed graph. All user data on
342      * the graph,edges & vertices are copied to their corresponding
343      * counterparts. Returns a new graph with a directed edge from a to b iff a
344      * was a predecessor of b in the original. For an undirected edge, this will create
345      * two new edges.
346      *
347      * @param uGraph
348      * the undirected graph to transform
349      * @return the resultant directed graph
350      * @deprecated As of version 1.4, replaced by
351      * {@link edu.uci.ics.jung.algorithms.transformation.DirectionTransformer#toDirected(Graph)}
352      */
353     public static DirectedGraph transform(Graph uGraph)
354     {
3550        return DirectionTransformer.toDirected(uGraph);
356     }
357  
358     /**
359      * Transforms a directed graph into a undirected graph. All user data on
360      * the graph,edges & vertices are copied to their corresponding
361      * counterparts.
362      *
363      * @param dGraph
364      * the directed graph to transform
365      * @return the resultant undirected graph
366      * @deprecated As of version 1.4, replaced by
367      * {@link edu.uci.ics.jung.algorithms.transformation.DirectionTransformer#toUndirected(Graph)}
368      */
369     public static UndirectedGraph transform(DirectedGraph dGraph)
370     {
3710        return DirectionTransformer.toUndirected(dGraph);
372     }
373  
374     /**
375      * Copies the labels of vertices from one StringLabeller to another. Only
376      * the labels of vertices that are equivalent are copied.
377      *
378      * @param source
379      * the source StringLabeller
380      * @param target
381      * the target StringLabeller
382      */
383     public static void copyLabels(StringLabeller source, StringLabeller target)
384         throws UniqueLabelException
385     {
3861        Graph g1 = source.getGraph();
3871        Graph g2 = target.getGraph();
3881        Set s1 = g1.getVertices();
3891        Set s2 = g2.getVertices();
390  
3911        for (Iterator iter = s1.iterator(); iter.hasNext();)
392         {
3935            Vertex v = (Vertex) iter.next();
3945            if (s2.contains(v))
395             {
3964                target.setLabel(
397                     (Vertex) v.getEqualVertex(g2),
398                     source.getLabel(v));
399             }
400         }
4011    }
402  
403     /**
404      * Returns true if <code>g1</code> and <code>g2</code> have equivalent
405      * vertex and edge sets (that is, if each vertex and edge in <code>g1</code>
406      * has an equivalent in <code>g2</code>, and vice versa), and false
407      * otherwise.
408      */
409     public static boolean areEquivalent(ArchetypeGraph g1, ArchetypeGraph g2)
410     {
4114        return (
412             (g1 == g2)
413                 || (g1.getVertices().equals(g2.getVertices())
414                     && g1.getEdges().equals(g2.getEdges())));
415     }
416  
417     /**
418      * For every vertex in s, prints sl.get(s). S must be made up of only
419      * vertices.
420      *
421      * @param s
422      * @param sl
423      */
424     public static String printVertices(Collection s, StringLabeller sl)
425     {
4260        StringBuffer sb = new StringBuffer();
4270        boolean first = true;
4280        sb.append("[");
4290        for (Iterator iter = s.iterator(); iter.hasNext();)
430         {
4310            Vertex v = (Vertex) iter.next();
4320            if (!first)
4330                sb.append(", ");
434             else
4350                first = false;
4360            sb.append( sl.getLabel(v) );
437  
438         }
4390        sb.append("]");
4400        return sb.toString();
441     }
442     
443     
444     /**
445      * Copies, for each vertex <code>v</code> in <code>g</code>,
446      * <code>source</code>'s value to <code>dest</code>.
447      * @param g the graph from which the vertices are taken
448      * @param source the <code>NumberVertexValue</code> from which values are to be copied
449      * @param dest the <code>NumberVertexValue</code> into which values are to be copied
450      */
451     public static void copyValues(ArchetypeGraph g, NumberVertexValue source, NumberVertexValue dest)
452     {
4530        for (Iterator iter = g.getVertices().iterator(); iter.hasNext(); )
454         {
4550            ArchetypeVertex v = (ArchetypeVertex)iter.next();
4560            dest.setNumber(v, source.getNumber(v));
457         }
4580    }
459     
460     /**
461      * Returns the <code>VertexGenerator</code>, if any, stored in <code>g</code>'s
462      * user data at the standardized location specified by the VG interface: <code>VertexGenerator.TAG</code>.
463      */
464     public static VertexGenerator getVertexGenerator(ArchetypeGraph g)
465     {
4660        return (VertexGenerator)g.getUserDatum(VertexGenerator.TAG);
467     }
468     
469     /**
470      * Converts <code>vertex_values</code> (a Map of vertex to Number values)
471      * to a DoubleArrayList, using <code>indexer</code> to determine the location
472      * of each vertex's value in the DAL.
473      * @param vertex_values
474      * @param indexer
475      * @return
476      */
477     public static DoubleArrayList vertexMapToDAL(Map vertex_values, Indexer indexer)
478     {
4790        DoubleArrayList dal = new DoubleArrayList(vertex_values.size());
480         
4810        for (Iterator iter = vertex_values.keySet().iterator(); iter.hasNext(); )
482         {
4830            ArchetypeVertex av = (ArchetypeVertex)iter.next();
4840            double value = ((Number)vertex_values.get(av)).doubleValue();
4850            dal.set(indexer.getIndex(av), value);
486         }
487         
4880        return dal;
489     }
490  
491     /**
492      * Adds all vertices in the specified set to <code>g</code>. Syntactic
493      * sugar for a loop that calls <code>g.addVertex</code> on all elements
494      * of the set.
495      * If any element of <code>vertices</code> may not be legally added
496      * to this graph, throws an exception: <code>ClassCastException</code> if
497      * the type is inappropriate, and <code>IllegalArgumentException</code>
498      * otherwise. If an exception is thrown, any vertices that may
499      * already have been added are not guaranteed to be retained.
500      */
501     public static void addVertices(Graph g, Set vertices)
502     {
5030        for (Iterator iter = vertices.iterator(); iter.hasNext(); )
5040            g.addVertex((Vertex)iter.next());
5050    }
506     
507     /**
508      * Adds all vertices in the specified set to <code>g</code>. Syntactic
509      * sugar for a loop that calls <code>g.addVertex</code> on all elements
510      * of the set.
511      * If any element of <code>vertices</code> may not be legally added
512      * to this graph, throws an exception: <code>ClassCastException</code> if
513      * the type is inappropriate, and <code>IllegalArgumentException</code>
514      * otherwise. If an exception is thrown, any vertices that may
515      * already have been added are not guaranteed to be retained.
516      */
517     public static void addVertices(Hypergraph g, Set vertices)
518     {
5190        for (Iterator iter = vertices.iterator(); iter.hasNext(); )
5200            g.addVertex((Hypervertex)iter.next());
5210    }
522     
523     /**
524      * Adds all edges in the specified set to <code>g</code>. Syntactic
525      * sugar for a loop that calls <code>g.addEdge</code> on all elements
526      * of the set.
527      * If any element of <code>edges</code> may not be legally added
528      * to this graph, throws an exception: <code>ClassCastException</code> if
529      * the type is inappropriate, and <code>IllegalArgumentException</code>
530      * otherwise. If an exception is thrown, any edges that may
531      * already have been added are not guaranteed to be retained.
532      */
533     public static void addEdges(Graph g, Set edges)
534     {
5350        for (Iterator iter = edges.iterator(); iter.hasNext(); )
5360            g.addEdge((Edge)iter.next());
5370    }
538     
539     /**
540      * Adds all edges in the specified set to <code>g</code>. Syntactic
541      * sugar for a loop that calls <code>g.addEdge</code> on all elements
542      * of the set.
543      * If any element of <code>edges</code> may not be legally added
544      * to this graph, throws an exception: <code>ClassCastException</code> if
545      * the type is inappropriate, and <code>IllegalArgumentException</code>
546      * otherwise. If an exception is thrown, any edges that may
547      * already have been added are not guaranteed to be retained.
548      */
549     public static void addEdges(Hypergraph g, Set edges)
550     {
5510        for (Iterator iter = edges.iterator(); iter.hasNext(); )
5520            g.addEdge((Hyperedge)iter.next());
5530    }
554     
555     /**
556      * Removes all vertices in the specified set from <code>g</code>. Syntactic
557      * sugar for a loop that calls <code>g.removeVertex</code> on all elements
558      * of the set.
559      * If any element of <code>vertices</code> is not part of this graph,
560      * then throws <code>IllegalArgumentException</code>. If this
561      * exception is thrown, any vertices that may have been removed already
562      * are not guaranteed to be restored to the graph.
563      */
564     public static void removeVertices(Graph g, Set vertices)
565     {
56621        for (Iterator iter = new LinkedList(vertices).iterator(); iter.hasNext(); )
56764            g.removeVertex((Vertex)iter.next());
56821    }
569  
570     /**
571      * Removes all vertices in the specified set from <code>g</code>. Syntactic
572      * sugar for a loop that calls <code>g.removeVertex</code> on all elements
573      * of the set.
574      * If any element of <code>vertices</code> is not part of this graph,
575      * then throws <code>IllegalArgumentException</code>. If this
576      * exception is thrown, any vertices that may have been removed already
577      * are not guaranteed to be restored to the graph.
578      */
579     public static void removeVertices(Hypergraph g, Set vertices)
580     {
5810        for (Iterator iter = new LinkedList(vertices).iterator(); iter.hasNext(); )
5820            g.removeVertex((Hypervertex)iter.next());
5830    }
584  
585     /**
586      * Removes all vertices in the specified set from <code>g</code>. Syntactic
587      * sugar for a loop that calls <code>g.removeVertex</code> on all elements
588      * of the set.
589      * If any element of <code>edges</code> is not part of this graph,
590      * then throws <code>IllegalArgumentException</code>. If this
591      * exception is thrown, any edges that may have been removed already
592      * are not guaranteed to be restored to the graph.
593      */
594     public static void removeEdges(Graph g, Set edges)
595     {
596118        for (Iterator iter = new LinkedList(edges).iterator(); iter.hasNext(); )
597228            g.removeEdge((Edge)iter.next());
598118    }
599  
600     /**
601      * Removes all vertices in the specified set from <code>g</code>. Syntactic
602      * sugar for a loop that calls <code>g.removeVertex</code> on all elements
603      * of the set.
604      * If any element of <code>edges</code> is not part of this graph,
605      * then throws <code>IllegalArgumentException</code>. If this
606      * exception is thrown, any edges that may have been removed already
607      * are not guaranteed to be restored to the graph.
608      */
609     public static void removeEdges(Hypergraph g, Set edges)
610     {
6110        for (Iterator iter = new LinkedList(edges).iterator(); iter.hasNext(); )
6120            g.removeEdge((Hyperedge)iter.next());
6130    }
614  
615 }

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.