graph.cpp

orange源码 数据挖掘技术

  TEdge **e = edges;
  for(int i = nVertices; i--; e++)
    if (*e)
      delete *e;
  delete edges;
}



void TGraphAsTree::sortIndices(const int &v1, const int &v2, TEdge **&e, int &subvert) const
{
  if (directed) {
    if ((v1 >= nVertices) || (v1 < 0))
      raiseError("vertex index %i is out of range 0-%i", v1, nVertices-1);
    if ((v2 >= nVertices) || (v2 < 0))
      raiseError("vertex index %i is out of range 0-%i", v2, nVertices-1);

    e = edges + v1;
    subvert = v2;
  }
  else {
    if (v1<v2) {
      if ((v2>=nVertices) || (v1<0))
        raiseError("invalid vertex index (%i, %i)", v1, v2);

      e = edges + v2;
      subvert = v1;
    }

    else {
      if ((v1>=nVertices) || (v2<0))
        raiseError("invalid vertex index (%i, %i)", v1, v2);

      e = edges + v1;
      subvert = v2;
    }
  }
}

double *TGraphAsTree::getEdge(TEdge *node, const int &subvert)
{
  while(node) {
    const int nvert = (int)(node->vertex & 0x7fffffff);
    if (nvert == subvert)
      return &node->weights;
    node = subvert < nvert ? node->left : node->right;
  }

  return NULL;
}


double *TGraphAsTree::getEdge(const int &v1, const int &v2)
{
  TEdge **pnode;
  int subvert;
  sortIndices(v1, v2, pnode, subvert);
  return getEdge(*pnode, subvert);
}


#define PAINT_RED(x) (x)->vertex |= 0x80000000
#define PAINT_BLACK(x) (x)->vertex &= 0x7fffffff
#define IS_RED(x) ((x)->vertex > 0x7fffffff)
#define IS_BLACK(x) ((x)->vertex < 0x80000000)

double *TGraphAsTree::getOrCreateEdge(const int &v1, const int &v2)
{
  TEdge **node;
  int subvert;
  sortIndices(v1, v2, node, subvert);

  vector<TEdge **> stack;

  stack.push_back(node);

  while(*node) {
    const int nvert = (int)((*node)->vertex & 0x7fffffff);
    if (nvert == subvert)
      return &((*node)->weights);
    node = &(subvert < nvert ? (*node)->left : (*node)->right);
    stack.push_back(node);
  }

  vector<TEdge **>::const_iterator sptr(stack.end()-1), stop(stack.begin());
  **sptr = createEdge(subvert | 0x80000000);
  double *res = &((***sptr).weights);

  // while the current node's parent is red
  while((sptr!=stop) && IS_RED(*sptr[-1])) { 

    // this node has no grandparent -- just paint the father black
    if (sptr - stop == 1) {
      PAINT_BLACK(**stop);
      break;
    }

    #define TROOT *sptr[-2]
    TEdge * const grandParent = *sptr[-2];
    TEdge * const parent = *sptr[-1];
    TEdge * const node = **sptr;

    // this node has a red uncle -- paint the grandfather red and parent and uncle black, handle the grandfather
    TEdge * const uncle = (sptr[-1] == &(grandParent->left)) ? grandParent->right : grandParent->left;
    if (uncle && IS_RED(uncle)) {
      PAINT_RED(grandParent);
      PAINT_BLACK(grandParent->left);
      PAINT_BLACK(grandParent->right);
      sptr -= 2; // now let's deal with the grandparent
      continue;
    }

    // if this node's parent is the left child of its grandparent...
    if (sptr[-1] == &(grandParent->left))

      // if this node is the left child of its parent
      if (*sptr == &(parent->left)) {
        grandParent->left = parent->right; // watchout: this overrides *sptr[-1] (it is stored in parent, though)
        parent->right = grandParent;
        TROOT = parent;

        PAINT_RED(grandParent);
        PAINT_BLACK(parent);
        break;
      }

      // if this node is the right child of its parent
      else {
        parent->right = node->left;
        grandParent->left = node->right;
        node->left = parent;
        node->right = grandParent;
        TROOT = node;

        PAINT_BLACK(node);
        PAINT_RED(grandParent);
        break;
      }

    // if this node's parent is the right child of its grandparent
    else

      // if this node is the right child of its parent
      if (*sptr == &(parent->right)) {
        grandParent->right = parent->left; // watchout: this overrides *sptr[-1] (it is stored in parent, though)
        parent->left = grandParent;
        TROOT = parent;

        PAINT_RED(grandParent);
        PAINT_BLACK(parent);
        break;
      }

      // if this node is the leftchild of its parent
      else {
        parent->left = node->right;
        grandParent->right = node->left;
        node->right = parent;
        node->left = grandParent;
        TROOT = node;

        PAINT_BLACK(node);
        PAINT_RED(grandParent);
        break;
      }
  }

  return res;
}


void TGraphAsTree::removeEdge(const int &v1, const int &v2)
{
  TEdge **node;
  int subvert;
  sortIndices(v1, v2, node, subvert);

  vector<TEdge **> stack;

  stack.push_back(node);

  while(*node) {
    const int nvert = (int)((*node)->vertex & 0x7fffffff);
    if (nvert == subvert)
      break;
    node = &(subvert < nvert ? (*node)->left : (*node)->right);
    stack.push_back(node);
  }

  if (!*node)
    return;

  TEdge *temp = *node;

  // find the bigest element in the left subtree
  if ((*node)->left) {
    node = &(*node)->left;
    stack.push_back(node);

    while ((*node)->right) {
      node = &(*node)->right;
      stack.push_back(node);
    }
  }

  if (*node != temp) {
    temp->vertex = (temp->vertex & 0x80000000) | ((*node)->vertex & 0x7fffffff);
    memcpy(&temp->weights, &(*node)->weights, nEdgeTypes * sizeof(double));
  }

  bool removedRed = IS_RED(*node);

  temp = *node;
  *node = (*node)->left ? (*node)->left : (*node)->right;
  temp->left = temp->right = NULL;
  delete temp;

  if (removedRed)
    return;

  vector<TEdge **>::iterator sptr(stack.end()-1), stop(stack.begin());
  
  for(;;) {
    TEdge *node = **sptr;

    if (node && IS_RED(node)) {
      PAINT_BLACK(node);
      return;
    }

    if (sptr == stop)
      return;

    TEdge *parent = *sptr[-1];
    
    if (*sptr == &(parent->left)) {
      TEdge *brother = parent->right;

      // Kononenko, case C1: brother is red, thus nephews are black; rotate so that one nephew becomes a brother
      if (IS_RED(brother)) {
        *sptr[-1] = brother;
        parent->right = brother->left;
        brother->left = parent;

        PAINT_BLACK(brother);
        PAINT_RED(parent);

        // fix the stack
        int sindex = sptr - stop;
        *sptr = &(brother->left);
        stack.push_back(&(parent->left));
        // push_back might have invalidated sptr
        stop = stack.begin();
        sptr = stop+sindex+1;

        brother = parent->right;
      }

      // Kononenko, case C2: brother is black and has no red nephews; paint him red and some node upwards will have to become black
      if ((!brother->left || IS_BLACK(brother->left)) && (!brother->right || IS_BLACK(brother->right))) {
        PAINT_RED(brother);
        sptr--;
        continue;
      }

      // Kononenko, case C3.1: brother is black and the outer nephew is black: bring the inner (which is surely red) out
      // This does not follow the book -- it does Fig 23a and 23b in one step
      if (!brother->right || IS_BLACK(brother->right)) {
        TEdge *nephew = brother->left;
        *sptr[-1] = nephew;
        parent->right = nephew->left;
        brother->left = nephew->right;
        nephew->left = parent;
        nephew->right = brother;

        if IS_RED(parent)
          PAINT_BLACK(parent);
        else
          PAINT_BLACK(nephew);

        return;
      }

      // Kononenko, case C3a: brother is black and the outer nephew is red
      parent->right = brother->left;
      brother->left = parent;
      *sptr[-1] = brother;

      if IS_RED(parent) {
        PAINT_RED(brother);
        PAINT_BLACK(parent);
      }
      PAINT_BLACK(brother->right);

      return;
    }
     
    else {
      TEdge *brother = parent->left;

      // Kononenko, case C1: brother is red, thus nephews are black; rotate so that one nephew becomes a brother
      if (IS_RED(brother)) {
        *sptr[-1] = brother;
        parent->left = brother->right;
        brother->right = parent;

        PAINT_BLACK(brother);
        PAINT_RED(parent);

        // fix the stack
        int sindex = sptr - stop;
        *sptr = &(brother->right);
        stack.push_back(&(parent->right));
        // push_back might have invalidated sptr
        stop = stack.begin();
        sptr = stop+sindex+1;

        brother = parent->left;
      }

      // Kononenko, case C2: brother is black and has no red nephews; paint him red and some node upwards will have to become black
      if ((!brother->left || IS_BLACK(brother->left)) && (!brother->right || IS_BLACK(brother->right))) {
        PAINT_RED(brother);
        sptr--;
        continue;
      }

      // Kononenko, case C3.1: brother is black and the outer nephew is black: bring the inner (which is surely red) out
      // This does not follow the book -- it does Fig 23a and 23b in one step
      if (!brother->left || IS_BLACK(brother->left)) {
        TEdge *nephew = brother->right;
        *sptr[-1] = nephew;
        parent->left = nephew->right;
        brother->right = nephew->left;
        nephew->right = parent;
        nephew->left = brother;

        if IS_RED(parent)
          PAINT_BLACK(parent);
        else
          PAINT_BLACK(nephew);
        return;
      }

      // Kononenko, case C3a: brother is black and the outer nephew is red
      parent->left = brother->right;
      brother->right = parent;
      *sptr[-1] = brother;

      if IS_RED(parent) {
        PAINT_RED(brother);
        PAINT_BLACK(parent);
      }
      PAINT_BLACK(brother->left);

      return;
    }
  }
}


void TGraphAsTree::getNeighbours_fromTree(TEdge *edge, vector<int> &neighbours)
{
  if (edge->left)
    getNeighbours_fromTree(edge->left, neighbours);

  neighbours.push_back(int(edge->vertex & 0x7fffffff));

  if (edge->right)
    getNeighbours_fromTree(edge->right, neighbours);
}



void TGraphAsTree::getNeighbours_Undirected(const int &v, vector<int> &neighbours)
{
  if (edges[v])
    getNeighbours_fromTree(edges[v], neighbours);

  int v2 = v+1;
  for(TEdge **ee = edges+v+1; v2 < nVertices; v2++, ee++)
    if (*ee && getEdge(*ee, v))
      neighbours.push_back(v2);
}



void TGraphAsTree::getNeighbours_fromTree_merge(TEdge *edge, vector<int> &neighbours, const int &v, int &latest)
{
  const int thisVertex = int(edge->vertex & 0x7fffffff);

  if (edge->left)
    getNeighbours_fromTree_merge(edge->left, neighbours, v, latest);

  for(TEdge **node = edges + ++latest; latest < thisVertex; latest++, node++)
    if (*node && getEdge(*node, v))
      neighbours.push_back(latest);
  
  neighbours.push_back(thisVertex);

  if (edge->right)
    getNeighbours_fromTree_merge(edge->right, neighbours, v, latest);
}

void TGraphAsTree::getNeighbours(const int &v, vector<int> &neighbours)
{
  GN_INIT

  int latest = -1;
  if (edges[v])
    getNeighbours_fromTree_merge(edges[v], neighbours, v, latest);

  for(TEdge **node = edges + ++latest; latest < nVertices; latest++, node++)
    if (*node && getEdge(*node, v))
      neighbours.push_back(latest);
}


void TGraphAsTree::getNeighboursFrom(const int &v, vector<int> &neighbours)
{
  GN_INIT
  getNeighboursFrom_Single(v, neighbours);
}


void TGraphAsTree::getNeighboursFrom_Single(const int &v, vector<int> &neighbours)
{
  neighbours.clear();
  if (edges[v])
    getNeighbours_fromTree(edges[v], neighbours);
}


void TGraphAsTree::getNeighboursTo(const int &v, vector<int> &neighbours)
{
  GN_INIT
  int v2 = 0;
  for(TEdge **ee = edges; v2 < nVertices; v2++, ee++)
    if (*ee && getEdge(*ee, v))
      neighbours.push_back(v2);
}



// A macro for checking the existence of certain type of connection,
// useful for GraphAsTree (this is not the same as the ones defined
// for GraphAsMatrix and for GraphAsList)

#define CHECK_EDGE(e,v2) { if (CONNECTED((&(e)->weights)[edgeType])) neighbours.push_back((v2)); }
#define CHECK_EDGE_TO(v2) { \
  double *w = *node ? getEdge(*node,v) : NULL; \
  if (w && CONNECTED(w[edgeType])) \
    neighbours.push_back(v2); \
  }

void TGraphAsTree::getNeighbours_fromTree(TEdge *edge, const int &edgeType, vector<int> &neighbours)
{
  if (edge->left)
    getNeighbours_fromTree(edge->left, edgeType, neighbours);

  CHECK_EDGE(edge, int(edge->vertex & 0x7fffffff));

  if (edge->right)
    getNeighbours_fromTree(edge->right, edgeType, neighbours);
}


void TGraphAsTree::getNeighbours_Undirected(const int &v, const int &edgeType, vector<int> &neighbours)
{
  getNeighbours_fromTree(edges[v], edgeType, neighbours);

  int v2 = v+1;
  for(TEdge **node = edges+v+1; v2 < nVertices; v2++, node++) 
    CHECK_EDGE_TO(v2)
}



void TGraphAsTree::getNeighbours_fromTree_merge(TEdge *edge, const int &edgeType, vector<int> &neighbours, const int &v, int &latest)
{
  const int thisVertex = int(edge->vertex & 0x7fffffff);

  if (edge->left)
    getNeighbours_fromTree_merge(edge->left, edgeType, neighbours, v, latest);

  for(TEdge **node = edges + ++latest; latest < thisVertex; latest++, node++)
    CHECK_EDGE_TO(latest)
  
  CHECK_EDGE(edge, thisVertex)

  if (edge->right)
    getNeighbours_fromTree_merge(edge->right, edgeType, neighbours, v, latest);
}


void TGraphAsTree::getNeighbours(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE

  int latest = -1;
  if (edges[v])
    getNeighbours_fromTree_merge(edges[v], edgeType, neighbours, v, latest);

  for(TEdge **node = edges + ++latest; latest < nVertices; latest++)
    CHECK_EDGE_TO(latest)
}


void TGraphAsTree::getNeighboursFrom(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  getNeighboursFrom_Single(v, edgeType, neighbours);
}


void TGraphAsTree::getNeighboursFrom_Single(const int &v, const int &edgeType, vector<int> &neighbours)
{
  neighbours.clear();
  if (edges[v])
    getNeighbours_fromTree(edges[v], edgeType, neighbours);
}


void TGraphAsTree::getNeighboursTo(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  for(TEdge **node = edges; v2 < nVertices; v2++, node++)
    CHECK_EDGE_TO(v2)
}