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 | /* | |
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 | */ | |
78 | 0 | public 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 | { | |
94 | 1 | 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 | { | |
114 | 1 | UndirectedGraph uGraph = new UndirectedSparseGraph(); |
115 | 1 | uGraph.importUserData(graph); |
116 | ||
117 | 1 | Map vertex_map = convertVertices(graph, uGraph, copy); |
118 | ||
119 | 1 | for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) { |
120 | 9 | Edge e = (Edge) eIt.next(); |
121 | 9 | Vertex dv1 = (Vertex) e.getEndpoints().getFirst(); |
122 | 9 | Vertex dv2 = (Vertex) e.getEndpoints().getSecond(); |
123 | 9 | Vertex uv1 = (Vertex)vertex_map.get(dv1); |
124 | 9 | Vertex uv2 = (Vertex)vertex_map.get(dv2); |
125 | 9 | if (uv1.isNeighborOf(uv2)) continue; |
126 | 7 | Edge uEdge = uGraph.addEdge(new UndirectedSparseEdge(uv1, uv2)); |
127 | 7 | uEdge.importUserData(e); |
128 | } | |
129 | 1 | 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 | { | |
140 | 4 | VertexGenerator vg = new TypedVertexGenerator(transformed); |
141 | 4 | Map vertex_map = new HashMap(); |
142 | ||
143 | 4 | for (Iterator iter = old.getVertices().iterator(); iter.hasNext(); ) |
144 | { | |
145 | 30 | Vertex v = (Vertex)iter.next(); |
146 | Vertex v_t; | |
147 | 30 | if (copy) |
148 | 30 | v_t = (Vertex)v.copy(transformed); |
149 | else | |
150 | { | |
151 | 0 | v_t = transformed.addVertex(vg.create()); |
152 | 0 | v_t.importUserData(v); |
153 | } | |
154 | 30 | vertex_map.put(v, v_t); |
155 | } | |
156 | 4 | 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 | { | |
172 | 3 | 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 | { | |
191 | 3 | DirectedGraph dGraph = new DirectedSparseGraph(); |
192 | 3 | dGraph.importUserData(graph); |
193 | ||
194 | 3 | Map vertex_map = convertVertices(graph, dGraph, copy); |
195 | ||
196 | 3 | for (Iterator eIt = graph.getEdges().iterator(); eIt.hasNext();) |
197 | { | |
198 | 26 | Edge e = (Edge) eIt.next(); |
199 | 26 | Vertex uv1 = (Vertex) e.getEndpoints().getFirst(); |
200 | 26 | Vertex uv2 = (Vertex) e.getEndpoints().getSecond(); |
201 | 26 | Vertex dv1 = (Vertex)vertex_map.get(uv1); |
202 | 26 | Vertex dv2 = (Vertex)vertex_map.get(uv2); |
203 | 26 | if (uv1.isPredecessorOf(uv2) && !dv1.isPredecessorOf(dv2)) { |
204 | 26 | Edge dEdge = dGraph.addEdge(new DirectedSparseEdge(dv1, dv2)); |
205 | 26 | dEdge.importUserData(e); |
206 | } | |
207 | 26 | if (uv2.isPredecessorOf(uv1) && !dv2.isPredecessorOf(dv1)) { |
208 | 25 | Edge dEdge = dGraph.addEdge(new DirectedSparseEdge(dv2, dv1)); |
209 | 25 | dEdge.importUserData(e); |
210 | } | |
211 | } | |
212 | ||
213 | 3 | return dGraph; |
214 | } | |
215 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |