EquivalenceIsomorphismInspector


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   * EquivalenceIsomorphismInspector.java
27   * -----------------
28   * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29   *
30   * Original Author:  Assaf Lehr
31   * Contributor(s):   -
32   *
33   * $Id: EquivalenceIsomorphismInspector.java 485 2006-06-26 09:12:14Z
34   * perfecthash $
35   *
36   * Changes
37   * -------
38   */
39  package org.jgrapht.experimental.isomorphism;
40  
41  import java.util.*;
42  
43  import org.jgrapht.*;
44  import org.jgrapht.experimental.equivalence.*;
45  import org.jgrapht.experimental.permutation.*;
46  
47  
48  /**
49   * The current implementation uses the vertexComparator to greatly increase the
50   * test speed by dividing the vertexes into equivalent groups and permuting
51   * inside them only. The EdgeComparator is used to test edges, but not to make a
52   * finer division, thus it adds overhead.  Use it only when needed.
53   *
54   * @author Assaf
55   * @since Jul 29, 2005
56   */
57  class EquivalenceIsomorphismInspector<V, E>
58      extends AbstractExhaustiveIsomorphismInspector<V, E>
59  {
60  
61      //~ Constructors ----------------------------------------------------------
62  
63      /**
64       * @param graph1
65       * @param graph2
66       * @param vertexChecker eq. group checker for vertexes. If null,
67       *                      UniformEquivalenceComparator will be used as default
68       *                      (always return true)
69       * @param edgeChecker eq. group checker for edges. If null,
70       *                    UniformEquivalenceComparator will be used as default
71       *                    (always return true)
72       */
73      public EquivalenceIsomorphismInspector(
74          Graph<V, E> graph1,
75          Graph<V, E> graph2,
76          
77          // XXX hb 060128: FOllowing parameter may need Graph<? super V,? super
78      // E>
79      EquivalenceComparator<? super V, ? super Graph<? super V, ? super E>> vertexChecker,
80          EquivalenceComparator<? super E, ? super Graph<? super V, ? super E>> edgeChecker)
81      {
82          super(graph1, graph2, vertexChecker, edgeChecker);
83      }
84  
85      /**
86       * Constructor which uses the default comparators.
87       *
88       * @see ExhaustiveIsomorphismInspector(Graph,Graph,EquivalenceComparator,EquivalenceComparator)
89       */
90      public EquivalenceIsomorphismInspector(
91          Graph<V, E> graph1,
92          Graph<V, E> graph2)
93      {
94          super(graph1, graph2);
95      }
96  
97      //~ Methods ---------------------------------------------------------------
98  
99      /**
100      * Creates the permutation iterator according to equivalance class.
101      *
102      * <p>1. Get the eq.group (ordered by size) array of the source vertex set
103      * (vertexSet1)
104      *
105      * <p>2. Get the eq.group ordered array of vertexSet2.
106      *
107      * <p>3. Reorder the second array to match the group order of the first
108      * array sets. 4. Use CompoundPermutationIter (and not regular
109      * IntegerPermutationIter) to permute only inside groups.
110      *
111      * <p>
112      * <p>That's it. If the eq.group comaparator is strong enough to provide
113      * small groups, this algortihm will produce a small possible permutations
114      * numbers. example: G1: [A,B,F,X,Y]  [A->B,B->X,X->Y]
115      *
116      * <p>G2: [D,Z,C,U,F]  [D->C,Z->C,U->Z]
117      *
118      * <p>vertexEq: three groups , one all letters A-E , second all letters S-Z
119      * , third the letter 'f'. 1. [(f)size=1, (X,Y)size=2 , (A,B)size=2] 2.
120      * [(f)size=1 ,(C,D)size=2 , (Z,U)size=2] 3. the match is done by reordering
121      * the second array to have the equiviavlant order :##[(f)size=1 ,
122      * (Z,U)size=2 , (C,D)size=2]## 4.for example G2 will not do all 5!=120
123      * permutations , but 2!x2!x1!=4 permutations only which are: (of the 3rd
124      * array) [ F, Z , U , C , D ] [ F, Z , U , D , C ] [ F, U , Z, C , D ] [
125      * F, U , Z , D , C ]
126      *
127      * @return null, if the eq.group do not match (there cannot be any
128      *         permutation for eq.groups) or the sets do not match in size;
129      *         otherwise, the permutationiterator otherwise
130      *
131      * @see AbstractExhaustiveIsomorphismInspector#createPermutationIterator(Set,
132      *      Set)
133      */
134     @SuppressWarnings  ("unchecked")
135     protected CollectionPermutationIter<V> createPermutationIterator(
136         Set<V> vertexSet1,
137         Set<V> vertexSet2)
138     {
139         if (vertexSet1.size() != vertexSet2.size()) {
140             // throw new IllegalArgumentException("the two vertx-sets
141             // parameters must be of"
142             // +"the same size. The first size was:"+vertexSet1.size()
143             // +" the other size was:" +vertexSet2.size() );
144             return null; // only instead of exception
145         }
146 
147         // 1//
148         EquivalenceSet [] eqGroupArray1 =
149             EquivalenceSetCreator.createEqualityGroupOrderedArray(
150                 vertexSet1,
151                 this.vertexComparator,
152                 this.graph1);
153 
154         // 2//
155         EquivalenceSet [] eqGroupArray2 =
156             EquivalenceSetCreator.createEqualityGroupOrderedArray(
157                 vertexSet2,
158                 this.vertexComparator,
159                 this.graph2);
160 
161         // 3//
162         boolean reorderSuccess =
163             reorderTargetArrayToMatchSourceOrder(eqGroupArray1, eqGroupArray2); // 2 is the taget
164         if (!reorderSuccess) {
165             // if reordering fail , no match can be done
166             return null;
167         }
168 
169         // reorder set1 (source), so when we work with the flat array of the
170         // second array,
171         // the permutations will be relevant.
172         // note that it does not start in any way related to eqGroup sizes.
173 
174         V [] reorderingVertexSet1Temp = (V []) new Object   [vertexSet1.size()];
175         fillElementsflatArray(eqGroupArray1, reorderingVertexSet1Temp);
176         vertexSet1.clear();
177         vertexSet1.addAll(Arrays.asList(reorderingVertexSet1Temp));
178 
179         // 4//use CompoundPermutationIter to permute only inside groups.
180         // the CollectionPermutationIter needs a array/set of objects and a
181         // permuter which will
182         // work on that set/array order. lets make these two:
183         // 1. create array of the vertexes , by flattening the eq.group array
184         // contents
185 
186         V [] flatVertexArray = (V []) new Object   [vertexSet2.size()];
187         fillElementsflatArray(eqGroupArray2, flatVertexArray);
188 
189         // 2. make the permuter according to the groups size
190         int [] groupSizesArray = new int [eqGroupArray1.length];
191 
192         // iterate over the EqualityGroup array
193         for (
194             int eqGroupCounter = 0;
195             eqGroupCounter < eqGroupArray2.length;
196             eqGroupCounter++) {
197             // now for (.2.) size count
198             groupSizesArray[eqGroupCounter] =
199                 eqGroupArray2[eqGroupCounter].size();
200         }
201 
202         ArrayPermutationsIter arrayPermIter =
203             PermutationFactory.createByGroups(groupSizesArray);
204         CollectionPermutationIter<V> vertexPermIter =
205             new CollectionPermutationIter<V>(
206                 Arrays.asList(flatVertexArray),
207                 arrayPermIter);
208 
209         return vertexPermIter;
210     }
211 
212     /**
213      * Reorders inplace targetArray
214      *
215      * <p>rules:
216      * <li>try to match only group of the same size and then hashcode
217      * <li>it is enough to choose one from each group to see if a match exist.
218      *
219      * <p>Algorithm: hold counters in the two arrays. [a,b,c,d,e]  assume groups
220      * are:a,(b,c,d),e [a,c,d,b,e] c1=0 , c2=0 check if eqvivalent . if not ,
221      * advance , as long as both size and hashcode are the same. if found a
222      * match , swap the group positions in array2. if not , throws
223      * IllegalArgumentExcpetion. Assumption: array size is the same. not
224      * checked.
225      *
226      * @param sourceArray
227      * @param targetArray
228      *
229      * @return true if the array was reordered successfully. false if not(It
230      *         will happen if there is no complete match between the groups)
231      */
232     private boolean reorderTargetArrayToMatchSourceOrder(
233         EquivalenceSet [] sourceArray,
234         EquivalenceSet [] targetArray)
235     {
236         boolean result = true;
237         for (
238             int sourceIndex = 0;
239             sourceIndex < sourceArray.length;
240             sourceIndex++) {
241             int currTargetIndex = sourceIndex;
242 
243             // if they are already equivalent do nothing.
244             EquivalenceSet sourceEqGroup = sourceArray[sourceIndex];
245             EquivalenceSet targetEqGroup = targetArray[currTargetIndex];
246             if (!sourceEqGroup.equals(targetEqGroup)) {
247                 // iterate through the next group in the targetArray until
248                 // a new size or hashcode is seen
249                 boolean foundMatch = false;
250                 int sourceSize = sourceEqGroup.size();
251                 int sourceHashCode = sourceEqGroup.hashCode();
252                 while (
253                     (targetEqGroup.size() == sourceSize)
254                     && (targetEqGroup.hashCode() == sourceHashCode)
255                     && (currTargetIndex < targetArray.length)) {
256                     currTargetIndex++;
257                     targetEqGroup = targetArray[currTargetIndex];
258                     if (targetEqGroup.equals(sourceEqGroup)) {
259                         foundMatch = true;
260 
261                         // swap . targetEqGroup will serve as the temp
262                         // variable.
263                         targetArray[currTargetIndex] = targetArray[sourceIndex];
264                         targetArray[sourceIndex] = targetEqGroup;
265                     }
266                 }
267                 if (!foundMatch) {
268                     // a match was not found
269                     // throw new IllegalArgumentException("could not reorder
270                     // the array , because the groups don`t match");
271                     result = false;
272                     break;
273                 }
274             }
275         }
276         return result;
277     }
278 
279     /**
280      * @param eqGroupArray
281      * @param flatArray an empy array with the proper size
282      */
283     protected void fillElementsflatArray(
284         EquivalenceSet [] eqGroupArray,
285         Object   [] flatVertexArray)
286     {
287         int flatVertexArrayNextFree = 0; // the next free place in the array
288 
289         // iterate over the EqualityGroup array
290         for (
291             int eqGroupCounter = 0;
292             eqGroupCounter < eqGroupArray.length;
293             eqGroupCounter++) {
294             Object   [] currGroupArray = eqGroupArray[eqGroupCounter].toArray();
295 
296             // copy this small array to the free place in the big
297             // flatVertexArray
298             System.arraycopy(
299                 currGroupArray, // src
300                 0, // srcPos
301                 flatVertexArray, // dest
302                 flatVertexArrayNextFree, // destPos
303                 currGroupArray.length // length
304             );
305             flatVertexArrayNextFree += currGroupArray.length;
306         }
307     }
308 
309     /**
310      * We know for sure, that the sets are alreay checked for equivalence , so
311      * it will return true without any further checks.
312      *
313      * @see AbstractExhaustiveIsomorphismInspector#areVertexSetsOfTheSameEqualityGroup(
314      *      Set, Set)
315      */
316     protected boolean areVertexSetsOfTheSameEqualityGroup(
317         Set vertexSet1,
318         Set vertexSet2)
319     {
320         return true;
321     }
322 }
323
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags