| 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. |