KickJava   Java API By Example, From Geeks To Geeks.

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


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  * VertexDegreeEquivalenceComparator.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: VertexDegreeEquivalenceComparator.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
44
45 /**
46  * Two vertexes are equivalent under this comparator if and only if:
47  *
48  * <ol>
49  * <li>they have the same IN degree
50  *
51  * <p>AND
52  * <li>they have the same OUT degree
53  * </ol>
54  *
55  * @author Assaf
56  * @since Jul 21, 2005
57  */
58 public class VertexDegreeEquivalenceComparator<V, E>
59     implements EquivalenceComparator<V, Graph<V, E>>
60 {
61
62     //~ Constructors ----------------------------------------------------------
63
64     /**
65      */
66     public VertexDegreeEquivalenceComparator()
67     {
68     }
69
70     //~ Methods ---------------------------------------------------------------
71
72     /**
73      * Compares the in degrees and the out degrees of the two vertexes.
74      *
75      * <p>One may reside in an Undirected Graph and the other in a Directed
76      * graph, or both on the same graph type.
77      *
78      * @see EquivalenceComparator#equivalenceCompare(Object, Object, Object,
79      * Object)
80      */
81     public boolean equivalenceCompare(
82         V vertex1,
83         V vertex2,
84         Graph<V, E> context1,
85         Graph<V, E> context2)
86     {
87         // note that VertexDegreeComparator cannot be used. It supports only
88 // directed graphs.
89 InOutDegrees inOut1 = getInOutDegrees(context1, vertex1);
90         InOutDegrees inOut2 = getInOutDegrees(context2, vertex2);
91         boolean result = inOut1.equals(inOut2);
92         return result;
93     }
94
95     /**
96      * Hashes using the in & out degree of a vertex
97      *
98      * @see EquivalenceComparator#equivalenceHashcode(Object, Object)
99      */
100     public int equivalenceHashcode(V vertex, Graph<V, E> context)
101     {
102         InOutDegrees inOut = getInOutDegrees(context, vertex);
103
104         // hash it using the string hash. use the format N '-' N
105 StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
106         sb.append(String.valueOf(inOut.inDegree));
107         sb.append("-"); // to diffrentiate inner and outer
108 sb.append(String.valueOf(inOut.outDegree));
109         return sb.toString().hashCode();
110     }
111
112     /**
113      * Calculates the In and Out degrees of vertexes. Supported graph types:
114      * UnDirectedGraph, DirectedGraph. In UnDirected graph, the in = out (as if
115      * it was undirected and every edge is both an in and out edge)
116      *
117      * @param aContextGraph
118      * @param vertex
119      */
120     protected InOutDegrees getInOutDegrees(
121         Graph<V, E> aContextGraph,
122         V vertex)
123     {
124         int inVertexDegree = 0;
125         int outVertexDegree = 0;
126         if (aContextGraph instanceof UndirectedGraph) {
127             UndirectedGraph<V, E> undirectedGraph =
128                 (UndirectedGraph<V, E>) aContextGraph;
129             inVertexDegree = undirectedGraph.degreeOf(vertex);
130             outVertexDegree = inVertexDegree; // it is UNdirected
131 } else if (aContextGraph instanceof DirectedGraph) {
132             DirectedGraph<V, E> directedGraph =
133                 (DirectedGraph<V, E>) aContextGraph;
134             inVertexDegree = directedGraph.inDegreeOf(vertex);
135             outVertexDegree = directedGraph.outDegreeOf(vertex);
136         } else {
137             throw new RuntimeException JavaDoc(
138                 "contextGraph is of unsupported type . It must be one of these two :"
139                 + " UndirectedGraph or DirectedGraph");
140         }
141         return new InOutDegrees(inVertexDegree, outVertexDegree);
142     }
143
144     //~ Inner Classes ---------------------------------------------------------
145
146     /**
147      * Simple structure used to hold the two ints: vertex in degree and vertex
148      * out degree. Useful as returned value for methods which calculate both at
149      * the same time.
150      *
151      * @author Assaf
152      * @since Jul 21, 2005
153      */
154     protected class InOutDegrees
155     {
156         public int inDegree;
157         public int outDegree;
158
159         public InOutDegrees(int aInDegree, int aOutDegree)
160         {
161             this.inDegree = aInDegree;
162             this.outDegree = aOutDegree;
163         }
164
165         /**
166          * Checks both inDegree and outDegree. Does not check class type to save
167          * time. If should be used with caution.
168          *
169          * @see java.lang.Object#equals(java.lang.Object)
170          */
171         public boolean equals(Object JavaDoc obj)
172         {
173             InOutDegrees other = (InOutDegrees) obj;
174             return
175                 ((this.inDegree == other.inDegree)
176                     && (this.outDegree == other.outDegree));
177         }
178     }
179 }
180
Popular Tags