KickJava   Java API By Example, From Geeks To Geeks.

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


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  * AbstractExhaustiveIsomorphismInspector.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: AbstractExhaustiveIsomorphismInspector.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 import org.jgrapht.util.*;
47
48
49 /**
50  * Abstract base for isomorphism inspectors which exhaustively test the possible
51  * mappings between graphs. The current algorithms do not support graphs with
52  * multiple edges (Multigraph / Pseudograph). For the maintainer: The reason is
53  * the use of GraphOrdering which currently does not support all graph types.
54  *
55  * @author Assaf Lehr
56  * @since May 20, 2005 ver5.3
57  */
58 abstract class AbstractExhaustiveIsomorphismInspector<V, E>
59     implements GraphIsomorphismInspector<IsomorphismRelation>
60 {
61
62     //~ Static fields/initializers --------------------------------------------
63
64     public static EquivalenceComparator<Object JavaDoc, Object JavaDoc> edgeDefaultIsomorphismComparator =
65         new UniformEquivalenceComparator<Object JavaDoc, Object JavaDoc>();
66     public static EquivalenceComparator<Object JavaDoc, Object JavaDoc> vertexDefaultIsomorphismComparator =
67         new UniformEquivalenceComparator<Object JavaDoc, Object JavaDoc>();
68
69     //~ Instance fields -------------------------------------------------------
70
71     protected EquivalenceComparator<? super E, ? super Graph<V, ? super E>> edgeComparator;
72     protected EquivalenceComparator<? super V, ? super Graph<? super V, E>> vertexComparator;
73
74     protected Graph<V, E> graph1;
75     protected Graph<V, E> graph2;
76
77     private PrefetchIterator<IsomorphismRelation> nextSupplier;
78
79     // kept as member, to ease computations
80 private GraphOrdering lableGraph1;
81     private LinkedHashSet<V> graph1VertexSet;
82     private LinkedHashSet<E> graph2EdgeSet;
83     private CollectionPermutationIter<V> vertexPermuteIter;
84     private Set<V> currVertexPermutation; // filled every iteration, used in the
85
86     // result relation.
87
88     //~ Constructors ----------------------------------------------------------
89
90     /**
91      * @param graph1
92      * @param graph2
93      * @param vertexChecker eq. group checker for vertexes. If null,
94      * UniformEquivalenceComparator will be used as default
95      * (always return true)
96      * @param edgeChecker eq. group checker for edges. If null,
97      * UniformEquivalenceComparator will be used as default
98      * (always return true)
99      */
100     public AbstractExhaustiveIsomorphismInspector(
101         Graph<V, E> graph1,
102         Graph<V, E> graph2,
103         
104         // XXX hb 060128: FOllowing parameter may need Graph<? super V,? super
105 // E>
106 EquivalenceComparator<? super V, ? super Graph<? super V, ? super E>> vertexChecker,
107         EquivalenceComparator<? super E, ? super Graph<? super V, ? super E>> edgeChecker)
108     {
109         this.graph1 = graph1;
110         this.graph2 = graph2;
111
112         if (vertexChecker != null) {
113             this.vertexComparator = vertexChecker;
114         } else {
115             this.vertexComparator = vertexDefaultIsomorphismComparator;
116         }
117
118         // Unlike vertexes, edges have better performance, when not tested for
119 // Equivalence, so if the user did not supply one, use null
120 // instead of edgeDefaultIsomorphismComparator.
121
122         if (edgeChecker != null) {
123             this.edgeComparator = edgeChecker;
124         }
125
126         init();
127     }
128
129     /**
130      * Constructor which uses the default comparators.
131      *
132      * @param graph1
133      * @param graph2
134      *
135      * @see #AbstractExhaustiveIsomorphismInspector(Graph,Graph,EquivalenceComparator,EquivalenceComparator)
136      */
137     public AbstractExhaustiveIsomorphismInspector(
138         Graph<V, E> graph1,
139         Graph<V, E> graph2)
140     {
141         this(
142             graph1,
143             graph2,
144             edgeDefaultIsomorphismComparator,
145             vertexDefaultIsomorphismComparator);
146     }
147
148     //~ Methods ---------------------------------------------------------------
149
150     /**
151      * Inits needed data-structures , among them:
152      * <li>LabelsGraph which is a created in the image of graph1
153      * <li>vertexPermuteIter which is created after the vertexes were divided to
154      * equivalence groups. This saves order-of-magnitude in performance, because
155      * the number of possible permutations dramatically decreases.
156      *
157      * <p>for example: if the eq.group are even/odd - only two groups. A graph
158      * with consist of 10 nodes of which 5 are even , 5 are odd , will need to
159      * test 5!*5! (14,400) instead of 10! (3,628,800).
160      *
161      * <p>besides the EquivalenceComparator`s supplied by the user, we also use
162      * predefined topological comparators.
163      */
164     private void init()
165     {
166         this.nextSupplier =
167             new PrefetchIterator<IsomorphismRelation>(
168                 // XXX hb 280106: I don't understand this warning, yet :-)
169 new NextFunctor());
170
171         this.graph1VertexSet = new LinkedHashSet<V>(this.graph1.vertexSet());
172
173         // vertexPermuteIter will be null, if there is no match
174 this.vertexPermuteIter =
175             createPermutationIterator(
176                 this.graph1VertexSet,
177                 this.graph2.vertexSet());
178
179         this.lableGraph1 =
180             new GraphOrdering<V, E>(
181                 this.graph1,
182                 this.graph1VertexSet,
183                 this.graph1.edgeSet());
184
185         this.graph2EdgeSet = new LinkedHashSet<E>(this.graph2.edgeSet());
186     }
187
188     /**
189      * Creates the permutation iterator for vertexSet2 . The subclasses may make
190      * either cause it to depend on equality groups or use vertexSet1 for it.
191      *
192      * @param vertexSet1 [i] may be reordered
193      * @param vertexSet2 [i] may not.
194      *
195      * @return permutation iterator
196      */
197     protected abstract CollectionPermutationIter<V> createPermutationIterator(
198         Set<V> vertexSet1,
199         Set<V> vertexSet2);
200
201     /**
202      * <p>1. Creates a LabelsGraph of graph1 which will serve as a source to all
203      * the comparisons which will follow.
204      *
205      * <p>2. extract the edge array of graph2; it will be permanent too.
206      *
207      * <p>3. for each permutation of the vertexes of graph2, test :
208      *
209      * <p>3.1. vertices
210      *
211      * <p>3.2. edges (in labelsgraph)
212      *
213      * <p>Implementation Notes and considerations: Let's consider a trivial
214      * example: graph of strings "A","B","C" with two edges A->B,B->C. Let's
215      * assume for this example that the vertex comparator always returns true,
216      * meaning String value does not matter, only the graph structure does. So
217      * "D" "E" "A" with D->E->A will be isomorphic , but "A","B,"C"with
218      * A->B,A->C will not.
219      *
220      * <p>First let's extract the important info for isomorphism from the graph.
221      * We don't care what the vertexes are, we care that there are 3 of them
222      * with edges from first to second and from second to third. So the source
223      * LabelsGraph will be: vertexes:[1,2,3] edges:[[1->2],[2->3]] Now we will
224      * do several permutations of D,E,A. A few examples: D->E , E->A
225      * [1,2,3]=[A,D,E] so edges are: 2->3 , 3->1 . does it match the source?
226      * NO. [1,2,3]=[D,A,E] so edges are: 1->3 , 3->2 . no match either.
227      * [1,2,3]=[D,E,A] so edges are: 1->2 , 2->3 . MATCH FOUND ! Trivial
228      * algorithm: We will iterate on all permutations
229      * [abc][acb][bac][bca][cab][cba]. (n! of them,3!=6) For each, first compare
230      * vertexes using the VertexComparator(always true). Then see that the edges
231      * are in the exact order 1st->2nd , 2nd->3rd. If we found a match stop and
232      * return true, otherwise return false; we will compare vetices and edges by
233      * their order (1st,2nd,3rd,etc) only. Two graphs are the same, by this
234      * order, if: 1. for each i, sourceVertexArray[i] is equivalent to
235      * targetVertexArray[i] 2. for each vertex, the edges which start in it (it
236      * is the source) goes to the same ordered vertex. For multiple ones, count
237      * them too.
238      *
239      * @return IsomorphismRelation for a permutation found, or null if no
240      * permutation was isomorphic
241      */
242     private IsomorphismRelation<V, E> findNextIsomorphicGraph()
243     {
244         boolean result = false;
245         IsomorphismRelation<V, E> resultRelation = null;
246         if (this.vertexPermuteIter != null) {
247             // System.out.println("Souce LabelsGraph="+this.lableGraph1);
248 while (this.vertexPermuteIter.hasNext()) {
249                 currVertexPermutation = this.vertexPermuteIter.getNextSet();
250
251                 // compare vertexes
252 if (
253                     !areVertexSetsOfTheSameEqualityGroup(
254                         this.graph1VertexSet,
255                         currVertexPermutation)) {
256                     continue; // this one is not iso, so try the next one
257 }
258
259                 // compare edges
260 GraphOrdering<V, E> currPermuteGraph =
261                     new GraphOrdering<V, E>(
262                         this.graph2,
263                         currVertexPermutation,
264                         this.graph2EdgeSet);
265
266                 // System.out.println("target LablesGraph="+currPermuteGraph);
267 if (this.lableGraph1.equalsByEdgeOrder(currPermuteGraph)) {
268                     // create result object.
269 resultRelation =
270                         new IsomorphismRelation<V, E>(
271                             new ArrayList<V>(graph1VertexSet),
272                             new ArrayList<V>(currVertexPermutation),
273                             graph1,
274                             graph2);
275
276                     // if the edge comparator exists, check equivalence by it
277 boolean edgeEq =
278                         areAllEdgesEquivalent(
279                             resultRelation,
280                             this.edgeComparator);
281                     if (edgeEq) // only if equivalent
282 {
283                         result = true;
284                         break;
285                     }
286                 }
287             }
288         }
289
290         if (result == true) {
291             return resultRelation;
292         } else {
293             return null;
294         }
295     }
296
297     /**
298      * Will be called on every two sets of vertexes returned by the permutation
299      * iterator. From findNextIsomorphicGraph(). Should make sure that the two
300      * sets are euqivalent. Subclasses may decide to implements it as an always
301      * true methods only if they make sure that the permutationIterator will
302      * always be already equivalent.
303      *
304      * @param vertexSet1 FIXME Document me
305      * @param vertexSet2 FIXME Document me
306      */
307     protected abstract boolean areVertexSetsOfTheSameEqualityGroup(
308         Set<V> vertexSet1,
309         Set<V> vertexSet2);
310
311     /**
312      * For each edge in g1, get the Correspondence edge and test the pair.
313      *
314      * @param resultRelation
315      * @param edgeComparator if null, always return true.
316      */
317     protected boolean areAllEdgesEquivalent(
318         IsomorphismRelation<V, E> resultRelation,
319         EquivalenceComparator<? super E, ? super Graph<V, E>> edgeComparator)
320     {
321         boolean checkResult = true;
322
323         if (edgeComparator == null) {
324             // nothing to check
325 return true;
326         }
327
328         try {
329             Set<E> edgeSet = this.graph1.edgeSet();
330
331             for (E currEdge : edgeSet) {
332                 E correspondingEdge =
333                     resultRelation.getEdgeCorrespondence(currEdge, true);
334
335                 // if one edge test fail , fail the whole method
336 if (
337                     !edgeComparator.equivalenceCompare(
338                         currEdge,
339                         correspondingEdge,
340                         this.graph1,
341                         this.graph2)) {
342                     checkResult = false;
343                     break;
344                 }
345             }
346         } catch (IllegalArgumentException JavaDoc illegal) {
347             checkResult = false;
348         }
349
350         return checkResult;
351     }
352
353     /**
354      * return nextElement() casted as IsomorphismRelation
355      */
356     public IsomorphismRelation nextIsoRelation()
357     {
358         return next();
359     }
360
361     /**
362      * Efficiency: The value is known after the first check for isomorphism
363      * activated on this class and returned there after in O(1). If called on a
364      * new ("virgin") class, it activates 1 iso-check.
365      *
366      * @return <code>true</code> iff the two graphs are isomorphic
367      */
368     public boolean isIsomorphic()
369     {
370         return !(this.nextSupplier.isEnumerationStartedEmpty());
371     }
372
373     /* (non-Javadoc)
374      * @see java.util.Enumeration#hasMoreElements()
375      */
376     public boolean hasNext()
377     {
378         boolean result = this.nextSupplier.hasMoreElements();
379
380         return result;
381     }
382
383     /**
384      * @see java.util.Iterator#next()
385      */
386     public IsomorphismRelation next()
387     {
388         return this.nextSupplier.nextElement();
389     }
390
391     /* (non-Javadoc)
392      * @see java.util.Iterator#remove()
393      */
394     public void remove()
395     {
396         throw new UnsupportedOperationException JavaDoc(
397             "remove() method is not supported in AdaptiveIsomorphismInspectorFactory."
398             + " There is no meaning to removing an isomorphism result.");
399     }
400
401     //~ Inner Classes ---------------------------------------------------------
402
403     private class NextFunctor
404         implements PrefetchIterator.NextElementFunctor<IsomorphismRelation>
405     {
406         public IsomorphismRelation nextElement()
407             throws NoSuchElementException
408         {
409             IsomorphismRelation resultRelation = findNextIsomorphicGraph();
410             if (resultRelation != null) {
411                 return resultRelation;
412             } else {
413                 throw new NoSuchElementException(
414                     "IsomorphismInspector does not have any more elements");
415             }
416         }
417     }
418 }
419
Popular Tags