KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > isomorphism > GraphOrdering


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -----------------
26  * GraphOrdering.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: GraphOrdering.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  */
38 package org.jgrapht.experimental.isomorphism;
39
40 import java.util.*;
41
42 import org.jgrapht.*;
43 import org.jgrapht.util.*;
44
45
46 /**
47  * Holds graph information as int labels only. vertexes: 1,2,3,4 edges:1->2 ,
48  * 3->4 ,1->1. Implementation as imutable graph by int[] for vetexes and
49  * LabelsEdge[] for edges. The current algorithms do not support graph with
50  * multiple edges (Multigraph / Pseudograph). For the maintaner: The reason for
51  * it is the use of edges sets of LabelsEdge in which the equals checks for
52  * source and target vertexes. Thus there cannot be two LabelsEdge with the same
53  * source and target in the same Set.
54  *
55  * @author Assaf
56  * @since May 20, 2005
57  */
58 public class GraphOrdering<V, E>
59 {
60
61     //~ Instance fields -------------------------------------------------------
62
63     /**
64      * Holds a mapping between key=V(vertex) and value=Integer(vertex order). It
65      * can be used for identifying the order of regular vertex/edge.
66      */
67     private Map<V, Integer JavaDoc> mapVertexToOrder;
68
69     /**
70      * Holds a HashSet of all LabelsGraph of the graph.
71      */
72     private Set<LabelsEdge> labelsEdgesSet;
73
74     //~ Constructors ----------------------------------------------------------
75
76     /**
77      * Creates a new labels graph according to the regular graph. After its
78      * creation they will no longer be linked, thus changes to one will not
79      * affect the other.
80      *
81      * @param regularGraph
82      */
83     public GraphOrdering(Graph<V, E> regularGraph)
84     {
85         this(regularGraph, regularGraph.vertexSet(), regularGraph.edgeSet());
86     }
87
88     /**
89      * Creates a new labels graph according to the regular graph. After its
90      * creation they will no longer be linked, thus changes to one will not
91      * affect the other.
92      *
93      * @param regularGraph
94      * @param vertexSet
95      * @param edgeSet
96      */
97     public GraphOrdering(
98         Graph<V, E> regularGraph,
99         Set<V> vertexSet,
100         Set<E> edgeSet)
101     {
102         init(regularGraph, vertexSet, edgeSet);
103     }
104
105     //~ Methods ---------------------------------------------------------------
106
107     private void init(Graph<V, E> g, Set<V> vertexSet, Set<E> edgeSet)
108     {
109         // create a map between vertex value to its order(1st,2nd,etc)
110 // "CAT"=1 "DOG"=2 "RHINO"=3
111
112         this.mapVertexToOrder = new HashMap<V, Integer JavaDoc>(vertexSet.size());
113
114         int counter = 0;
115         for (V vertex : vertexSet) {
116             mapVertexToOrder.put(vertex, new Integer JavaDoc(counter));
117             counter++;
118         }
119
120         // create a friendlier representation of an edge
121 // by order, like 2nd->3rd instead of B->A
122 // use the map to convert vertex to order
123 // on directed graph, edge A->B must be (A,B)
124 // on undirected graph, edge A-B can be (A,B) or (B,A)
125
126         this.labelsEdgesSet = new HashSet<LabelsEdge>(edgeSet.size());
127         for (E edge : edgeSet) {
128             V sourceVertex = g.getEdgeSource(edge);
129             Integer JavaDoc sourceOrder = mapVertexToOrder.get(sourceVertex);
130             int sourceLabel = sourceOrder.intValue();
131             int targetLabel =
132                 (mapVertexToOrder.get(g.getEdgeTarget(edge))).intValue();
133
134             LabelsEdge lablesEdge = new LabelsEdge(sourceLabel, targetLabel);
135             this.labelsEdgesSet.add(lablesEdge);
136
137             if (g instanceof UndirectedGraph) {
138                 LabelsEdge oppositeEdge =
139                     new LabelsEdge(targetLabel, sourceLabel);
140                 this.labelsEdgesSet.add(oppositeEdge);
141             }
142         }
143     }
144
145     /**
146      * Tests equality by order of edges
147      */
148     public boolean equalsByEdgeOrder(GraphOrdering otherGraph)
149     {
150         boolean result =
151             this.getLabelsEdgesSet().equals(otherGraph.getLabelsEdgesSet());
152
153         return result;
154     }
155
156     public Set<LabelsEdge> getLabelsEdgesSet()
157     {
158         return labelsEdgesSet;
159     }
160
161     /**
162      * This is the format example:
163      *
164      * <pre>
165        mapVertexToOrder= labelsOrder=
166      * </pre>
167      */
168     public String JavaDoc toString()
169     {
170         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
171         sb.append("mapVertexToOrder=");
172
173         // vertex will be printed in their order
174 Object JavaDoc [] vertexArray = new Object JavaDoc [this.mapVertexToOrder.size()];
175         Set<V> keySet = this.mapVertexToOrder.keySet();
176         for (V currVertex : keySet) {
177             Integer JavaDoc index = this.mapVertexToOrder.get(currVertex);
178             vertexArray[index.intValue()] = currVertex;
179         }
180         sb.append(ArrayUtil.toString(vertexArray));
181         sb.append("labelsOrder=").append(this.labelsEdgesSet.toString());
182         return sb.toString();
183     }
184
185     //~ Inner Classes ---------------------------------------------------------
186
187     private class LabelsEdge
188     {
189         private int source;
190         private int target;
191         private int hashCode;
192
193         public LabelsEdge(int aSource, int aTarget)
194         {
195             this.source = aSource;
196             this.target = aTarget;
197             this.hashCode =
198                 new String JavaDoc(this.source + "" + this.target).hashCode();
199         }
200
201         /**
202          * Checks both source and target. Does not check class type to be fast,
203          * so it may throw ClassCastException. Careful!
204          *
205          * @see java.lang.Object#equals(java.lang.Object)
206          */
207         public boolean equals(Object JavaDoc obj)
208         {
209             LabelsEdge otherEdge = (LabelsEdge) obj;
210             if (
211                 (this.source == otherEdge.source)
212                 && (this.target == otherEdge.target)) {
213                 return true;
214             } else {
215                 return false;
216             }
217         }
218
219         /**
220          * @see java.lang.Object#hashCode()
221          */
222         public int hashCode()
223         {
224             return this.hashCode; // filled on constructor
225 }
226
227         public String JavaDoc toString()
228         {
229             return this.source + "->" + this.target;
230         }
231     }
232 }
233
Popular Tags