// 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 Wed Nov 27 19:12:58 2019 by hak
* @author Hassan Aït-Kaci
* @copyright © by the author
*/
package hlt.math.matrix;
// Import my own hlt.language.util classes used for set operations in this class:
import hlt.language.util.SetOf;
import hlt.language.util.ArrayList;
import java.util.Hashtable;
/**
* 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 SquareMatrix, so using it can rely on its
* SquareMatrix 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., ...).
*
* @see Matrix
* @see DoublyStochasticMatrix
*/
public class BipartiteGraph extends SquareMatrix
{
/**
*
* Constructors
*
*/
/**
* Constructs an empty BipartiteGraph. N.B: this is a
* private constructor: the only public way to construct one is with the
* public newBipartiteGraph(double[][] data) method, which ensures
* that the data array is defined and square (violation of either condition
* causes a runtime exception to be thrown).
*/
private BipartiteGraph ()
{
}
/**
* Constructs a BipartiteGraph with the given data
* array. N.B: this is a private constructor: the only way to
* construct one is with the public newBipartiteGraph(double[][]
* data) method, which ensure checking that the data array is defined
* and square (violation of either condition causes a runtime exception to
* be thrown).
*/
private BipartiteGraph (double[][] data)
{
setData(data);
}
/**
*
* Bipartite Graph Components
*
*
* A BipartiteGraph has one specific additional component which is
* a boolean[][] array.
*/
/**
* This is a boolean matrix having the same sign pattern as the
* data array at graph creation time.
*/
private boolean[][] isEdge;
private initializeIsEdgeArray ()
{
int order = order();
isEdge = new boolean[order][order];
for (int i = 0; i < order; i++)
for (int j = 0; j < order; j++)
isEdge[i][j] = (data[i][j] == 0.0);
}
/**
* Return true iff there is an edge in this
* BipartiteGraph between left node i and right node
* j.
*/
public final boolean isEdge (int i, int j)
{
return isEdge[i][j];
}
/**
* Return true iff there is an edge in this
* BipartiteGraph between right node i and left node
* j.
*/
public final boolean isTransposeEdge (int i, int j)
{
return isEdge[j][i];
}
///////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
/**
* The set of indices, a SetOf(Integer).
*/
private SetOf indices = null;
/**
* The array of left nodes.
*/
private Node[] leftNodes = null;
/**
* The array of right nodes.
*/
private Node[] rightNodes = null;
/**
* Lists of Edges from of each left node (an array of ArrayLists of edges).
*/
private ArrayList[] edgesFromLeftNode = null;
/**
* Unlabeled successors of each left (an array of ints indices of
* right nodes).
*/
private int[] unlabeledSuccessors = null;
/**
* Unlabeled predecessors of each right (an array of ints indices
* of left nodes).
*/
private int[] unlabeledPredecessors = null;
/**
* A table mapping the name of an edge (a String) to the edge it
* refers to. This is to ensure a unique object per edge name.
*/
private Hashtable edgeTable = new Hashtable();
/**
* Return a unique representative for an edge from left node at index
* left to right node at index right.
*/
static final Edge getEdge (int left, int right)
{
String edgeName = ("L"+left+"R"+right).intern();
Edge knownEdge = (Edge)edgeTable.get(edgeName);
if (knownEdge == null)
edgeTable.put(edgeName,knownEdge=edge);
return knownEdge;
}
/**
* The dual component of a BipartiteGraph is the
* BipartiteGraph that corresponds to the transpose of this as a
* matrix. Graphically, it is the graph obtained by swapping the left and
* right nodes preserving edges as they are connected to their nodes. Why
* bother? This is for pragmatic concerns: Java uses C's multi-dimensional
* array representation where a 2D-array is in fact an 1D-array of
* 1D-arrays. So returning the i-th row of the double[][]
* data is done by direct access as the array double[]
* data[i]. But returning the j-th column of
* the same double[][] data necessitates looping through all the
* rows data[1], ..., data[data.length] and extract a new 1D array
* containing their j-th elements data[1][j],
* ..., data[data.length][j]. In other words, having
* the dual handy allows accessing columns as quickly as rows, and thus all
* right-node methods in this graph (that correspond to its column-oriented
* methods as a matrix) are more efficiently implemented as the dual's
* left-node methods (that correspond to its row-oriented methods as a
* matrix) — and vice-versa. This is because the dual's dual
* of this graph is of course this graph. To make the implementation
* consistent with the above, the first time the dual() method is
* invoked on a BipartiteGraph, its dual component is set
* to a new BipartiteGraph computed as the transpose of this as a
* matrix and sets this new graph's dual to this.
*/
private BipartiteGraph dual = null;
/**
*
* Static Methods
*
*/
/**
* Returns a new BipartiteGraph with the given data
* array of doubles. If data is null or not
* square, this throws a RuntimeException.
*/
public static BipartiteGraph newBipartiteGraph (double[][] data)
{
return new BipartiteGraph(data);
}
/**
* Returns the dual of this bipartite graph.
*/
public BipartiteGraph dual ()
{
if (dual != null) // if it has already been set
return dual; // return it
setDual(graphTranspose());
return this;
}
/**
* If it is not defined yet, set the component this.dual of this
* BipartiteGraph to the specified one and return the specified
* graph (i.e. the argument dual). If it is already
* defined do nothing. N.B.: Why doesn't this check whether the dual
* is indeed this graph and throw a runtime exception if this is
* not so? It does not because such can never be the case as things are set
* up since the BipartiteGraph creating its dual always creates a
* new one. So BipartiteGraph objects always exist in dual
* pairs consisting of a creator object (the one that creates its
* dual) and a created object (the one created by its dual).
*/
private BipartiteGraph setDual (BipartiteGraph dual)
{
if (this.dual == null)
{ // this graph has no dual yet; so set it to the given one:
this.dual = dual; // this is the creator
// and also set the dual graph's dual to this graph
dual.setDual(this);
}
// else // this graph already has a dual defined (this is the created)
// if (this.dual != this) // verify that the defined dual is this graph (CAN NEVER HAPPEN!)
// throw new RuntimeException("Non-consistent dual pair of bipartite graphs");
// so we're ok: there is nothing to do.
// always return the dual
return dual;
}
/**
* Modifies this BipartiteGraph in place to its own transpose and
* returns this.
*/
private final BipartiteGraph graphTranspose ()
{
return setData(dataTranspose(data));
}
// /**
// * Create and return an identity BipartiteGraph of order
// * order.
// */
// static public BipartiteGraph identity (int order)
// {
// return super.identity(order);
// }
/**
* Create and return a BipartiteGraph of order order with
* random entries having values between 0.0 and 1.0. See
* Matrix for how to control random
* value generation .
*/
static public BipartiteGraph random (int order)
{
return new BipartiteGraph().setData(randomDataArray(order,order));
}
/**
*
* Object Methods
*
*/
/**
* The base node index carrier list for sets of indices; once created and
* filled, never changes.
*/
private ArrayList nodeIndexList;
/**
* Create the base node index set-carrier list for sets of indices.
*/
private void createNodeIndexList (int size)
{
// create the base set-carrier for the set of node indices:
nodeIndexList = new ArrayList(size);
// for each index, fill it with a distinct Integer object having for
// value this index
for (int index = 0; index < size; index++)
nodeIndexList.add(Integer.valueOf(index));
// set the set of all indices to contain them all
indices = new SetOf(nodeIndexList).top();
System.err.println("created index set: "+indices);
}
/**
* The left node set-carrier list for sets of left nodes; once created and
* filled, never changes.
*/
private ArrayList leftNodeList;
/**
* Create the left node set-carrier list for sets of left nodes.
*/
private void createLeftNodeList (int size)
{
// create the base set-carrier for the set of left nodes:
leftNodeList = new ArrayList(size);
// for each index, fill it with a distinct Node object having for
// index this index
for (int index = 0; index < size; index++)
leftNodeList.add(new Node(index,true));
// set the set of all left nodes to contain them all
leftNodes = new SetOf(leftNodeList).top();
System.err.println("created left node set: "+leftNodes);
}
/**
* The right node set-carrier list for sets of right nodes; once created
* and filled, never changes.
*/
private ArrayList rightNodeList;
/**
* Create the right node set-carrier list for sets of right nodes.
*/
private void createRightNodeList (int size)
{
// create the base carrier for the set of right nodes:
rightNodeList = new ArrayList(size);
// for each index, fill it with a distinct Node object having for
// index this index
for (int index = 0; index < size; index++)
rightNodeList.add(new Node(index,false));
// set the set of all right nodes to contain them all
rightNodes = new SetOf(rightNodeList).top();
System.err.println("created right node set: "+rightNodes);
}
/**
* Initialize this BipartiteGraph with the given data
* array of doubles and return this. If the array is not
* square, a runtime exception is thrown.
*/
public BipartiteGraph setData (double[][] data)
{
super.setData(data); // set the matrix components (data, rows, cols)
// create the base set of node indices
createNodeIndexList(data.length);
// create the base set of left nodes
createLeftNodeList(data.length);
// create the base set of rights
createRightNodeList(data.length);
// set the graph components (leftNodes, rightNodes) from data array
initializeGraphComponents();
return this;
}
/**
* Initialize the graph components of this BipartiteGraph from its
* data array.
*/
private void initializeGraphComponents ()
{
int order = order();
// initialize the array of left nodes
Node[] leftNodes = new Node[order];
// initialize the array of right nodes
Node[] rightNodes = new Node[order];
// for each index
for (int i = 0; i < order; i++)
{
// create the left node of index i
Node leftNode = new Node(i,true);
// add it to the set of left nodes
leftNodes[i] = leftNode;
// create the right node of index i
Node rightNode = new Node(i,false);
// add it to the set of right nodes
rightNodes[i] = rightNode;
// initialize the edges from left node i
ArrayList edgesFromLeftNode = new ArrayList();
successors[i] = new ArrayList();
for (int j = 0; i < order; j++)
if (data[i][j] != 0.0)
{
Node leftNode = (Node)nodeIndexList.get(j);
edgesFromLeftNode[i].add(leftNode.index,getEdge(i,j));
}
}
// initialize the right
rightNodes = new SetOf(rightNodeList);
// initialize the predecessors of the right nodes
predecessors = new SetOf[order];
rightEdges = new SetOf[order];
for (int i = 0; i < order; i++)
{
predecessors[i] = new SetOf(nodeIndexList);
for (int j = 0; i < order; j++)
if (data[i][j] != 0.0)
{
Node from = (Node)nodeIndexList.get(j);
predecessors[i].add(from);
rightEdges[i].add(getEdge(i,j));
}
}
resetLabels();
}
/**
* Reset all nodes of this graph to be unlabeled.
*/
private final void resetLabels ()
{
for (int i = 0; i < order(); i++)
unlabeledSuccessors[i] = unlabeledPredecessors[i] = -1;
}
/**
* Returns the set of (right) nodes the given (left) node is
* connected to.
*/
// public final SetOf /*rightNodes*/ successors (Node node)
// {
// /// return node.SOMETHING ???
// }
}
/**
*
* Private Classes
*
*/
/**
* This class represents node objects.
*/
class Node
{
/**
* The node index in nodeIndexList.
*/
int index;
/**
* This is true if this node is a left node,
* and false if it is is a right node.
*/
boolean isLeft;
/**
* The node's name: it is of the form "Xn" where X
* is L if this is a left note and R otherwise, and
* n is the node's index.
*/
String name;
/**
* This is the node's label. If this node's in unlabeled, this is
* -1. If this node is labeled, it is the index of a right node
* when this is a left node, and it is the index of a left node when this
* is a right node.
*/
int label = -1;
/**
* Constructs a node at index: a left node isLeft is
* true, and a right node otherwise.
*/
Node (int index, boolean isLeft)
{
this.index = index;
this.isLeft = isLeft;
name = (isLeft?"L":"R")+index;
}
/**
* Creates and return a new left node at index.
*/
Node newLeftNode (int index)
{
return new Node(index,true);
}
/**
* Creates and return a new right node at index.
*/
Node newRightNode (int index)
{
return new Node(index,false);
}
/**
* Returns a string form for this node (its name).
*/
public String toString ()
{
return name;
}
}
/**
* This class represents edge objects.
*/
class Edge
{
/**
* The BipartiteGraph this edge refers to (and was created from).
*/
BipartiteGraph graph;
/**
* This edge's left node.
*/
Node left;
/**
* This edge's right node.
*/
Node right;
/**
* Contructs an edge between the two given nodes with weight weight.
*/
private Edge (Node left, Node right, BipartiteGraph graph)
{
this.graph = graph.
this.left = left;
this.right = right;
if (weight() == 0.0)
throw new RuntimeException("Cannot create a zero-edge between node "+left+
" and node "+right);
}
/**
* Return the weight of this edge; i.e.,the double entry in
* data corresponding to its left and right nodes.
*/
double weight ()
{
return graph.data()[left.index,right.index];
}
/**
* Returns a string form for this edge of the form: [left,right](weight)
*/
public String toString ()
{
return "["+left+","+right+"]("+weight()+")";
}
}