edu.uci.ics.dillenco.graphalg
Class Matching

java.lang.Object
  edu.uci.ics.dillenco.graphalg.Matching

public class Matching
extends Object

Field Summary

(package private) LinkedList<Node>

nodeQueue

Constructor Summary

Matching(Graph graph)
Construct a matching for the given graph.

Method Summary

int	getSize() Returns the size of the matching.
boolean	isAlmostPerfect() Return true if this matching is almost perfect.
boolean	isPerfect() Return true if this matching is perfect.
String	toString() Returns a string representation of the matching.

Methods inherited from class java.lang.Object

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

Field Detail

nodeQueue

LinkedList<Node> nodeQueue

Constructor Detail

Matching

public Matching(Graph graph)

Construct a matching for the given graph. For now, the only option available is a maximum-cardinality matching.

Parameters:

graph - the Graph for which the matching is to be constructed.

Method Detail

toString

public String toString()

Returns a string representation of the matching.

Overrides:

toString in class Object

Returns:

a string containing the vertex pairs in the matching.

getSize

public int getSize()

Returns the size of the matching.

Returns:

the number of edges in the matching.

isPerfect

public boolean isPerfect()

Return true if this matching is perfect.

Returns:

true if every vertex in the graph is matched.

isAlmostPerfect

public boolean isAlmostPerfect()

Return true if this matching is almost perfect.

Returns:

true if every vertex in the graph with at most one exception is matched.