/*
* (C) Copyright 2016-2017, by Joris Kinable 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.vertexcover.util;
import java.util.*;
/**
* Helper class for vertex covers. Guarantees that vertices can be sorted, thereby obtaining a
* unique ordering.
*
* @param the graph vertex type
*
* @author Joris Kinable
*/
public class RatioVertex
implements Comparable>
{
/** original vertex **/
public final V v;
/** weight of the vertex **/
public double weight;
/** unique id, used to guarantee that compareTo never returns 0 **/
public final int ID;
/** degree of this vertex **/
protected int degree = 0;
/** Map of neighbors, and a count of the number of edges to this neighbor **/
public final Map, Integer> neighbors;
/**
* Create a new ratio vertex
*
* @param ID unique id
* @param v the vertex
* @param weight the vertex weight
*/
public RatioVertex(int ID, V v, double weight)
{
this.ID = ID;
this.v = v;
this.weight = weight;
neighbors = new LinkedHashMap<>();
}
/**
* Add a neighbor.
*
* @param v the neighbor
*/
public void addNeighbor(RatioVertex v)
{
if (!neighbors.containsKey(v))
neighbors.put(v, 1);
else
neighbors.put(v, neighbors.get(v) + 1);
degree++;
assert (neighbors.values().stream().mapToInt(Integer::intValue).sum() == degree);
}
/**
* Remove a neighbor.
*
* @param v the neighbor to remove
*/
public void removeNeighbor(RatioVertex v)
{
degree -= neighbors.get(v);
neighbors.remove(v);
}
/**
* Returns the degree of the vertex
*
* @return degree of the vertex
*/
public int getDegree()
{
return degree;
}
/**
* Returns the ratio between the vertex' weight and its degree
*
* @return the ratio between the vertex' weight and its degree
*/
public double getRatio()
{
return weight / degree;
}
@Override
public int compareTo(RatioVertex other)
{
if (this.ID == other.ID) // Same vertex
return 0;
int result = Double.compare(this.getRatio(), other.getRatio());
if (result == 0) // If vertices have the same value, resolve tie by an ID comparison
return Integer.compare(this.ID, other.ID);
else
return result;
}
@Override
public int hashCode()
{
return ID;
}
@Override
public boolean equals(Object o)
{
if (this == o)
return true;
else if (!(o instanceof RatioVertex))
return false;
RatioVertex other = (RatioVertex) o;
return this.ID == other.ID;
}
@Override
public String toString()
{
return "v" + ID + "(" + degree + ")";
}
}
Ads help maintain this website.