KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > graph > Transpose


1 /*
2  * Generic graph library
3  * Copyright (C) 2000,2003,2004 University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19
20 // $Revision: 1.14 $
21
22 package edu.umd.cs.findbugs.graph;
23
24 import java.util.IdentityHashMap JavaDoc;
25 import java.util.Iterator JavaDoc;
26
27 /**
28  * Algorithm to transpose a graph.
29  */
30 public class Transpose
31         <
32         GraphType extends Graph<EdgeType, VertexType>,
33         EdgeType extends GraphEdge<EdgeType, VertexType>,
34         VertexType extends GraphVertex<VertexType>
35         > {
36
37     private IdentityHashMap JavaDoc<VertexType, VertexType> m_origToTransposeMap;
38     private IdentityHashMap JavaDoc<VertexType, VertexType> m_transposeToOrigMap;
39
40     /**
41      * Constructor.
42      */
43     public Transpose() {
44         m_origToTransposeMap = new IdentityHashMap JavaDoc<VertexType, VertexType>();
45         m_transposeToOrigMap = new IdentityHashMap JavaDoc<VertexType, VertexType>();
46     }
47
48     /**
49      * Transpose a graph. Note that the original graph is not modified;
50      * the new graph and its vertices and edges are new objects.
51      *
52      * @param orig the graph to transpose
53      * @param toolkit a GraphToolkit to be used to create the transposed Graph
54      * @return the transposed Graph
55      */
56     public GraphType transpose(GraphType orig, GraphToolkit<GraphType, EdgeType, VertexType> toolkit) {
57
58         GraphType trans = toolkit.createGraph();
59
60         // For each vertex in original graph, create an equivalent
61 // vertex in the transposed graph,
62 // ensuring that vertex labels in the transposed graph
63 // match vertex labels in the original graph
64 for (Iterator JavaDoc<VertexType> i = orig.vertexIterator(); i.hasNext();) {
65             VertexType v = i.next();
66
67             // Make a duplicate of original vertex
68 // (Ensuring that transposed graph has same labeling as original)
69 VertexType dupVertex = toolkit.duplicateVertex(v);
70             dupVertex.setLabel(v.getLabel());
71             trans.addVertex(v);
72
73             // Keep track of correspondence between equivalent vertices
74 m_origToTransposeMap.put(v, dupVertex);
75             m_transposeToOrigMap.put(dupVertex, v);
76         }
77         trans.setNumVertexLabels(orig.getNumVertexLabels());
78
79         // For each edge in the original graph, create a reversed edge
80 // in the transposed graph
81 for (Iterator JavaDoc<EdgeType> i = orig.edgeIterator(); i.hasNext();) {
82             EdgeType e = i.next();
83
84             VertexType transSource = m_origToTransposeMap.get(e.getTarget());
85             VertexType transTarget = m_origToTransposeMap.get(e.getSource());
86
87             EdgeType dupEdge = trans.createEdge(transSource, transTarget);
88             dupEdge.setLabel(e.getLabel());
89
90             // Copy auxiliary information for edge
91 toolkit.copyEdge(e, dupEdge);
92         }
93         trans.setNumEdgeLabels(orig.getNumEdgeLabels());
94
95         return trans;
96
97     }
98
99     /**
100      * Get the vertex in the transposed graph which corresponds to the
101      * given vertex in the original graph.
102      *
103      * @param v the vertex in the original graph
104      * @return the equivalent vertex in the transposed graph
105      */
106     public VertexType getTransposedGraphVertex(VertexType v) {
107         return m_origToTransposeMap.get(v);
108     }
109
110     /**
111      * Get the vertex in the original graph which corresponds to the
112      * given vertex in the transposed graph.
113      *
114      * @param v the vertex in the transposed graph
115      * @return the equivalent vertex in the original graph
116      */
117     public VertexType getOriginalGraphVertex(VertexType v) {
118         return m_transposeToOrigMap.get(v);
119     }
120
121 }
122
123 // vim:ts=4
124
Popular Tags