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

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

All Implemented Interfaces:

Graph, java.io.Serializable

public class GraphImpl
extends java.lang.Object
implements Graph

See Also:

Serialized Form

Field Summary

Fields inherited from interface edu.ucsb.cs.jicos.applications.utilities.graph.Graph

METRIC_EUC_2D, METRIC_GEO

Constructor Summary

GraphImpl(int[][] costs)
Constructs the graph according to the argument cost matrix.

GraphImpl(int nodes, int seed, int maxEdgeWeight)
Constructs a random graph, using seed as the seed for the random number generator.

Method Summary

java.lang.String	costs2String()
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[]	getMinCostMaxMatch() Get the minimum cost maximum matching in the graph.
int	size() Get the number of nodes in the graph.
java.lang.String	toString() A string representation of the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphImpl

public GraphImpl(int nodes,
                 int seed,
                 int maxEdgeWeight)

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.

maxEdgeWeight - The maximum edge weight: edge weights are in the interval [0, maxEdgeWeight).

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

GraphImpl

public GraphImpl(int[][] costs)

Constructs the graph according to the argument cost matrix.

Parameters:

costs - The cost matrix that is used to construct this graph.

Method Detail

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.

toString

public java.lang.String toString()

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.