AdaptiveIsomorphismInspectorFactory


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   * AdaptiveIsomorphismInspectorFactory.java
27   * -----------------
28   * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29   *
30   * Original Author:  Assaf Lehr
31   * Contributor(s):   -
32   *
33   * $Id: AdaptiveIsomorphismInspectorFactory.java 485 2006-06-26 09:12:14Z
34   * perfecthash $
35   *
36   * Changes
37   * -------
38   */
39  package org.jgrapht.experimental.isomorphism;
40  
41  import org.jgrapht.*;
42  import org.jgrapht.experimental.equivalence.*;
43  import org.jgrapht.graph.*;
44  
45  
46  /**
47   * This class serves as a factory for GraphIsomorphismInspector concrete
48   * implementations. It can be used in two ways:
49   * <li>You can can let this class to determine what is the most efficient
50   * algorithm for your graph.
51   * <li>You can specify the type of your graph (planar / tree / other) and save
52   * this class the graph-checking time.
53   *
54   * <p>Note that the concrete implementations are package-private and should not
55   * be created directly.  If you are the maintainer of the package, you can add
56   * new implementation classes, and add them to the "check-list". The current
57   * algorithms do not support graphs with multiple edges (Multigraph /
58   * Pseudograph)
59   *
60   * @author Assaf
61   * @see GraphIsomorphismInspector
62   * @since Jul 17, 2005
63   */
64  public class AdaptiveIsomorphismInspectorFactory
65  {
66  
67      //~ Static fields/initializers --------------------------------------------
68  
69      public static final int GRAPH_TYPE_ARBITRARY = 0;
70      public static final int GRAPH_TYPE_PLANAR = 1;
71      public static final int GRAPH_TYPE_TREE = 2;
72      public static final int GRAPH_TYPE_MULTIGRAPH = 3;
73  
74      //~ Methods ---------------------------------------------------------------
75  
76      /**
77       * Creates a new inspector, letting this class determine what is the most
78       * efficient algorithm.
79       *
80       * @param graph1
81       * @param graph2
82       * @param vertexChecker may be null
83       * @param edgeChecker may be null
84       */
85      public static <V, E> GraphIsomorphismInspector createIsomorphismInspector(
86          Graph<V, E> graph1,
87          Graph<V, E> graph2,
88          EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
89          EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
90      {
91          int graphType = checkGraphsType(graph1, graph2);
92          return
93              createAppropriateConcreteInspector(
94                  graphType,
95                  graph1,
96                  graph2,
97                  vertexChecker,
98                  edgeChecker);
99      }
100 
101     /**
102      * Creates a new inspector, letting this class determine what is the most
103      * efficient algorithm and using default equivalence comparators.
104      *
105      * <p>same as calling createIsomorphismInspector(graph1,graph2,null,null);
106      *
107      * @param graph1
108      * @param graph2
109      */
110     public static <V, E> GraphIsomorphismInspector createIsomorphismInspector(
111         Graph<V, E> graph1,
112         Graph<V, E> graph2)
113     {
114         return createIsomorphismInspector(graph1, graph2, null, null);
115     }
116 
117     /**
118      * Creates a new inspector for a particular graph type (planar / tree /
119      * other).
120      *
121      * @param type - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX
122      * @param graph1
123      * @param graph2
124      * @param vertexChecker - can be null
125      * @param edgeChecker - can be null
126      */
127     public static <V, E> GraphIsomorphismInspector
128     createIsomorphismInspectorByType(
129         int type,
130         Graph<V, E> graph1,
131         Graph<V, E> graph2,
132         EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
133         EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
134     {
135         return
136             createAppropriateConcreteInspector(
137                 type,
138                 graph1,
139                 graph2,
140                 vertexChecker,
141                 edgeChecker);
142     }
143 
144     /**
145      * Creates a new inspector for a particular graph type (planar / tree /
146      * other) using default equivalence comparators.
147      *
148      * <p>same as calling
149      * createAppropriateConcreteInspector(graph1,graph2,null,null);
150      *
151      * @param type - AdaptiveIsomorphismInspectorFactory.GRAPH_TYPE_XXX
152      * @param graph1
153      * @param graph2
154      */
155     public static <V, E> GraphIsomorphismInspector
156     createIsomorphismInspectorByType(
157         int type,
158         Graph<V, E> graph1,
159         Graph<V, E> graph2)
160     {
161         return
162             createAppropriateConcreteInspector(
163                 type,
164                 graph1,
165                 graph2,
166                 null,
167                 null);
168     }
169 
170     /**
171      * Checks the graph type, and accordingly decides which type of concrete
172      * inspector class to create. This implementation creates an exhaustive
173      * inspector without further tests, because no other implementations are
174      * available yet.
175      *
176      * @param graph1
177      * @param graph2
178      * @param vertexChecker
179      * @param edgeChecker
180      */
181     protected static <V, E> GraphIsomorphismInspector
182     createAppropriateConcreteInspector(
183         int graphType,
184         Graph<V, E> graph1,
185         Graph<V, E> graph2,
186         EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
187         EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
188     {
189         assertUnsupportedGraphTypes(graph1);
190         assertUnsupportedGraphTypes(graph2);
191         GraphIsomorphismInspector currentInspector = null;
192 
193         switch (graphType) {
194         case GRAPH_TYPE_PLANAR:
195         case GRAPH_TYPE_TREE:
196         case GRAPH_TYPE_ARBITRARY:
197             currentInspector =
198                 createTopologicalExhaustiveInspector(
199                     graph1,
200                     graph2,
201                     vertexChecker,
202                     edgeChecker);
203             break;
204 
205         default:
206 
207             throw new IllegalArgumentException  (
208                 "The type was not one of the supported types.");
209         }
210         return currentInspector;
211     }
212 
213     /**
214      * Checks if one of the graphs is from unsupported graph type and throws
215      * IllegalArgumentException if it is. The current unsupported types are
216      * graphs with multiple-edges.
217      *
218      * @param graph1
219      * @param graph2
220      *
221      * @throws IllegalArgumentException
222      */
223     protected static void assertUnsupportedGraphTypes(Graph g)
224         throws IllegalArgumentException  
225     {
226         if (
227             (g instanceof Multigraph)
228             || (g instanceof DirectedMultigraph)
229             || (g instanceof Pseudograph)) {
230             throw new IllegalArgumentException  (
231                 "graph type not supported for the graph" + g);
232         }
233     }
234 
235     protected static int checkGraphsType(Graph graph1, Graph graph2)
236     {
237         return GRAPH_TYPE_ARBITRARY;
238     }
239 
240     /**
241      * @return ExhaustiveInspector, where the equivalence comparator is chained
242      *         with a topological comparator. This implementation uses:
243      *         <li>vertex degree size comparator
244      */
245     @SuppressWarnings  ("unchecked")
246     protected static <V, E> GraphIsomorphismInspector
247     createTopologicalExhaustiveInspector(
248         Graph<V, E> graph1,
249         Graph<V, E> graph2,
250         EquivalenceComparator<? super V, ? super Graph<V, E>> vertexChecker,
251         EquivalenceComparator<? super E, ? super Graph<V, E>> edgeChecker)
252     {
253         VertexDegreeEquivalenceComparator<V, E> degreeComparator =
254             new VertexDegreeEquivalenceComparator<V, E>();
255         EquivalenceComparatorChain<V, Graph<V, E>> vertexChainedChecker =
256             new EquivalenceComparatorChainBase<V, Graph<V, E>>(
257                 degreeComparator);
258         vertexChainedChecker.appendComparator(vertexChecker);
259 
260         GraphIsomorphismInspector inspector =
261 
262             // FIXME hb060208 I don't understand how to generify this, yet
263             new EquivalenceIsomorphismInspector(
264                 graph1,
265                 graph2,
266                 vertexChainedChecker,
267                 edgeChecker);
268         return inspector;
269     }
270 }
271
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags