libibdm-dev 1.2-OFED-1.4.2-1.1 / usr / include / ibdm / Bipartite.h

/*
 * Copyright (c) 2008 Mellanox Technologies LTD. All rights reserved.
 *
 * This software is available to you under a choice of one of two
 * licenses.  You may choose to be licensed under the terms of the GNU
 * General Public License (GPL) Version 2, available from the file
 * COPYING in the main directory of this source tree, or the
 * OpenIB.org BSD license below:
 *
 *     Redistribution and use in source and binary forms, with or
 *     without modification, are permitted provided that the following
 *     conditions are met:
 *
 *      - Redistributions of source code must retain the above
 *        copyright notice, this list of conditions and the following
 *        disclaimer.
 *
 *      - Redistributions in binary form must reproduce the above
 *        copyright notice, this list of conditions and the following
 *        disclaimer in the documentation and/or other materials
 *        provided with the distribution.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * $Id$
 */

/*
 * Fabric Utilities Project
 *
 * Bipartite Graph Header file
 *
 * Author: Vladimir Zdornov, Mellanox Technologies
 *
 */

#ifndef IBDM_BIPARTITE_H_
#define IBDM_BIPARTITE_H_

#include <list>
#include "RouteSys.h"

using namespace std;

typedef list<void*>::iterator peIter;
typedef list<void*> peList;

typedef enum side_ {LEFT=0, RIGHT} side;

class edge
{
 public:
  // Vertices
  void* v1;
  void* v2;
  // Connection indices
  int idx1;
  int idx2;

  // Edge list iterator
  peIter it;

  // Request data
  inputData reqDat;

  // C'tor
  edge():v1(NULL),v2(NULL),idx1(-1),idx2(-1){};

  // Get the vertex on the other side of the edge
  void* otherSide(const void* v) {
    if (v == v1)
      return v2;
    if (v == v2)
      return v1;
    return NULL;
  }

  // Check whether the edge is matched
  bool isMatched();
};

class vertex
{
  // ID
  int id;
  // Side (0 - left, 1 - right)
  side s;
  // Array of connected edges
  edge** connections;
  // Initial number of neighbors
  int radix;
  // Current number of neighbors
  int maxUsed;

  // Matching fields

  // Edge leading to the partner (NULL if none)
  edge* partner;
  // Array of layers predecessors
  edge** pred;
  // Number of predecessors
  int predCount;
  // Array of layers successors
  edge** succ;
  // Number of successors
  int succCount;
  // Denotes whether vertex is currently in layers
  bool inLayers;

 public:
  // C'tor
  vertex(int n, side sd, int rad);
  // D'tor
  ~vertex();
  // Getters + Setters
  int getID() const;
  side getSide() const;
  edge* getPartner() const;
  vertex* getPredecessor() const;
  bool getInLayers() const;
  void setInLayers(bool b);
  // Reset matching info
  void resetLayersInfo();
  // Adding partner to match layers
  void addPartnerLayers(list<vertex*>& l);
  // Adding non-partners to match layers
  // Return true if one of the neighbors was free
  bool addNonPartnersLayers(list<vertex*>& l);
  // Add new connection (this vertex only)
  void pushConnection(edge* e);
  // Remove given connection (vertices on both sides)
  void delConnection(edge* e);
  // Flip predecessor edge status
  // idx represents the layer index % 2 in the augmenting backward traversal (starting from 0)
  void flipPredEdge(int idx);
  // Remove vertex from layers, update predecessors and successors
  void unLink(list<vertex*>& l);
  // Get SOME connection and remove it (from both sides)
  // If no connections present NULL is returned
  edge* popConnection();
  // Match vertex to SOME unmatched neighbor
  // In case of success true is returned, false in case of failure
  bool match();
};

class Bipartite
{
  // Number of vertices on each side
  int size;
  // Number of edges per vertex
  int radix;
  // Vertices arrays
  vertex** leftSide;
  vertex** rightSide;

  peIter it;
  // Edges list
  peList List;

  // Apply augmenting paths
  void augment(list<vertex*>& l);

 public:
  // C'tor
  Bipartite(int s, int r);
  // D'tor
  ~Bipartite();
  int getRadix() const;
  // Set iterator to first edge (returns false if list is empty)
  bool setIterFirst();
  // Set iterator to next edge (return false if list end is reached)
  bool setIterNext();
  // Get inputData pointed by iterator
  inputData getReqDat();
  // Add connection between two nodes
  void connectNodes(int n1, int n2, inputData reqDat);
  // Find maximal matching on current graph
  void maximalMatch();
  // Find maximum matching and remove it from the graph
  // We use a variant of Hopcroft-Karp algorithm
  Bipartite* maximumMatch();
  // Decompose bipartite into to edge disjoint radix/2-regular bps
  // We use a variant of Euler Decomposition
  void decompose(Bipartite** bp1, Bipartite** bp2);
};

#endif