graph.cpp

orange源码 数据挖掘技术

/*
    This file is part of Orange.

    Orange is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Orange is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Orange; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    Authors: Janez Demsar, Blaz Zupan, 1996--2002
    Contact: [e-mail]
*/


#include "graph.ppp"

double _disconbuf;

bool set_disconbuf() { 
  DISCONNECT(_disconbuf);
return true;
}

bool _foognc = set_disconbuf();


//template ORANGE_API GCPtr<TGraph>::GCPtr<TGraph>(TGraph *);

#define GN_INIT \
  if ((v < 0) || (v >= nVertices)) \
    raiseError("vertex index %i is out of range 0-%i", v, nVertices-1); \
  neighbours.clear(); \
  \
  if (!directed) { \
    getNeighbours_Undirected(v, neighbours); \
    return; \
  }

#define GN_INIT_EDGETYPE \
  if ((v < 0) || (v >= nVertices)) \
    raiseError("vertex index %i is out of range 0-%i", v, nVertices-1); \
  if (edgeType >= nEdgeTypes) \
    raiseError("edge type %i is out of range 0-%i", v, nEdgeTypes-1); \
  neighbours.clear(); \
  \
  if (!directed) {\
    getNeighbours_Undirected(v, edgeType, neighbours); \
    return; \
  }



TGraph::TGraph(const int &nVert, const int &nTypes, const bool dir)
: nVertices(nVert),
  nEdgeTypes(nTypes),
  directed(dir),
  lastAddition(-1),
  lastRemoval(-1),
  currentVersion(0)
{
  if (nVertices<1)
    raiseError("invalid number of vertices (less than 1)");

  if (!nEdgeTypes)
    nEdgeTypes = 1;
  else if (nEdgeTypes < 0)
    raiseError("invalid (negative) number of edge types");
}


TGraphAsMatrix::TGraphAsMatrix(const int &nVert, const int &nTypes, const bool dir)
: TGraph(nVert, nTypes, dir),
  msize(nEdgeTypes * (directed ? nVertices * nVertices : (nVertices*(nVertices+1)) >> 1))
{
  edges = new double[msize];
  for(double *vt = edges, *ve = edges + msize; vt != ve; DISCONNECT(*(vt++)));
}

TGraphAsMatrix::~TGraphAsMatrix()
{ 
  delete edges;
}


double *TGraphAsMatrix::getEdge(const int &v1, const int &v2)
{ 
  double *edge = findEdge(v1, v2);
  for(double *e = edge, *ee = edge+nEdgeTypes; e!=ee; e++)
    if (CONNECTED(*e))
      return edge;
  return NULL;
}
      

double *TGraphAsMatrix::findEdge(const int &v1, const int &v2)
{ 
  if (v1>v2)
    if ((v1>=nVertices) || (v2<0))
      raiseError("invalid vertex index (%i, %i)", v1, v2);
    else
      return edges + nEdgeTypes * (v2 + (directed ? v1*nVertices : ((v1*(v1+1))) >> 1));
  else
    if ((v2 >= nVertices) || (v1<0))
      raiseError("invalid vertex index (%i, %i)", v1, v2);
    else
      return edges + nEdgeTypes * (directed ? (v1*nVertices + v2) : (((v2*(v2+1)) >> 1) + v1) );

  return NULL; // only to make the compiler happy
}


double *TGraphAsMatrix::getOrCreateEdge(const int &v1, const int &v2)
{ 
  double *res = findEdge(v1, v2);
  lastAddition = ++currentVersion;
  return res;
}


void TGraphAsMatrix::removeEdge(const int &v1, const int &v2)
{
  double *edge = getEdge(v1, v2);
  if (edge) {
    for(double *eedge = edge + nEdgeTypes; edge != eedge; DISCONNECT(*edge++));
    lastRemoval = ++currentVersion;
  }
}


#define CHECK_NONEMPTY(weights) \
{ for(swe = (weights), ne = nEdgeTypes; ne-- && !CONNECTED(*swe++); ); \
  if (ne >= 0) { neighbours.push_back(v2); continue; } }


void TGraphAsMatrix::getNeighbours_Undirected(const int &v, vector<int> &neighbours)
{
  int v2 = 0, ne;
  double *swe;
  double *weights = edges + nEdgeTypes * ((v * (v+1)) >> 1);

  for(; v2<=v; weights += nEdgeTypes, v2++)
    CHECK_NONEMPTY(weights)

  // v2 now equals v+1 and weights points to the beginning of the row for v2
  for(weights += v * nEdgeTypes; v2 < nVertices; weights += ++v2 * nEdgeTypes)
    CHECK_NONEMPTY(weights)
}


void TGraphAsMatrix::getNeighbours(const int &v, vector<int> &neighbours)
{
  GN_INIT
  int v2 = 0, ne;
  double *swe;
  int llen = nVertices * nEdgeTypes;
  double *weightsFrom = edges + nEdgeTypes * v * nVertices;
  double *weightsTo = edges + nEdgeTypes * v;
  for(; v2 < nVertices; weightsFrom += nEdgeTypes, weightsTo += llen, v2++) {
    CHECK_NONEMPTY(weightsFrom)
    CHECK_NONEMPTY(weightsTo)
  }
}


void TGraphAsMatrix::getNeighboursFrom(const int &v, vector<int> &neighbours)
{
  GN_INIT
  getNeighboursFrom_Single(v, neighbours);
  int v2 = 0, ne;
  for(double *swe, *weights = edges + nEdgeTypes * v * nVertices; v2 < nVertices; weights += nEdgeTypes, v2++)
    CHECK_NONEMPTY(weights)
}


void TGraphAsMatrix::getNeighboursFrom_Single(const int &v, vector<int> &neighbours)
{
  neighbours.clear();
  int v2 = 0, ne;
  for(double *swe, *weights = edges + nEdgeTypes * (directed ? (v * nVertices) : ((v*(v+1)) >> 1)); v2 <= v; weights += nEdgeTypes, v2++)
    CHECK_NONEMPTY(weights)
}


void TGraphAsMatrix::getNeighboursTo(const int &v, vector<int> &neighbours)
{
  GN_INIT
  int v2 = 0, ne;
  int llen = nVertices * nEdgeTypes;
  for(double *swe, *weights = edges + nEdgeTypes * v; v2 < nVertices; weights += llen, v2++)
    CHECK_NONEMPTY(weights)
}

#undef CHECK_NONEMPTY


// A macro for checking the existence of certain type of connection,
// used for GraphAsMatrix (another macro with the same name is defined
// later, which works for other representations)

#define CHECK_EDGE(weights) \
  if (CONNECTED(*weights)) \
    neighbours.push_back((v2));

void TGraphAsMatrix::getNeighbours_Undirected(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  double *weights = edges + nEdgeTypes * ((v * (v+1)) >> 1) + edgeType, *we = weights + nEdgeTypes * (v+1);

  for(; weights != we; weights += nEdgeTypes, v2++)
    CHECK_EDGE(weights)

  // v2 now equals v+1 and weights points to the beginning of the row for v2
  for(; v2 < nVertices; weights += v2++ * nEdgeTypes)
    CHECK_EDGE(weights)
}


void TGraphAsMatrix::getNeighbours(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  double *weightsFrom = edges + nEdgeTypes * v * nVertices + edgeType;
  double *weightsTo = edges + nEdgeTypes * v + edgeType;
  for(; v2 < nVertices; weightsFrom += nEdgeTypes, weightsTo += nEdgeTypes * nVertices, v2++)
    if (CONNECTED(*weightsFrom) || CONNECTED(*weightsTo))
      neighbours.push_back(v2);
}


void TGraphAsMatrix::getNeighboursFrom(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  for(double *weights = edges + nEdgeTypes * v * nVertices + edgeType; v2 < nVertices; weights += nEdgeTypes, v2++)
    CHECK_EDGE(weights)
}


void TGraphAsMatrix::getNeighboursFrom_Single(const int &v, const int &edgeType, vector<int> &neighbours)
{
  neighbours.clear();
  int v2 = 0;
  for(double *weights = edges + nEdgeTypes * (directed ? (v * nVertices) : ((v*(v+1)) >> 1)) + edgeType; v2 <=v; weights += nEdgeTypes, v2++)
    CHECK_EDGE(weights)
}


void TGraphAsMatrix::getNeighboursTo(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  int llen = nVertices * nEdgeTypes;
  for(double *weights = edges + nEdgeTypes * v + edgeType; v2 < nVertices; weights += llen, v2++)
    CHECK_EDGE(weights)
}

#undef CHECK_EDGE

TGraphAsList::TEdge *TGraphAsList::createEdge(TEdge *next, const int &vertex) const
{
  TEdge *newedge = (TEdge *)malloc(sizeof(TEdge) + (nEdgeTypes-1)*sizeof(double));
  newedge->next = next;
  newedge->vertex = vertex;
  double *w = &newedge->weights;
  for(int i = nEdgeTypes; i--; DISCONNECT(*w++));
  return newedge;
}



TGraphAsList::TGraphAsList(const int &nVert, const int &nEdge, const bool dir)
: TGraph(nVert, nEdge, dir),
  edges(new TEdge *[nVert])
{
  TEdge **e = edges;
  for(int i = nVert; i--; *e++ = NULL);
}


TGraphAsList::~TGraphAsList()
{
  TEdge **e = edges;
  for(int i = nVertices; i--; e++)
    for(TEdge *ei = *e, *en; ei; ei = en) {
      en = ei->next;
      delete ei;
    }
  delete edges;
}


bool TGraphAsList::findEdgePtr(const int &v1, const int &v2, TEdge **&e, int &subvert)
{
  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;
    }
  }
  
  while(*e)
    if ((*e)->vertex >= subvert)
      return (*e)->vertex == subvert;
    else
      e = &((*e)->next);

  return false;
}


double *TGraphAsList::getEdge(const int &v1, const int &v2)
{
  TEdge **e;
  int subvert;
  return findEdgePtr(v1, v2, e, subvert) ? &((*e)->weights) : NULL;
}


double *TGraphAsList::getOrCreateEdge(const int &v1, const int &v2)
{
  TEdge **e;
  int subvert;
  if (!findEdgePtr(v1, v2, e, subvert))
    *e = createEdge(*e, subvert);

  return &((*e)->weights);
}


void TGraphAsList::removeEdge(const int &v1, const int &v2)
{
  TEdge **e;
  int subvert;
  if (findEdgePtr(v1, v2, e, subvert)) {
    TEdge *n = (*e)->next;
    delete *e;
    *e = n;
  }
}

void TGraphAsList::getNeighbours_Undirected(const int &v, vector<int> &neighbours)
{
  TEdge *e;
  for(e = edges[v]; e; e = e->next)
    neighbours.push_back(e->vertex);

  if (!directed) {
    int v2 = v+1;
    for(TEdge **se = edges+v2, **ee = edges+nVertices; se != ee; v2++, se++) {
      for(e = *se; e && (e->vertex <=v); e = e->next)
        if (e->vertex == v) {
          neighbours.push_back(v2);
          break;
        }
    }
  }
}


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

  // passes through the v's list and the edges simultaneously and merges the neighbours to get a sorted list
  int lastV = -1;
  for(TEdge *e = edges[v]; e; lastV = e->vertex, e = e->next) {
    for(int v2 = lastV; ++v2 != e->vertex; ) {
      for(TEdge *e2 = edges[v2]; e2 && (e2->vertex <=v); e2 = e2->next)
        if (e2->vertex == v) {
          neighbours.push_back(v2);
          break;
        }
    }

    neighbours.push_back(e->vertex);
  }
}


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


void TGraphAsList::getNeighboursFrom_Single(const int &v, vector<int> &neighbours)
{
  neighbours.clear();
  for(TEdge *e = edges[v]; e; e = e->next)
    neighbours.push_back(e->vertex);
}


void TGraphAsList::getNeighboursTo(const int &v, vector<int> &neighbours)
{
  GN_INIT
  int v2 = 0;
  for(TEdge **se = edges, **ee = edges+nVertices; se != ee; v2++, se++) {
    for(TEdge *e = *se; e && (e->vertex <=v); e = e->next)
      if (e->vertex == v) {
        neighbours.push_back(v2);
        break;
      }
  }
}


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

#define CHECK_EDGE(e,v2) { if (CONNECTED((&(e)->weights)[edgeType])) neighbours.push_back((v2)); }
#define CHECK_EDGE_TO(e) { if (e->vertex==v) { CHECK_EDGE(e, v2); break; }}

void TGraphAsList::getNeighbours_Undirected(const int &v, const int &edgeType, vector<int> &neighbours)
{
  TEdge *e;
  for(e = edges[v]; e; e = e->next)
    CHECK_EDGE(e, e->vertex);

  int v2 = v+1;
  for(TEdge **se = edges+v2, **ee = edges+nVertices; se != ee; v2++, se++)
    for(e = *se; e && (e->vertex <=v); e = e->next)
      CHECK_EDGE_TO(e)
}




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

  // passes through the v's list and the edges simultaneously and merges the neighbours to get a sorted list
  int lastV = -1;
  for(TEdge *e = edges[v]; e; lastV = e->vertex, e = e->next) {
    for(int v2 = lastV; ++v2 != e->vertex; )
      for(TEdge *e2 = edges[v2]; e2 && (e2->vertex <=v); e2 = e2->next)
        CHECK_EDGE_TO(e2)
    CHECK_EDGE(e,e->vertex)
  }
}


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


void TGraphAsList::getNeighboursFrom_Single(const int &v, const int &edgeType, vector<int> &neighbours)
{
  neighbours.clear();
  for(TEdge *e = edges[v]; e; e = e->next)
    CHECK_EDGE(e, e->vertex)
}


void TGraphAsList::getNeighboursTo(const int &v, const int &edgeType, vector<int> &neighbours)
{
  GN_INIT_EDGETYPE
  int v2 = 0;
  for(TEdge **se = edges, **ee = edges+nVertices; se != ee; v2++, se++)
    for(TEdge *e = *se; e && (e->vertex <=v); e = e->next)
      CHECK_EDGE_TO(e)
}

#undef CHECK_EDGE
#undef CHECK_EDGE_TO


TGraphAsTree::TEdge *TGraphAsTree::createEdge(const int &vertex) const
{
  TEdge *newedge = (TEdge *)malloc(sizeof(TEdge) + (nEdgeTypes-1)*sizeof(double));
  newedge->vertex = vertex;
  newedge->left = newedge->right = NULL;
  double *w = &newedge->weights;
  for(int i = nEdgeTypes; i--; DISCONNECT(*w++));
  return newedge;
}


TGraphAsTree::TEdge::~TEdge()
{
  if (left)
    delete left;
  if (right)
    delete right;
}

TGraphAsTree::TGraphAsTree(const int &nVert, const int &nEdge, const bool dir)
: TGraph(nVert, nEdge, dir),
  edges(new TEdge *[nVert])
{
  TEdge **e = edges;
  for(int i = nVert; i--; *e++ = NULL);
}


TGraphAsTree::~TGraphAsTree()
{