KickJava   Java API By Example, From Geeks To Geeks.

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


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  * PermutationIsomorphismInspector.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: PermutationIsomorphismInspector.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  * Checks every possible permutation.
50  *
51  * <p>It does not uses the graph topology to enhance the performance. It is
52  * recommended to use only if there cannot be a useful division into equivalence
53  * sets.
54  *
55  * @author Assaf
56  * @since Jul 29, 2005
57  */
58 class PermutationIsomorphismInspector<V, E>
59     extends AbstractExhaustiveIsomorphismInspector<V, E>
60 {
61
62     //~ Constructors ----------------------------------------------------------
63
64     /**
65      * @param graph1
66      * @param graph2
67      * @param vertexChecker eq. group checker for vertexes. If null,
68      * UniformEquivalenceComparator will be used as default
69      * (always return true)
70      * @param edgeChecker eq. group checker for edges. If null,
71      * UniformEquivalenceComparator will be used as default
72      * (always return true)
73      */
74     public PermutationIsomorphismInspector(
75         Graph<V, E> graph1,
76         Graph<V, E> graph2,
77         
78         // XXX hb 060128: FOllowing parameter may need Graph<? super V,? super
79 // E>
80 EquivalenceComparator<? super V, ? super Graph<? super V, ? super E>> vertexChecker,
81         EquivalenceComparator<? super E, ? super Graph<? super V, ? super E>> edgeChecker)
82     {
83         super(graph1, graph2, vertexChecker, edgeChecker);
84     }
85
86     /**
87      * Constructor which uses the default comparators.
88      *
89      * @see AbstractExhaustiveIsomorphismInspector#AbstractExhaustiveIsomorphismInspector(Graph,
90      * Graph)
91      */
92     public PermutationIsomorphismInspector(
93         Graph<V, E> graph1,
94         Graph<V, E> graph2)
95     {
96         super(graph1, graph2);
97     }
98
99     //~ Methods ---------------------------------------------------------------
100
101     /**
102      * Creates the permutation iterator, not dependant on equality group, or the
103      * other vertexset.
104      *
105      * @param vertexSet1 FIXME Document me
106      * @param vertexSet2 FIXME Document me
107      *
108      * @return the permutation iterator
109      */
110     protected CollectionPermutationIter<V> createPermutationIterator(
111         Set<V> vertexSet1,
112         Set<V> vertexSet2)
113     {
114         return new CollectionPermutationIter<V>(vertexSet2);
115     }
116
117     /**
118      * FIXME Document me FIXME Document me
119      *
120      * @param vertexSet1 FIXME Document me
121      * @param vertexSet2 FIXME Document me
122      *
123      * @return FIXME Document me
124      */
125     protected boolean areVertexSetsOfTheSameEqualityGroup(
126         Set<V> vertexSet1,
127         Set<V> vertexSet2)
128     {
129         if (vertexSet1.size() != vertexSet2.size()) {
130             return false;
131         }
132         Iterator<V> iter2 = vertexSet2.iterator();
133
134         // only check hasNext() of one , cause they are of the same size
135 for (Iterator<V> iter1 = vertexSet1.iterator(); iter1.hasNext();) {
136             V vertex1 = iter1.next();
137             V vertex2 = iter2.next();
138             if (
139                 !this.vertexComparator.equivalenceCompare(
140                     vertex1,
141                     vertex2,
142                     this.graph1,
143                     this.graph2)) {
144                 return false;
145             }
146         }
147         return true;
148     }
149 }
150
Popular Tags