edu.ucsb.cs.jicos.applications.utilities.graph
Class GraphEuclidean

java.lang.Object
  edu.ucsb.cs.jicos.applications.utilities.graph.GraphEuclidean

All Implemented Interfaces:

Graph, java.io.Serializable

public final class GraphEuclidean
extends java.lang.Object
implements Graph

See Also:

Serialized Form

Field Summary

static int	METRIC_EUC_2D
static int	METRIC_GEO

Constructor Summary

GraphEuclidean(int $nodes, int seed, int magnification)
Constructs a random graph, using seed as the seed for the random number generator.

GraphEuclidean(int $nodes, int metric, java.lang.String name, java.lang.String description)

Method Summary

java.lang.String	costs2String()
void	drawCappello2Approximation(java.awt.Graphics g, int x, int y, int extent)
void	drawMatching(java.awt.Graphics g, int x, int y, int extent) Draw a minimum cost maximum matching of this graph.
void	drawTour(java.awt.Graphics g, int x, int y, int extent)
void	drawVertices(java.awt.Graphics g, int x, int y, int extent) Draw the vertices in a square of extent X extent pixels, starting at pixel offset (x, y) on Graphics g.
java.lang.String	getComment()
int	getCost(int i, int j) Return the distance between nodes whose node numbers are the arguments.
int[][]	getCosts() Returns a symmetric cost matrix.
int[]	getMaxCostMaxMatch() Get the maximum cost maximum matching in the graph.
int	getMetric()
int[]	getMinCostMaxMatch() Get the minimum cost maximum matching in the graph.
java.lang.String	getName()
int[]	getTour(int[] tour)
static void	main(java.lang.String[] args)
void	setComment(java.lang.String value)
void	setMetric(int value)
void	setName(java.lang.String value)
void	setTour(int[] tour)
void	setVertex(int index, edu.ucsb.cs.jicos.applications.utilities.graph.Vertex vert)
int	size() Get the number of nodes in the graph.
java.lang.String	toString() Get a string representation of the graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

METRIC_GEO

public static final int METRIC_GEO

See Also:

Constant Field Values

METRIC_EUC_2D

public static final int METRIC_EUC_2D

See Also:

Constant Field Values

Constructor Detail

GraphEuclidean

public GraphEuclidean(int $nodes,
                      int seed,
                      int magnification)

Constructs a random graph, using seed as the seed for the random number generator. The graph has n vertices in the unit square, which are magnified by magnification. For example, if the x coordinate of a vertex is 0.76543 and the magnification is 1000, then the magnified x coordinate is 765 and the unit square maps to a 1000 X 1000 int grid.

Parameters:

$nodes - Number of nodes in the graph.

seed - The seed to use for the random number generator.

magnification - The magnification factor. For example, if the x coordinate of a vertex is 0.76543 and the magnification is 1000, then the magnified x coordinate is 765 and the unit square maps to a 1000 X 1000 int grid.

GraphEuclidean

public GraphEuclidean(int $nodes,
                      int metric,
                      java.lang.String name,
                      java.lang.String description)

Method Detail

setVertex

public void setVertex(int index,
                      edu.ucsb.cs.jicos.applications.utilities.graph.Vertex vert)

setMetric

public void setMetric(int value)

getMetric

public int getMetric()

setName

public void setName(java.lang.String value)

getName

public java.lang.String getName()

setComment

public void setComment(java.lang.String value)

getComment

public java.lang.String getComment()

costs2String

public java.lang.String costs2String()

Specified by:

costs2String in interface Graph

getCost

public int getCost(int i,
                   int j)

Return the distance between nodes whose node numbers are the arguments.

Specified by:

getCost in interface Graph

Parameters:

i - the 1st node number.

j - the other node number.

Returns:

The Euclidean distance between these nodes.

getCosts

public int[][] getCosts()

Returns a symmetric cost matrix. Entry [i,j] is the distance between node i and node j.

Specified by:

getCosts in interface Graph

Returns:

Returns a symmetric cost matrix. Entry [i,j] is the distance between node i and node j.

getMinCostMaxMatch

public int[] getMinCostMaxMatch()

Get the minimum cost maximum matching in the graph.

Specified by:

getMinCostMaxMatch in interface Graph

Returns:

Returns an array of matched nodes. The ith entry is the node number of the node that is matched to the node numbered i. Node numbers are 0, ..., n-1, where n is the number of nodes in the graph.

getMaxCostMaxMatch

public int[] getMaxCostMaxMatch()

Get the maximum cost maximum matching in the graph.

Specified by:

getMaxCostMaxMatch in interface Graph

Returns:

Returns an array of matched nodes. The ith entry is the node number of the node that is matched to the node numbered i.

size

public int size()

Get the number of nodes in the graph.

Specified by:

size in interface Graph

Returns:

the number of nodes in the graph.

drawMatching

public void drawMatching(java.awt.Graphics g,
                         int x,
                         int y,
                         int extent)

Draw a minimum cost maximum matching of this graph.

Parameters:

g - The Graphics object on which the drawing takes place.

x - The horizontal offset.

y - The vertical offset.

extent - The edge length, in pixels, of the square containing the drawing.

drawCappello2Approximation

public void drawCappello2Approximation(java.awt.Graphics g,
                                       int x,
                                       int y,
                                       int extent)

drawTour

public void drawTour(java.awt.Graphics g,
                     int x,
                     int y,
                     int extent)

drawVertices

public void drawVertices(java.awt.Graphics g,
                         int x,
                         int y,
                         int extent)

Draw the vertices in a square of extent X extent pixels, starting at pixel offset (x, y) on Graphics g.

Parameters:

g - The graphics object on which the drawing is to take place.

x - The horizontal offset in pixels.

y - The vertical offset in pixels.

extent - The edge length, in pixels, of a square region containing the set of nodes.

getTour

public int[] getTour(int[] tour)

setTour

public void setTour(int[] tour)

toString

public java.lang.String toString()

Description copied from interface: Graph

Get a string representation of the graph.

Specified by:

toString in interface Graph

Overrides:

toString in class java.lang.Object

Returns:

a string representation of the graph.

main

public static void main(java.lang.String[] args)