KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > util > VertexDegreeComparator


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  * VertexDegreeComparator.java
27  * ---------------------------
28  * (C) Copyright 2003-2006, by Linda Buisman and Contributors.
29  *
30  * Original Author: Linda Buisman
31  * Contributor(s): Christian Hammer
32  *
33  * $Id: VertexDegreeComparator.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 06-Nov-2003 : Initial revision (LB);
38  * 07-Jun-2005 : Made generic (CH);
39  *
40  */
41 package org.jgrapht.alg.util;
42
43 import org.jgrapht.*;
44
45
46 /**
47  * Compares two vertices based on their degree.
48  *
49  * <p>Used by greedy algorithms that need to sort vertices by their degree. Two
50  * vertices are considered equal if their degrees are equal.</p>
51  *
52  * @author Linda Buisman
53  * @since Nov 6, 2003
54  */
55 public class VertexDegreeComparator<V, E>
56     implements java.util.Comparator JavaDoc<V>
57 {
58
59     //~ Instance fields -------------------------------------------------------
60
61     /**
62      * The graph that contains the vertices to be compared.
63      */
64     private UndirectedGraph<V, E> graph;
65
66     /**
67      * The sort order for vertex degree. <code>true</code> for ascending degree
68      * order (smaller degrees first), <code>false</code> for descending.
69      */
70     private boolean ascendingOrder;
71
72     //~ Constructors ----------------------------------------------------------
73
74     /**
75      * Creates a comparator for comparing the degrees of vertices in the
76      * specified graph. The comparator compares in ascending order of degrees
77      * (lowest first).
78      *
79      * @param g graph with respect to which the degree is calculated.
80      */
81     public VertexDegreeComparator(UndirectedGraph<V, E> g)
82     {
83         this(g, true);
84     }
85
86     /**
87      * Creates a comparator for comparing the degrees of vertices in the
88      * specified graph.
89      *
90      * @param g graph with respect to which the degree is calculated.
91      * @param ascendingOrder true - compares in ascending order of degrees
92      * (lowest first), false - compares in descending
93      * order of degrees (highest first).
94      */
95     public VertexDegreeComparator(
96         UndirectedGraph<V, E> g,
97         boolean ascendingOrder)
98     {
99         graph = g;
100         this.ascendingOrder = ascendingOrder;
101     }
102
103     //~ Methods ---------------------------------------------------------------
104
105     /**
106      * Compare the degrees of <code>v1</code> and <code>v2</code>, taking into
107      * account whether ascending or descending order is used.
108      *
109      * @param v1 the first vertex to be compared.
110      * @param v2 the second vertex to be compared.
111      *
112      * @return -1 if <code>v1</code> comes before <code>v2</code>, +1 if <code>
113      * v1</code> comes after <code>v2</code>, 0 if equal.
114      */
115     public int compare(V v1, V v2)
116     {
117         int degree1 = graph.degreeOf(v1);
118         int degree2 = graph.degreeOf(v2);
119
120         if (
121             ((degree1 < degree2) && ascendingOrder)
122             || ((degree1 > degree2) && !ascendingOrder)) {
123             return -1;
124         } else if (
125             ((degree1 > degree2) && ascendingOrder)
126             || ((degree1 < degree2) && !ascendingOrder)) {
127             return 1;
128         } else {
129             return 0;
130         }
131     }
132 }
133
Popular Tags