KickJava   Java API By Example, From Geeks To Geeks.

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


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  * IsomorphismRelation.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: IsomorphismRelation.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 org.jgrapht.*;
43 import org.jgrapht.graph.*;
44
45
46 /**
47  * Holds an isomorphism relation for two graphs. It contains a mapping between
48  * the two graphs.
49  *
50  * <p>Usage:
51  *
52  * <ol>
53  * <li>use <code>getVertexCorrespondence()</code> or <code>
54  * getEdgeCorrespondence()</code> to get the mapped object in the other graph.
55  * </ol>
56  *
57  * <p>
58  * <p>It consists of two vertexes array , the i-th vertex in the 1st array is
59  * the isomorphic eqv. of the i-th in 2nd array. Note that the getters are
60  * unsafe (they return the array and not a copy of it).
61  *
62  * @author Assaf
63  * @since May 27, 2005
64  */
65 public class IsomorphismRelation<V, E>
66     implements GraphMapping<V, E>
67 {
68
69     //~ Instance fields -------------------------------------------------------
70
71     private List<V> vertexList1;
72     private List<V> vertexList2;
73
74     private GraphMapping<V, E> graphMapping = null;
75
76     private Graph<V, E> graph1;
77     private Graph<V, E> graph2;
78
79     //~ Constructors ----------------------------------------------------------
80
81     /**
82      */
83     public IsomorphismRelation(
84         List<V> aGraph1vertexArray,
85         List<V> aGraph2vertexArray,
86         Graph<V, E> g1,
87         Graph<V, E> g2)
88     {
89         this.vertexList1 = aGraph1vertexArray;
90         this.vertexList2 = aGraph2vertexArray;
91         this.graph1 = g1;
92         this.graph2 = g2;
93     }
94
95     //~ Methods ---------------------------------------------------------------
96
97     public String JavaDoc toString()
98     {
99         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
100         sb.append("vertexList1: ").append(
101             this.vertexList1.toString());
102         sb.append("\tvertexList2: ").append(
103             this.vertexList2.toString());
104         return sb.toString();
105     }
106
107     public V getVertexCorrespondence(V vertex, boolean forward)
108     {
109         // lazy initializer for graphMapping
110 if (graphMapping == null) {
111             initGraphMapping();
112         }
113
114         return graphMapping.getVertexCorrespondence(vertex, forward);
115     }
116
117     public E getEdgeCorrespondence(E edge, boolean forward)
118     {
119         // lazy initializer for graphMapping
120 if (graphMapping == null) {
121             initGraphMapping();
122         }
123
124         return graphMapping.getEdgeCorrespondence(edge, forward);
125     }
126
127     /**
128      * We currently have the vertexes array. From them we will construct two
129      * maps: g1ToG2 and g2ToG1, using the array elements with the same index.
130      */
131     private void initGraphMapping()
132     {
133         int mapSize = vertexList1.size();
134         Map<V, V> g1ToG2 = new HashMap<V, V>(mapSize);
135         Map<V, V> g2ToG1 = new HashMap<V, V>(mapSize);
136
137         for (int i = 0; i < mapSize; i++) {
138             V source = this.vertexList1.get(i);
139             V target = this.vertexList2.get(i);
140             g1ToG2.put(source, target);
141             g2ToG1.put(target, source);
142         }
143         this.graphMapping =
144             new DefaultGraphMapping<V, E>(
145                 g1ToG2,
146                 g2ToG1,
147                 this.graph1,
148                 this.graph2);
149     }
150 }
151
Popular Tags