KickJava   Java API By Example, From Geeks To Geeks.

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


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  * GraphIsomorphismInspector.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: GraphIsomorphismInspector.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
43 /**
44  * <b>Isomorphism Overview</b>
45  *
46  * <p>Isomorphism is the problem of testing whether two graphs are topologically
47  * the same. Suppose we are given a collection of graphs and must perform some
48  * operation on each of them. If we can identify which of the graphs are
49  * duplicates, they can be discarded so as to avoid redundant work.
50  *
51  * <p>In Formal Math: <i>Input description:</i> Two graphs, G and H. <i>Problem
52  * description:</i> Find a (or all) mappings f of the vertices of G to the
53  * vertices of H such that G and H are identical; i.e. (x,y) is an edge of G iff
54  * (f(x),f(y)) is an edge of H. <a
55  * HREF="http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE180.HTM">
56  * http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE180.HTM</a>.
57  *
58  * <p><i>Efficiency:</i> The general algorithm is not polynomial, however
59  * polynomial algorithms are known for special cases, like acyclic graphs,
60  * planar graphs etc. There are several heuristic algorithms which gives quite
61  * good results (polynomial) in general graphs, for most but not all cases.
62  *
63  * <p><b>Usage:</b>
64  *
65  * <ol>
66  * <li>Choose comparators for the vertexes and edges. You may use the default
67  * comparator by sending null parameters for them to the constructor. Example:
68  * Assume Your graphs are of human relations. Each vertex is either a man or a
69  * woman and also has the person name. You may decide that isomorphism is
70  * checked according to gender, but not according to the specific name. So you
71  * will create a comparator that distinguishes vertexes only according to
72  * gender.
73  * <li>Use the isIsomorphic() method as a boolean test for isomorphism
74  * <li>Use the Iterator interface to iterate through all the possible
75  * isomorphism ordering.
76  * </ol>
77  *
78  * @author Assaf Lehr
79  * @since Jul 15, 2005
80  */
81 // REVIEW jvs 5-Sept-2005: Since we're using JDK1.5 now, we should be
82 // able to declare this as Iterator<GraphMapping>, correct? Otherwise
83 // the caller doesn't even know what they're getting back.
84 public interface GraphIsomorphismInspector<E>
85     extends Iterator<E>
86 {
87
88     //~ Methods ---------------------------------------------------------------
89
90     /**
91      * @return <code>true</code> iff the two graphs are isomorphic
92      */
93     public boolean isIsomorphic();
94 }
95
Popular Tags