/*
* (C) Copyright 2003-2017, by Linda Buisman and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.util;
import java.util.*;
import org.jgrapht.*;
/**
* Compares two vertices based on their degree.
*
*
* Used by greedy algorithms that need to sort vertices by their degree. Two vertices are considered
* equal if their degrees are equal.
*
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Linda Buisman
* @since Nov 6, 2003
*/
public class VertexDegreeComparator
implements Comparator
{
/**
* Order in which we sort the vertices: ascending vertex degree or descending vertex degree
*/
public enum Order
{
ASCENDING,
DESCENDING
};
/**
* The graph that contains the vertices to be compared.
*/
private UndirectedGraph graph;
/**
* Order in which the vertices are sorted: ascending or descending
*/
private Order order;
/**
* Creates a comparator for comparing the degrees of vertices in the specified graph. The
* comparator compares in ascending order of degrees (lowest first).
*
* @param g graph with respect to which the degree is calculated.
*/
public VertexDegreeComparator(UndirectedGraph g)
{
this(g, Order.ASCENDING);
}
/**
* Creates a comparator for comparing the degrees of vertices in the specified graph.
*
* @param g graph with respect to which the degree is calculated.
* @param order order in which the vertices are sorted (ascending or descending)
*/
public VertexDegreeComparator(UndirectedGraph g, Order order)
{
graph = g;
this.order = order;
}
/**
* Compare the degrees of v1 and v2, taking into account whether
* ascending or descending order is used.
*
* @param v1 the first vertex to be compared.
* @param v2 the second vertex to be compared.
*
* @return -1 if v1 comes before v2, +1 if
* v1 comes after v2, 0 if equal.
*/
@Override
public int compare(V v1, V v2)
{
int comparison = Integer.compare(graph.degreeOf(v1), graph.degreeOf(v2));
if (order == Order.ASCENDING)
return comparison;
else
return -1 * comparison;
}
}
// End VertexDegreeComparator.java
Ads help maintain this website.