Coverage details for edu.uci.ics.jung.algorithms.transformation.DirectionTransformer

LineHitsSource
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 /*
11  * Created on Apr 21, 2004
12  */
13 package edu.uci.ics.jung.algorithms.transformation;
14  
15 import java.util.HashMap;
16 import java.util.Iterator;
17 import java.util.Map;
18  
19 import edu.uci.ics.jung.graph.DirectedGraph;
20 import edu.uci.ics.jung.graph.Edge;
21 import edu.uci.ics.jung.graph.Graph;
22 import edu.uci.ics.jung.graph.UndirectedGraph;
23 import edu.uci.ics.jung.graph.Vertex;
24 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
25 import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;
26 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
27 import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
28 import edu.uci.ics.jung.utils.TypedVertexGenerator;
29 import edu.uci.ics.jung.utils.VertexGenerator;
30  
31 /**
32  * <p>Transforms graphs of one directionality into the other.</p>
33  *
34  * <P>The <code>copy</code> parameter of the transformation methods, if
35  * <code>true</code>, specifies
36  * that the vertices of the input graph will be copied (using the
37  * <code>ArchetypeVertex.copy()</code> method) into the new graph;
38  * if <code>false</code>,
39  * new vertices will be created (using the most restrictive vertex type
40  * appropriate to the transformed graph type). In
41  * either case, the user data repositories of the original vertices will be
42  * imported into the corresponding vertices of the transformed graph.</p>
43  *
44  * <p>The advantage
45  * of using the <code>copy</code> mode is that the vertex equality
46  * relationship reflected by <code>getEqualVertex()</code> will be
47  * established between the vertices of the two graphs; however, the
48  * vertices of the original graph must be able to accommodate edges of
49  * the types appropriate to both the original and the transformed graph.
50  * (As of version 1.4, this means that the vertices of the input
51  * graph must be instances of either <code>SparseVertex</code> or
52  * <code>SimpleSparseVertex</code>.)</p>
53  *
54  * <p>The advantage of not using the <code>copy</code> mode is that
55  * the vertices of the original graph do not need to be able to accommodate
56  * both directed and undirected edges, which relieves the user from having
57  * to worry about this matter.</p>
58  *
59  * <p>Directed edges cannot be copied to undirected edges or vice versa,
60  * so the edges of the transformed graph are always new edges; as above,
61  * the user data repositories of the original edges are imported into
62  * the edges of the transformed graph.</p>
63  *
64  * <p><b>Known issues:</b>
65  * <ul>
66  * <li/><code>toUndirected()</code>: if the edges
67  * <code>(a,b)</code> and <code>(b,a)</code> both exist in the original
68  * graph, the user data from one will be imported into the new undirected
69  * edge; the user data from the other will not be imported. It is not
70  * specified which edge's user data will be imported.
71  * <li/>The resultant graphs will not have parallel edges, regardless of
72  * whether the original graphs had parallel edges.
73  * </ul>
74  *
75  * @author Danyel Fisher
76  * @author Joshua O'Madadhain
77  */
780public class DirectionTransformer
79 {
80  
81     /**
82      * Transforms <code>graph</code> (which may be of any directionality)
83      * into an undirected graph without
84      * parallel edges. (This is likely to be very useful for visualization
85      * tasks). Creates exactly one undirected edge (a, b) iff a isNeighborOf b.
86      * Equivalent to <code>toUndirected(dGraph, true)</code>.
87      *
88      * @param graph the graph to be transformed
89      * @return the transformed <code>UndirectedGraph</code>
90      * @see toUndirected(Graph, boolean)
91      */
92     public static UndirectedGraph toUndirected(Graph graph)
93     {
941        return toUndirected(graph, true);
95     }
96  
97     
98     /**
99      * Transforms <code>graph</code> (which may be of any directionality)
100      * into an undirected graph. (This is likely to be very useful for
101      * visualization tasks). Creates exactly one undirected edge (a, b) iff a
102      * isNeighborOf b. If <code>copy</code> is <code>true</code>, specifies
103      * that the vertices of the input graph will be copied (using the
104      * <code>ArchetypeVertex.copy()</code> method) into the new graph; if
105      * <code>false</code>, new vertices will be created (using the most
106      * restrictive vertex type appropriate to the transformed graph type).
107      *
108      * @param graph the graph to be transformed
109      * @param copy specifies whether the vertices are to be copied or duplicated
110      * @return the transformed <code>UndirectedGraph</code>
111      */
112     public static UndirectedGraph toUndirected(Graph graph, boolean copy)
113     {
1141        UndirectedGraph uGraph = new UndirectedSparseGraph();
1151        uGraph.importUserData(graph);
116  
1171        Map vertex_map = convertVertices(graph, uGraph, copy);
118  
1191        for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) {
1209            Edge e = (Edge) eIt.next();
1219            Vertex dv1 = (Vertex) e.getEndpoints().getFirst();
1229            Vertex dv2 = (Vertex) e.getEndpoints().getSecond();
1239            Vertex uv1 = (Vertex)vertex_map.get(dv1);
1249            Vertex uv2 = (Vertex)vertex_map.get(dv2);
1259            if (uv1.isNeighborOf(uv2)) continue;
1267            Edge uEdge = uGraph.addEdge(new UndirectedSparseEdge(uv1, uv2));
1277            uEdge.importUserData(e);
128         }
1291        return uGraph;
130  
131     }
132     
133     /**
134      * Puts a version of each vertex from <code>old</code> into
135      * <code>transformed</code>. See the class-level documentation for
136      * the behavior of the <code>copy</code> parameter.
137      */
138     protected static Map convertVertices(Graph old, Graph transformed, boolean copy)
139     {
1404        VertexGenerator vg = new TypedVertexGenerator(transformed);
1414        Map vertex_map = new HashMap();
142         
1434        for (Iterator iter = old.getVertices().iterator(); iter.hasNext(); )
144         {
14530            Vertex v = (Vertex)iter.next();
146             Vertex v_t;
14730            if (copy)
14830                v_t = (Vertex)v.copy(transformed);
149             else
150             {
1510                v_t = transformed.addVertex(vg.create());
1520                v_t.importUserData(v);
153             }
15430            vertex_map.put(v, v_t);
155         }
1564        return vertex_map;
157     }
158     
159     /**
160      * Transforms <code>graph</code> (which may be of any directionality)
161      * into a directed graph without
162      * parallel edges. Creates exactly one directed edge (a, b) iff a
163      * isPredecessorOf b (so an UndirectedEdge will actually produce two edges).
164      * Equivalent to <code>toDirected(graph, true)</code>.
165      *
166      * @param graph the graph to be transformed
167      * @return the transformed <code>DirectedGraph</code>
168      * @see toDirected(Graph, boolean)
169      */
170     public static DirectedGraph toDirected(Graph graph)
171     {
1723        return toDirected(graph, true);
173     }
174  
175     /**
176      * Transforms <code>graph</code> (which may be of any directionality)
177      * into a directed graph. Creates exactly one directed edge (a, b) iff a
178      * isPredecessorOf b (so an UndirectedEdge will actually produce two edges).
179      * If <code>copy</code> is <code>true</code>, specifies
180      * that the vertices of the input graph will be copied (using the
181      * <code>ArchetypeVertex.copy()</code> method) into the new graph; if
182      * <code>false</code>, new vertices will be created (using the most
183      * restrictive vertex type appropriate to the transformed graph type).
184      *
185      * @param graph the graph to be transformed
186      * @param copy specifies whether the vertices are to be copied or duplicated
187      * @return the transformed <code>DirectedGraph</code>
188      */
189     public static DirectedGraph toDirected(Graph graph, boolean copy)
190     {
1913        DirectedGraph dGraph = new DirectedSparseGraph();
1923        dGraph.importUserData(graph);
193         
1943        Map vertex_map = convertVertices(graph, dGraph, copy);
195  
1963        for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();)
197         {
19826            Edge e = (Edge) eIt.next();
19926            Vertex uv1 = (Vertex) e.getEndpoints().getFirst();
20026            Vertex uv2 = (Vertex) e.getEndpoints().getSecond();
20126            Vertex dv1 = (Vertex)vertex_map.get(uv1);
20226            Vertex dv2 = (Vertex)vertex_map.get(uv2);
20326            if (uv1.isPredecessorOf(uv2) && !dv1.isPredecessorOf(dv2)) {
20426                Edge dEdge = dGraph.addEdge(new DirectedSparseEdge(dv1, dv2));
20526                dEdge.importUserData(e);
206             }
20726            if (uv2.isPredecessorOf(uv1) && !dv2.isPredecessorOf(dv1)) {
20825                Edge dEdge = dGraph.addEdge(new DirectedSparseEdge(dv2, dv1));
20925                dEdge.importUserData(e);
210             }
211         }
212  
2133        return dGraph;
214     }
215 }

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.