// FILE. . . . . d:/hak/hlt/src/hlt/math/matrix/sources/BipartiteGraph.java
// EDIT BY . . . Hassan Ait-Kaci
// ON MACHINE. . Hak-Laptop
// STARTED ON. . Fri Nov 22 14:01:20 2019
/**
* @version Last modified on Thu Dec 12 11:15:12 2019 by hak
* @author Hassan Aït-Kaci
* @copyright © by the author
*/
package hlt.math.matrix;
/**
* package hlt.math.matrix
* documentation listing
*/
import java.util.Iterator;
import hlt.language.util.ArrayList;
import hlt.language.util.IntArrayList;
import hlt.language.util.IntIterator;
/**
* This is a class representing a weighted bipartite graph with edges between
* two sets of nodes of equal cardinality: left nodes and right nodes. It is
* a subclass of Matrix, so using it can rely on its
* Matrix and Matrix structure where its nodes
* correspond to rows and columns and its edges correspond to non-zero
* entries in its data array. More precisely, a left node is a row
* and a right node is a column, and an edge exists between a left node and a
* right node iff the corresponding entry in the data array is non-zero at
* edge-creation time. Indeed, a BipartiteGraph is always
* generated from its defined data array component. Hence, at
* creation time, all its edges have a non-zero weight equal to the
* corresponding entry in the data array. After it is created, a
* BipartiteGraph's graph structure does not change, but the weights
* on its edges can change. After creation time, modifying such an edge's
* weight to any value (including zero) will modify the corresponding matrix
* entry in the data array, and conversely, modifying any matrix
* entry in the data array corresponding to an existing edge will
* modify the weight on the edge. N.B.: Since a
* BipartiteGraph's graph structure is immutable after it is
* created, setting an edge's weight to zero will not delete the edge. This
* is convenient for implementing many weight-based computation algorithms
* (e.g. finding a matching, an augmenting path, etc., ...).
*
*
*
*
* Contents (package hlt.math.matrix
* documentation listing)
*
*
*
* @see Matrix
* @see Matrix
*/
public class BipartiteGraph extends Matrix
{
/**
*
*/
/**
* Construct a BipartiteGraph with the given data
* array. This ensures that the data array is defined and square (violation
* of either condition causes a runtime exception to be thrown).
*/
public BipartiteGraph (double[][] data)
{
setData(data);
initializeGraphComponents();
}
/**
*
*
* In addition to the components it inherits form its Matrix superclass, a
* BipartiteGraph has one specific additional component which
* is a boolean[][] array. It also keeps handy information in
* node-indexed arrays.
*/
/**
* This is a square array of booleans having the same sign pattern
* as the data array at graph creation time. It serves as a mask on the
* data array of this BipartiteGraph to identify which
* entries in its data array are its edges. Hence, it is immutable
* once created.
*/
private boolean[][] isEdge;
/**
* This is an array of IntArrayLists containing the lists of
* successors of left nodes.
*/
private IntArrayList[] succLists;
/**
* This is an array of right node indices, each of which is the first
* successor of a left node, or -1 if a left node has no
* successor.
*/
private int[] firstSuccs;
/**
* This is an array of right node indices, each of which is the last
* successor of a left node, or -1 if a left node has no
* successor.
*/
private int[] lastSuccs;
/**
* This is an array of IntArrayLists containing the lists of
* predecessors of right nodes.
*/
private IntArrayList[] predLists;
/**
* This is an array of left node indices, each of which is the first
* predecessor of a right node, or -1 if a right node has no
* predecessor.
*/
private int[] firstPreds;
/**
* This is an array of left node indices, each of which is the last
* predecessor of a right node, or -1 if a right node has no
* predecessor.
*/
private int[] lastPreds;
/**
* Contains the number of successors of each left node.
*/
private int[] numOfSuccs;
/**
* Contains the number of predecessors of each right node.
*/
private int[] numOfPreds;
/**
*
*/
/**
*
*/
/**
* Return true iff there is an edge in this
* BipartiteGraph between left node and right
* node.
*/
public final boolean isEdge (int left, int right)
{
return isEdge[left][right];
}
/**
* Return true iff there is an edge in this
* BipartiteGraph between right node and left
* node.
*/
public final boolean isDualEdge (int right, int left)
{
return isEdge[left][right];
}
/**
* Return the number of successors of the given left node.
*/
public final int numOfSuccessors (int left)
{
return numOfSuccs[left];
}
/**
* Return the number of predecessors of the given right node.
*/
public final int numOfPredecessors (int right)
{
return numOfPreds[right];
}
/**
* Return the right node index of the first successor of the given
* left node, or -1 if it has no successor.
*/
public final int firstSuccessor (int left)
{
return firstSuccs[left];
}
/**
* Return the right node index of the last successor of the given
* left node, or -1 if it has no successor.
*/
public final int lastSuccessor (int left)
{
return lastSuccs[left];
}
/**
* Return the left node index of the first predecessor of the given
* right node, or -1 if it has no predecessor.
*/
public final int firstPredecessor (int right)
{
return firstPreds[right];
}
/**
* Return the left node index of the last predecessor of the given
* right node, or -1 if it has no predecessor.
*/
public final int lastPredecessor (int right)
{
return lastPreds[right];
}
/**
*
*/
/**
* Print this BipartiteGraph as a matrix to standard output
* printing each double entry formatted using the current floatFormatString() value.
*/
public void show ()
{
jot("\t"); // tab space over the row numbers
for (int col = 0; col < cols; col++)
jot(centerColumnHeader(headerString(col+1))); // column number (counted from 1)
ln(2);
for (int row = 0; row < rows; row++)
{
jot(headerString(row+1)+"\t"); // row number (counted from 1)
for (int col = 0; col < cols; col++)
if (isEdge(row,col))
System.out.printf(floatFormatString(),data[row][col]);
else
jot(noEdgeString());
ln();
}
}
/**
* Print this BipartiteGraph's components to standard output.
*/
public void showComponents ()
{
int order = rows;
sln("Showing the successors of each left node:");
for (int left = 0; left < order; left++)
say("\t"+(left+1)+": " + numOfSuccs[left]+" succs. = "+succSetString(left));
ln();
sln("Showing the predecessors of each right node:");
for (int right = 0; right < order; right++)
say("\t"+(right+1)+": " + numOfPreds[right]+" preds. = "+predSetString(right));
}
/**
* Returns a String form of the successor set of the given
* left node.
*/
public final String succSetString (int left)
{
StringBuilder buf = new StringBuilder();
buf.append('{');
for (IntIterator it = succsIterator(left); it.hasNext();)
{
buf.append(Integer.toString(it.next()+1));
if (it.hasNext())
buf.append(',');
}
return buf.append('}').toString();
}
/**
* Returns a String form of the predecessor set of the given
* right node.
*/
public final String predSetString (int right)
{
StringBuilder buf = new StringBuilder();
buf.append('{');
for (IntIterator it = predsIterator(right); it.hasNext();)
{
buf.append(Integer.toString(it.next()+1));
if (it.hasNext())
buf.append(',');
}
return buf.append('}').toString();
}
/**
*
*/
/**
* A bipartite graph B of order n is a triple
* (Lefts, Rights, Edges) where Lefts
* and Right are two distinct sets of nodes of equal size
* n, and Edges is a set of edges.
*
*
*
* A node is indexed by its position in {1,...,n} and is denoted
* by its index.
*
*
*
* An edge (left,right) ∈ {1,...,n} ×
* {1,...,n} of this bipartite graph is a pair of left/right node
* indices.
*
*
*
* A matching M of this bipartite graph is a set of pairs
* of left/right node indices (for us, an ArrayList of
* Edge objects) such that no two pairs share a node (i.e.,
* the degree of all nodes in M is either 0 or 1).
*
*
*
* A node of this bipartite graph will be said to be used by a
* matching M if it appears as the left or right node of an edge
* in M (i.e., if it has degree 1 in M).
*
*
*
* An alternating path of this bipartite graph with respect to a
* matching M is a set of pairs of left/right node indices (for
* us, an ArrayList of Edges) such that no pair share a
* node.
*
*
*
* A path of this bipartite graph is a sequence of such
* directed Edges starting at left node where the right
* node of an edge is the left node of the following
*
*
*
*
* Algorithm for finding a maximum bipartite-graph matching:
*
*
*
* - Start with empty matching M
*
*
*
*
*
*
*
*/
/**
*
*/
/**
* Return the right node that is the first successor of left node,
* or -1 if left has no successor.
*/
private int getFirstSucc (int left)
{
if (succLists[left].isEmpty())
return -1;
return succLists[left].firstElement();
}
/**
* Return the right node that is the last successor of left node,
* or -1 if left has no successor.
*/
private int getLastSucc (int left)
{
if (succLists[left].isEmpty())
return -1;
return succLists[left].lastElement();
}
/**
* Return the right node that is the first predecessor of right
* node, or -1 if right has no predecessor.
*/
private int getFirstPred (int right)
{
if (predLists[right].isEmpty())
return -1;
return predLists[right].firstElement();
}
/**
* Return the right node that is the last predecessor of right
* node, or -1 if right has no predecessor.
*/
private int getLastPred (int right)
{
if (predLists[right].isEmpty())
return -1;
return predLists[right].lastElement();
}
/**
* Initialize the isEdge array and successor/predecessor arrays of
* this BipartiteGraph at creation time, setting an entry to
* true iff the corresponding edge exists (i.e., iff the
* entry in the data array is non-zero at creation time).
*/
private final void initializeGraphComponents ()
{
int order = rows;
// create the isEdge array
isEdge = new boolean[order][order];
// create the arrays containing the numbers of successors/predecessors
// for each left/right node.
numOfSuccs = new int[order];
numOfPreds = new int[order];
// initialize isEdge, succLists, and numOfSuccs
succLists = new IntArrayList[order]; // an array of lists of successor indices
for (int left = 0; left < order; left++)
{
succLists[left] = new IntArrayList();
for (int right = 0; right < order; right++)
{
if (isEdge[left][right] = (data[left][right] != 0.0))
{
succLists[left].add(right);
numOfSuccs[left]++;
}
}
}
// System.err.println(">>> Succ Lists:");
// for (int left = 0; left < order; left++)
// {
// System.err.print(">>>\t"+(left+1)+":");
// for (IntIterator it = succsIterator(left); it.hasNext();)
// System.err.print(" "+(it.next()+1));
// System.err.println();
// }
// initialize predLists and numOfPreds
predLists = new IntArrayList[order]; // an array of lists of predecessor indices
for (int right = 0; right < order; right++)
{
predLists[right] = new IntArrayList();
for (int left = 0; left < order; left++)
{
if (isEdge[left][right])
{
predLists[right].add(left);
numOfPreds[right]++;
}
}
}
// System.err.println(">>> Pred Lists:");
// for (int right = 0; right < order; right++)
// {
// System.err.print(">>>\t"+(right+1)+":");
// for (IntIterator it = predsIterator(right); it.hasNext();)
// System.err.print(" "+(it.next()+1));
// System.err.println();
// }
// create and initialize the array containing the first-successor right
// node of each left node
firstSuccs = new int[order];
for (int left = 0; left < order; left++)
firstSuccs[left] = getFirstSucc(left);
// System.err.print("firstSuccs:");
// for (int i = 0; i < order; i++)
// System.err.print(" "+(firstSuccs[i]+1));
// System.err.println();
// create and initialize the array containing the last-successor right
// node of each left node
lastSuccs = new int[order];
for (int left = 0; left < order; left++)
lastSuccs[left] = getFirstSucc(left);
// System.err.print("lastSuccs: ");
// for (int i = 0; i < order; i++)
// System.err.print(" "+(lastSuccs[i]+1));
// System.err.println();
// create and initialize the array containing the first-predecessor left
// node of each right node
firstPreds = new int[order];
for (int right = 0; right < order; right++)
firstPreds[right] = getFirstPred(right);
// System.err.print("firstPreds:");
// for (int i = 0; i < order; i++)
// System.err.print(" "+(firstPreds[i]+1));
// System.err.println();
// create and initialize the array containing the last-predecessor left
// node of each right node
lastPreds = new int[order];
for (int right = 0; right < order; right++)
lastPreds[right] = getLastPred(right);
// System.err.print("lastPreds: ");
// for (int i = 0; i < order; i++)
// System.err.print(" "+(lastPreds[i]+1));
// System.err.println();
// showComponents();
}
/**
* Return an IntIterator for the list of successors of
* left node.
*/
public IntIterator succsIterator (int left)
{
return succLists[left].iterator();
}
/**
* Return an IntIterator for the list of predecessors of
* right node.
*/
public IntIterator predsIterator (int right)
{
return predLists[right].iterator();
}
/**
* Return a String equal to the square-bracketed row/column
* index.
*/
private final String headerString (int index)
{
return "["+index+"]";
}
/**
* Return a String to serve as well-centered column header
* given a column-header String header, centering
* the bracketed column index according to the current
* printWidth().
*/
private final String centerColumnHeader (String header)
{
int headerWidth = header.length();
int beforeWidth = (printWidth() - headerWidth) / 2 + 2;
int afterWidth = printWidth() - beforeWidth - headerWidth - 1;
char spaceChar = ' ';
StringBuilder centeredHeader = new StringBuilder(spaceChar);
for (int i = 0; i < beforeWidth; i++)
centeredHeader.append(spaceChar);
centeredHeader.append(header);
for (int i = 0; i < afterWidth; i++)
centeredHeader.append(spaceChar);
return centeredHeader.append(spaceChar).toString();
}
/**
* This is the character used for showing no edge; defaults to the space
* char.
*/
private char noEdgeChar = ' ';
/**
* Return a String of noEdgeChars fitting the
* floating-point print width to indicate that there is no edge.
*/
private String noEdgeString ()
{
StringBuilder str = new StringBuilder();
for (int i = 0; i < printWidth(); i++)
str.append(noEdgeChar);
return str.toString();
}
/**
*
*/
/**
*
*/
/**
* This BipartiteGraph list of edges.
*/
static private ArrayList Edges;
/**
*
*/
}// end BipartiteGraph class
/**
*
*/
/**
*
*/
/**
* A local class representing a (left,right) edge between a
* left node of index left, and a right node of index right.
*/
class Edge
{
int left;
int right;
Edge (int left, int right)
{
this.left = left;
this.right = right;
}
boolean startsWith (int left)
{
return this.left == left;
}
boolean endsWith (int right)
{
return this.right == right;
}
boolean isFollowedBy (Edge next)
{
return right == next.left;
}
public boolean equal (Object other)
{
if (!(other instanceof Edge))
return false;
return (left == ((Edge)other).left) && (right == ((Edge)other).right);
}
public String toString ()
{
return "("+left+","+right+")";
}
}// end Edge class
/**
*
*/
/**
* A local class representing a matching of a BipartiteGraph.
*/
class Matching
{
ArrayList matching = new ArrayList();
BipartiteGraph graph;
Matching (BipartiteGraph graph)
{
this.graph = graph;
}
/**
* Return true iff this Matching is maximum for its
* BipartiteGraph.
*/
boolean isMaximum ()
{
return matching.size() == graph.rows();
}
/**
* Return true iff this Matching uses the given
* edge.
*/
boolean uses (Edge edge)
{
return uses(edge.left) || uses(edge.right);
}
/**
* Return true iff this Matching uses the given
* node.
*/
boolean uses (int node)
{
return degree(node) == 1;
}
/**
* Return the degree of the given node in this
* Matching. This is the number of Edge objects in this
* Matching for which the given node is a left
* or right.
*/
int degree (int node)
{
int degree = 0;
for (Iterator it = matching.iterator(); it.hasNext();)
{
Edge edge = (Edge)it.next();
if (edge.left == node || edge.right == node)
degree++;
}
return degree;
}
/**
*
*/
Matching add (Edge edge)
{
return this;
}
public boolean equal (Object other)
{
if (!(other instanceof Matching))
return false;
// TO FINISH
return true;
}
public String toString ()
{
StringBuilder buf = new StringBuilder();
// TO FINISH
return "{"+buf+"}";
}
}// end Matching class