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


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  * IsomorphismInspectorTest.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: IsomorphismInspectorTest.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 junit.framework.*;
43
44 import org.jgrapht.*;
45 import org.jgrapht.experimental.equivalence.*;
46 import org.jgrapht.experimental.isomorphism.comparators.*;
47 import org.jgrapht.generate.*;
48 import org.jgrapht.graph.*;
49
50
51 /**
52  * @author Assaf
53  * @since May 27, 2005
54  */
55 public class IsomorphismInspectorTest
56     extends TestCase
57 {
58
59     //~ Constructors ----------------------------------------------------------
60
61     /**
62      * Constructor for IsomorphismInspectorTest.
63      *
64      * @param arg0
65      */
66     public IsomorphismInspectorTest(String arg0)
67     {
68         super(arg0);
69     }
70
71     //~ Methods ---------------------------------------------------------------
72
73     /*
74      * @see TestCase#setUp()
75      */
76     protected void setUp()
77         throws Exception
78     {
79         super.setUp();
80     }
81
82     /**
83      * Calls the same method with different (default) parameters
84      * EqualityGroupChecker vertexChecker = null EqualityGroupChecker
85      * edgeChecker = null
86      */
87     private void assertIsomorphic(
88         Graph<Integer , DefaultEdge> [] graphs,
89         boolean shouldTheyBeIsomorphic)
90     {
91         assertIsomorphic(graphs, shouldTheyBeIsomorphic, null, null);
92     }
93
94     @SuppressWarnings ("unchecked")
95     private void assertIsomorphic(
96         Graph<Integer , DefaultEdge> [] graphs,
97         boolean shouldTheyBeIsomorphic,
98         EquivalenceComparator vertexChecker,
99         EquivalenceComparator edgeChecker)
100     {
101         // System.out.println("\nassertIsomorphic:"+shouldTheyBeIsomorphic);
102 Graph<Integer , DefaultEdge> g1 = graphs[0];
103         Graph<Integer , DefaultEdge> g2 = graphs[1];
104
105         // System.out.println("g1:"+g1);
106 // System.out.println("g2:"+g2);
107 // long beforeTime=System.currentTimeMillis();
108 GraphIsomorphismInspector iso =
109             AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(
110                 g1,
111                 g2,
112                 vertexChecker,
113                 edgeChecker);
114         int counter = 0;
115         while (iso.hasNext()) {
116             IsomorphismRelation isioResult = (IsomorphismRelation) iso.next();
117
118             if (false) {
119                 if (counter == 0) {
120                     System.out.println(
121                         "Graphs are isomorphic. Iterating over all options:");
122                 }
123                 System.out.println(counter + " : " + isioResult);
124             }
125             counter++;
126         }
127
128         // if (counter==0)
129 // {
130 // System.out.println("Graphs are NOT isomorphic.");
131 // }
132 // long deltaTime=System.currentTimeMillis()-beforeTime;
133 // String timeDesc;
134 // timeDesc= deltaTime<=10 ? "<10ms [less than minimum measurement
135 // time]": String.valueOf(deltaTime);
136 // System.out.println("# Performence: Isomorphism check in
137 // MiliSeconds:"+timeDesc);
138 if (shouldTheyBeIsomorphic) {
139             assertTrue(counter != 0);
140         } else {
141             assertTrue(counter == 0);
142         }
143     }
144
145     @SuppressWarnings ("unchecked")
146     private void checkRelation(
147         Graph<Integer , DefaultEdge> [] graphs,
148         EquivalenceComparator vertexChecker,
149         EquivalenceComparator edgeChecker)
150     {
151         Graph<Integer , DefaultEdge> g1 = graphs[0];
152         Graph<Integer , DefaultEdge> g2 = graphs[1];
153
154         GraphIsomorphismInspector iso =
155             AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(
156                 g1,
157                 g2,
158                 vertexChecker,
159                 edgeChecker);
160         IsomorphismRelation<Integer , DefaultEdge> isoResult;
161         if (iso.hasNext()) {
162             isoResult = (IsomorphismRelation) iso.next();
163
164             Set<Integer > vertexSet = g1.vertexSet();
165             for (Iterator<Integer > iter = vertexSet.iterator();
166                 iter.hasNext();) {
167                 Integer v1 = iter.next();
168                 Integer v2 = isoResult.getVertexCorrespondence(v1, true);
169                 if (false) {
170                     System.out.println("Vertex relation " + v1 + " to " + v2);
171                 }
172             }
173             Set<DefaultEdge> edgeSet = g1.edgeSet();
174             for (
175                 Iterator<DefaultEdge> iter = edgeSet.iterator();
176                 iter.hasNext();) {
177                 DefaultEdge e1 = iter.next();
178                 DefaultEdge e2 = isoResult.getEdgeCorrespondence(e1, true);
179                 if (false) {
180                     System.out.println("Vertex relation " + e1 + " to " + e2);
181                 }
182             }
183
184             // if (counter==0)
185 // {
186 // System.out.println("Graphs are isomorphic. Iterating over all
187 // options:");
188 // }
189 // System.out.println(counter+" : "+isioResult);
190
191         }
192     }
193
194     @SuppressWarnings ("unchecked")
195     public void testWheelGraphAddRemoveParts()
196     {
197         final int NUM_OF_VERTEXES_IN_WHEEL = 6;
198         final int FIRST_INTEGER_FOR_G2 = 13;
199
200         Graph<Integer , DefaultEdge> g1 =
201             new DefaultDirectedGraph<Integer , DefaultEdge>(
202                 DefaultEdge.class);
203         Graph<Integer , DefaultEdge> g2 =
204             new DefaultDirectedGraph<Integer , DefaultEdge>(
205                 DefaultEdge.class);
206         WheelGraphGenerator<Integer , DefaultEdge> gen1 =
207             new WheelGraphGenerator<Integer , DefaultEdge>(
208                 NUM_OF_VERTEXES_IN_WHEEL);
209         gen1.generateGraph(g1, new IntegerVertexFactory(), null);
210
211         // FIRST_INTEGER_FOR_G2-1 , cause first integer is always the next one.
212 gen1.generateGraph(
213             g2,
214             new IntegerVertexFactory(FIRST_INTEGER_FOR_G2),
215             null);
216         assertIsomorphic(new Graph [] {
217                 g1,
218                 g2
219             }, true);
220
221         // In a wheel , the last vertex is the wheel center!
222 g1.removeVertex(new Integer (NUM_OF_VERTEXES_IN_WHEEL)); // delete one vertex from g1
223 assertIsomorphic(new Graph [] {
224                 g1,
225                 g2
226             }, false);
227
228         // for example: 10+4
229 g2.removeVertex(
230             new Integer (FIRST_INTEGER_FOR_G2
231                 + NUM_OF_VERTEXES_IN_WHEEL));
232         assertIsomorphic(new Graph [] {
233                 g1,
234                 g2
235             }, true);
236
237         g1.removeEdge(new Integer (1), new Integer (2));
238         assertIsomorphic(new Graph [] {
239                 g1,
240                 g2
241             }, false);
242     }
243
244     @SuppressWarnings ("unchecked")
245     public void testLinear4vertexIsomorphicGraph()
246     {
247         Graph<Integer , DefaultEdge> g1 =
248             new DefaultDirectedGraph<Integer , DefaultEdge>(
249                 DefaultEdge.class);
250         LinearGraphGenerator gen1 = new LinearGraphGenerator(4);
251         gen1.generateGraph(g1, new IntegerVertexFactory(), null);
252
253         Graph<Integer , DefaultEdge> g2 =
254             new DefaultDirectedGraph<Integer , DefaultEdge>(
255                 DefaultEdge.class);
256         LinearGraphGenerator gen2 = new LinearGraphGenerator(4);
257         gen2.generateGraph(g2, new IntegerVertexFactory(5), null); // start vertex from number 6
258 assertIsomorphic(new Graph [] {
259                 g1,
260                 g2
261             }, true);
262
263         checkRelation(new Graph [] {
264                 g1,
265                 g2
266             }, null, null);
267     }
268
269     /**
270      * Create two graphs which are topologically the same (same number of
271      * vertexes and same edges connection), but the contents of the vertexes
272      * belong to different eq. set. g1: 1-->2-->3-->4 g2: 2-->3-->4-->5 g3:
273      * 3-->4-->5-->6 The eq-group-check is if the number is even or odd. So, g1
274      * and g3 are isomorphic. g2 is not isomorphic to either of them.
275      */
276     @SuppressWarnings ("unchecked")
277     public void testLinear4vertexNonIsomorphicCauseOfVertexEqGroup()
278     {
279         LinearGraphGenerator<Integer , DefaultEdge> gen4 =
280             new LinearGraphGenerator<Integer , DefaultEdge>(4);
281
282         Graph<Integer , DefaultEdge> g1 =
283             new DefaultDirectedGraph<Integer , DefaultEdge>(
284                 DefaultEdge.class);
285         gen4.generateGraph(g1, new IntegerVertexFactory(), null);
286
287         Graph<Integer , DefaultEdge> g2 =
288             new DefaultDirectedGraph<Integer , DefaultEdge>(
289                 DefaultEdge.class);
290         gen4.generateGraph(g2, new IntegerVertexFactory(1), null); // start vertex from number 2
291
292         Graph<Integer , DefaultEdge> g3 =
293             new DefaultDirectedGraph<Integer , DefaultEdge>(
294                 DefaultEdge.class);
295         gen4.generateGraph(g3, new IntegerVertexFactory(2), null); // start vertex from number 3
296
297         // first assert all are isomorphic (if vertexChecker is not used)
298 assertIsomorphic(new Graph [] {
299                 g1,
300                 g2
301             }, true);
302         assertIsomorphic(new Graph [] {
303                 g2,
304                 g3
305             }, true);
306         assertIsomorphic(new Graph [] {
307                 g1,
308                 g3
309             }, true);
310
311         // create a functor according to odd even
312 EquivalenceComparator vertexEqChecker = new OddEvenGroupComparator();
313         assertIsomorphic(new Graph [] {
314                 g1,
315                 g2
316             },
317             false,
318             vertexEqChecker,
319             null);
320         assertIsomorphic(new Graph [] {
321                 g2,
322                 g3
323             },
324             false,
325             vertexEqChecker,
326             null);
327         assertIsomorphic(new Graph [] {
328                 g1,
329                 g3
330             }, true, vertexEqChecker, null);
331     }
332
333     /**
334      * Passes an EdgeComparator, which compares according to odd-even edge
335      * weight. The generated graphs are: A-(12)->B-(10)->C-(5)->D
336      * A-(10)->B-(18)->C-(3)->D A-(11)->B-(10)->C-(5)->D (the first here is odd)
337      *
338      * @author Assaf
339      * @since Aug 12, 2005
340      */
341     @SuppressWarnings ("unchecked")
342     public void testEdgeComparator()
343     {
344         int LINEAR_GRAPH_VERTEX_NUM = 4;
345         Graph [] graphsArray = new DirectedGraph [3];
346         Character [] charArray =
347             new Character [] {
348                 new Character ('A'),
349                 new Character ('B'),
350                 new Character ('C'),
351                 new Character ('D')
352             };
353         int [][] weigthsArray =
354             new int [][] {
355                 {
356                     12,
357                     10,
358                     5
359                 },
360                 {
361                     10,
362                     18,
363                     3
364                 },
365                 {
366                     11,
367                     10,
368                     5
369                 }
370             };
371
372         for (int i = 0; i < graphsArray.length; i++) {
373             Graph<Character , DefaultEdge> currGraph =
374                 graphsArray[i] =
375                     new DefaultDirectedWeightedGraph<Character , DefaultWeightedEdge>(
376                         DefaultWeightedEdge.class);
377             for (int j = 0; j < LINEAR_GRAPH_VERTEX_NUM; j++) {
378                 currGraph.addVertex(charArray[j]);
379             }
380
381             // create the 3 edges with weights
382 for (int j = 0; j < 3; j++) {
383                 Graphs.addEdge(
384                     currGraph,
385                     charArray[j],
386                     charArray[j + 1],
387                     weigthsArray[i][j]);
388             }
389         }
390
391         // first assert all are isomorphic (if vertexChecker is not used)
392 assertIsomorphic(new Graph [] {
393                 graphsArray[0],
394                 graphsArray[1]
395             },
396             true);
397         assertIsomorphic(new Graph [] {
398                 graphsArray[0],
399                 graphsArray[2]
400             },
401             true);
402         assertIsomorphic(new Graph [] {
403                 graphsArray[1],
404                 graphsArray[2]
405             },
406             true);
407
408         // create a functor according to odd even
409 EquivalenceComparator edgeEqChecker =
410             new DirectedEdgeWeightOddEvenComparator(graphsArray[0]);
411         assertIsomorphic(
412             new Graph [] {
413                 graphsArray[0],
414                 graphsArray[1]
415             },
416             true,
417             null,
418             edgeEqChecker);
419         assertIsomorphic(
420             new Graph [] {
421                 graphsArray[0],
422                 graphsArray[2]
423             },
424             false,
425             null,
426             edgeEqChecker);
427         assertIsomorphic(
428             new Graph [] {
429                 graphsArray[1],
430                 graphsArray[2]
431             },
432             false,
433             null,
434             edgeEqChecker);
435     }
436
437     @SuppressWarnings ("unchecked")
438     private void assertIsomorphicStopAfterFirstMatch(
439         Graph [] graphs,
440         boolean assertActive,
441         boolean shouldTheyBeIsomorphic,
442         EquivalenceComparator vertexChecker,
443         EquivalenceComparator edgeChecker)
444     {
445         if (assertActive) {
446             System.out.println("\nassertIsomorphic:"
447                 + shouldTheyBeIsomorphic);
448         }
449         Graph g1 = graphs[0];
450         Graph g2 = graphs[1];
451         System.out.println("g1:" + g1);
452         System.out.println("g2:" + g2);
453         long beforeTime = System.currentTimeMillis();
454         GraphIsomorphismInspector iso =
455             AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(
456                 g1,
457                 g2,
458                 vertexChecker,
459                 edgeChecker);
460         boolean isoResult = iso.isIsomorphic();
461         if (isoResult) {
462             System.out.println("Graphs are isomorphic. ");
463         } else {
464             System.out.println("Graphs are NOT isomorphic.");
465         }
466
467         long deltaTime = System.currentTimeMillis() - beforeTime;
468         String timeDesc;
469         timeDesc =
470             (deltaTime <= 10) ? "<10ms [less than minumun measurement time]"
471             : String.valueOf(deltaTime);
472         System.out.println(
473             "# Performence: Isomorphism check in MiliSeconds:" + timeDesc);
474         if (assertActive) {
475             assertEquals(shouldTheyBeIsomorphic, isoResult);
476         }
477     }
478
479     /**
480      * Performance test with different number of vertex, edges. For each number
481      * pair, 3 graphs are generated. The first two, using the same generator,
482      * the third using a different generator. Note: the 1st and 2nd must be
483      * isomorphic. The 3rd will most likely not be isomorphic , but on special
484      * occasaions may be, so do not assert it. (example: empty graph, full mesh
485      * , rare case that they are not real random). NOTE: RENAME TO testXXX to
486      * make it work. It shows output and not assertions, so it cannot be used by
487      * automatic tests.
488      */
489     @SuppressWarnings ("unchecked")
490     public void performanceTestOnRandomGraphs()
491         throws Exception
492     {
493         final int [] numOfVertexesArray =
494             new int [] {
495                 6,
496                 6,
497                 6,
498                 8,
499                 8,
500                 8,
501                 10,
502                 10,
503                 10,
504                 12,
505                 14,
506                 20,
507                 30,
508                 99
509             };
510         final int [] numOfEdgesArray =
511             new int [] {
512                 0,
513                 4,
514                 12,
515                 1,
516                 15,
517                 54,
518                 0,
519                 40,
520                 90,
521                 130,
522                 50,
523                 79,
524                 30,
525                 234
526             };
527
528         // there will be two different generators. The first will be used for
529 // 1st,2nd graph
530 // the other for the3rd graph
531 final int NUM_OF_GENERATORS = 2;
532         RandomGraphGenerator [] genArray =
533             new RandomGraphGenerator [NUM_OF_GENERATORS];
534
535         String [] graphConctereClassesFullName =
536             new String [] { // "org.jgrapht.graph.SimpleGraph" ,
537 "org.jgrapht.graph.SimpleDirectedGraph",
538                 "org.jgrapht.graph.DefaultDirectedGraph",
539                 // "org.jgrapht.graph.Multigraph",
540 // "org.jgrapht.graph.Pseudograph"
541 };
542
543         // 3 graphs. 1st,2nd must be isomorphic .3rd probably not iso.
544 final int SIZE_OF_GENERATED_GRAPH_ARRAY = 3;
545
546         // graphsArray rows are different graph types. Columns are few
547 // instances of that type
548 Graph [][] graphsArray =
549             new Graph [graphConctereClassesFullName.length][SIZE_OF_GENERATED_GRAPH_ARRAY];
550
551         Graph [] currIsoTestArray = new Graph [2];
552         for (int testNum = 0; testNum < numOfVertexesArray.length; testNum++) {
553             // recreate the graphs (empty)
554 try {
555                 for (int i = 0; i < graphConctereClassesFullName.length; i++) {
556                     for (int j = 0; j < SIZE_OF_GENERATED_GRAPH_ARRAY; j++) {
557                         graphsArray[i][j] =
558                             (Graph) Class.forName(
559                                 graphConctereClassesFullName[i]).newInstance();
560                     }
561                 }
562             } catch (Exception e) {
563                 throw new Exception ("failed to initilized the graphs", e);
564             }
565
566             // create generators for the new vertex/edges number
567 for (int i = 0; i < genArray.length; i++) {
568                 genArray[i] =
569                     new RandomGraphGenerator(
570                         numOfVertexesArray[testNum],
571                         numOfEdgesArray[testNum]);
572             }
573
574             for (
575                 int graphType = 0;
576                 graphType < graphConctereClassesFullName.length;
577                 graphType++) {
578                 System.out.println(
579                     "### numOfVertexes= " + numOfVertexesArray[testNum]);
580                 System.out.println(
581                     "### numOfEdges= " + numOfEdgesArray[testNum]);
582                 System.out.println(
583                     "######### Graph Type:"
584                     + graphConctereClassesFullName[graphType]);
585                 System.out.println(
586                     "# # # # # # # # # # # # # # # # # # # # # # # # # # # #");
587
588                 // 1st and 2nd from genArray[0]
589 genArray[0].generateGraph(
590                     graphsArray[graphType][0],
591                     new IntegerVertexFactory(),
592                     null);
593                 genArray[0].generateGraph(
594                     graphsArray[graphType][1],
595                     new IntegerVertexFactory(),
596                     null);
597
598                 // 3rd from genArray[1]
599 genArray[1].generateGraph(
600                     graphsArray[graphType][2],
601                     new IntegerVertexFactory(),
602                     null);
603
604                 // now start testing
605 currIsoTestArray[0] = graphsArray[graphType][0];
606                 currIsoTestArray[1] = graphsArray[graphType][1];
607
608                 assertIsomorphicStopAfterFirstMatch(
609                     currIsoTestArray,
610                     true,
611                     true,
612                     null,
613                     null);
614
615                 // remember it is not a MUST - it can be true . DEGUG REASON
616 // ONLY , and with care
617 currIsoTestArray[1] = graphsArray[graphType][2];
618                 assertIsomorphicStopAfterFirstMatch(
619                     currIsoTestArray,
620                     false,
621                     false,
622                     null,
623                     null);
624             }
625         }
626     }
627 }
628

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags