org.jgrapht.alg.vertexcover.util

Class RatioVertex<V>

java.lang.Object

org.jgrapht.alg.vertexcover.util.RatioVertex<V>

Type Parameters:

V - the graph vertex type

All Implemented Interfaces:

Comparable<RatioVertex<V>>

public class RatioVertex<V>
extends Object
implements Comparable<RatioVertex<V>>

Helper class for vertex covers. Guarantees that vertices can be sorted, thereby obtaining a unique ordering.

Author:

Joris Kinable

Field Summary

Fields

Modifier and Type	Field and Description
protected int	degree degree of this vertex
int	ID unique id, used to guarantee that compareTo never returns 0
Map<RatioVertex<V>,Integer>	neighbors Map of neighbors, and a count of the number of edges to this neighbor
V	v original vertex
double	weight weight of the vertex

Constructor Summary

Constructors

Constructor and Description
RatioVertex(int ID, V v, double weight) Create a new ratio vertex

Method Summary

Modifier and Type	Method and Description
void	addNeighbor(RatioVertex<V> v) Add a neighbor.
int	compareTo(RatioVertex<V> other)
boolean	equals(Object o)
int	getDegree() Returns the degree of the vertex
double	getRatio() Returns the ratio between the vertex' weight and its degree
int	hashCode()
void	removeNeighbor(RatioVertex<V> v) Remove a neighbor.
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

v

public final V v

original vertex

weight

public double weight

weight of the vertex

ID

public final int ID

unique id, used to guarantee that compareTo never returns 0

degree

protected int degree

degree of this vertex

neighbors

public final Map<RatioVertex<V>,Integer> neighbors

Map of neighbors, and a count of the number of edges to this neighbor

Constructor Detail

RatioVertex

public RatioVertex(int ID,
                   V v,
                   double weight)

Create a new ratio vertex

Parameters:

ID - unique id

v - the vertex

weight - the vertex weight

Method Detail

addNeighbor

public void addNeighbor(RatioVertex<V> v)

Add a neighbor.

Parameters:

v - the neighbor

removeNeighbor

public void removeNeighbor(RatioVertex<V> v)

Remove a neighbor.

Parameters:

v - the neighbor to remove

getDegree

public int getDegree()

Returns the degree of the vertex

Returns:

degree of the vertex

getRatio

public double getRatio()

Returns the ratio between the vertex' weight and its degree

Returns:

the ratio between the vertex' weight and its degree

compareTo

public int compareTo(RatioVertex<V> other)

Specified by:

compareTo in interface Comparable<RatioVertex<V>>

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object

toString

public String toString()

Overrides:

toString in class Object