BipartiteGraph.html

BipartiteGraph.java

// 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

Copyright: © by the author

Author: Hassan Aït-Kaci

Version: Last modified on Thu Dec 12 11:15:12 2019 by hak


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)

Object Constructors

Object Components

Object Methods

Node/Edge Methods
I/O Methods
Methods for Matchings and Paths
Local Private Methods

Class Methods

Class Components
Class Methods

Local Classes

Edge Class
Matching Class

See also: Matrix, Matrix

public class BipartiteGraph extends Matrix
{

Object Constructors

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();
  }

Object Components

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;

Object Methods

Node/Edge Methods

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];
  }

I/O Methods

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();
  }

Methods for Matchings and Paths

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

Local Private Methods

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();
  }

Class Components and Methods

Class Components

This BipartiteGraph list of edges.

  static private ArrayList Edges;

Class Methods



}// end BipartiteGraph class

Local Classes

Edge 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

Matching 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

This file was generated on Wed Dec 18 03:37:41 PST 2019 from file BipartiteGraph.java
by the hlt.language.tools.Hilite Java tool written by Hassan Aït-Kaci