All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class CH.rubin.matching.Graph2DM

java.lang.Object
   |
   +----CH.rubin.matching.Graph2DM

public class Graph2DM
extends Object
Contains a two dimensional matching graph

Version:
$Revision: 2.4 $
Author:
Patrick Feisthammel email: pafei@rubin.ch

Constructor Index

 o Graph2DM(int)
Constructs an empty bipartite graph.
 o Graph2DM(int[])
Constructs a bipartite matching graph.

Method Index

 o canEdgeXYBeSet(int, int)
Checks if the given edge can be set or not.
 o equals(Graph2DM)
compares two Graph2DM and gives true if they represent the same graph.
 o existsEdgeXY(int, int)
Test if the edge between x and y exists.
 o hashCode()
a hashCode of the graph; actually the hashcode of IntArray is used.
 o insertEdgeXY(int, int)
Insert an edge between the points x and y.
 o points()
returns the points per dimension in this graph.
 o removeEdgeXY(int, int)
Remove the edge between the points x and y.
 o toString()
gives the String representing the graph
 o xPoint(int)
Returns the point in dimension x which is connected to the point y.
 o yPoint(int)
Returns the point in dimension y which is connected to the point x.
 o yPointList()
Returns the y points in the order x1, x2, ...

Constructors

 o Graph2DM
 public Graph2DM(int pointList[])
Constructs a bipartite matching graph. In pointList[i] there must be the point in dimension Y which is connected to the point i of the dimension X. ( 0 <= i < pointList.length ) If point i is not connected to any other point, -1 must be given The points are numbered starting with 0.

 o Graph2DM
 public Graph2DM(int points)
Constructs an empty bipartite graph. In points there must be the number of points of the graph. new Graph2DM(5) will generate a graph with 5 points in the X dimension and 5 points in the Y dimension.

Parameters:
points - the number of points per dimension for the bipartite graph
See Also:
points

Methods

 o points
 public int points()
returns the points per dimension in this graph.

 o yPointList
 public int[] yPointList()
Returns the y points in the order x1, x2, ...
(2, 1, 3) stands for a graph 1->2, 2->1, 3->3.

Time to execute ist linear to points(). The asked array of points is already present, so it is just a return array statement.

Returns:
int[] with the y points of the graph. Not connected points are set to -1. The list has the length points().
See Also:
points
 o existsEdgeXY
 public boolean existsEdgeXY(int x,
                             int y)
Test if the edge between x and y exists.

Parameters:
x - point in the X dimension, 0 <= x <= points()
y - point in the Y dimension, 0 <= y <= points()
See Also:
points
 o canEdgeXYBeSet
 public boolean canEdgeXYBeSet(int x,
                               int y)
Checks if the given edge can be set or not. It can only be set if both points at the end are not yet connected.

Parameters:
x - point in the X dimension, 0 <= x <= points()
y - point in the Y dimension, 0 <= y <= points()
See Also:
points
 o insertEdgeXY
 public void insertEdgeXY(int x,
                          int y)
Insert an edge between the points x and y. Because it is a 2DM graph, only unconnected points may be connected. (Inserting an already existing edge is ok)

Parameters:
x - point in the X dimension, 0 <= x <= points()
y - point in the Y dimension, 0 <= y <= points()
See Also:
points
 o removeEdgeXY
 public void removeEdgeXY(int x,
                          int y)
Remove the edge between the points x and y.

Parameters:
x - point in the X dimension, 0 <= x <= points()
y - point in the Y dimension, 0 <= y <= points()
See Also:
points
 o yPoint
 public int yPoint(int x)
Returns the point in dimension y which is connected to the point x. If no point is connected to x, -1 is returned

Parameters:
x - point in dimension x, 0 <= x <= points()
See Also:
points
 o xPoint
 public int xPoint(int y)
Returns the point in dimension x which is connected to the point y. If no point is connected to y, -1 is returned

Parameters:
y - point in dimension y, 0 <= y <= points()
See Also:
points
 o hashCode
 public int hashCode()
a hashCode of the graph; actually the hashcode of IntArray is used.

Overrides:
hashCode in class Object
See Also:
equals
 o equals
 public boolean equals(Graph2DM object)
compares two Graph2DM and gives true if they represent the same graph. They are equal if all edges are the same, including the numbering. So the graph 0->0 1->1 and 0->1 1->0 are not equal.

See Also:
equals, equals
 o toString
 public String toString()
gives the String representing the graph

Overrides:
toString in class Object

All Packages  Class Hierarchy  This Package  Previous  Next  Index