graph.cc

来自「PostsBayesian Optimization Algorithm wit」· CC 代码 · 共 495 行

// ################################################################################
//
// name:          graph.cc      
//
// author:        Martin Pelikan
//
// purpose:       the definition of classes OrientedGraph and AcyclicOrientedGraph
//                for manipulation with oriented graphs
//
// last modified: February 1999
//
// ################################################################################

#include <stdlib.h>
#include <stdio.h>

#include "graph.h"
#include "memalloc.h"
#include "stack.h"
#include "utils.h"

//==========================================================
//==========================================================
//==========================================================

OrientedGraph::OrientedGraph(int n)
{
  int i;

  // set the number of vertices

  N=n;
  N2=N*N;

  // allocate memory for coincidence, path, and parentList matrices

  coincidence = (char**) Calloc(N,sizeof(char*));
  path = (char**) Calloc(N,sizeof(char*));
  parentList = (int**) Calloc(N,sizeof(int*));

  for (i=0; i<N; i++)
    {
      coincidence[i] = (char*) Calloc(N,sizeof(char));
      path[i]        = (char*) Calloc(N,sizeof(char));
      parentList[i]  = (int*) Calloc(N,sizeof(int));
    }

  // allocate memory for the number of incoming and outcoming edges

  numIn = (int*) Calloc(N,sizeof(int));
  numOut = (int*) Calloc(N,sizeof(int));

  // allocate memory for vertex-marks

  mark = (int*) Calloc(n,sizeof(int));

  // set this graph to an empy graph

  removeAllEdges();

  // unmark all vertices

  removeAllMarks();
};

//==========================================================

OrientedGraph::~OrientedGraph()
{
  int i;

  // free the memory used by coincidence, path, and parentList matrices

  for (i=0; i<N; i++)
    {
      Free(coincidence[i]);
      Free(path[i]);
      Free(parentList[i]);
    }

  Free(coincidence);
  Free(path);
  Free(parentList);

  // free the memory used by numInt and numOut arrays

  Free(numIn);
  Free(numOut);

  // free the memory used by vertex-marks

  Free(mark);
};

//==========================================================

int OrientedGraph::size()
{
  return N;
}

//==========================================================

int OrientedGraph::addEdge(int i, int j)
{
  register int k,l;

  // is the edge already present?

  if (coincidence[i][j])
     return SUCCESS;

  // connect the vertices and update the list of parents

  coincidence[i][j]=CONNECTED;
  parentList[j][numIn[j]]=i;
  numOut[i]++;
  numIn[j]++;
  path[i][j]=CONNECTED;

  // update the path matrix

  for (k=0; k<N; k++)
  if (path[k][i])
     for (l=0; l<N; l++)
         if ((l!=k)&&(path[j][l]))
            path[k][l]=CONNECTED;

  return SUCCESS;
};

//==========================================================

int OrientedGraph::removeEdge(int i, int j)
{
  int k;
  register int l,m;
  char added;
  IntStack *from,*to,*from2,*to2;

  // is the edge present?

  if (!coincidence[i][j])
     return SUCCESS;

  // initialize stacks (needed later)

  from  = new IntStack(N2);
  to    = new IntStack(N2);
  from2 = new IntStack(N2);
  to2   = new IntStack(N2);

  // remove the edge

  coincidence[i][j]=NOT_CONNECTED;
  numOut[i]--;
  numIn[j]--;

  // update the list of parents

  for (k=0; k<=numIn[j]; k++)
    if (parentList[j][k]==i)
      if (k<numIn[j])
	parentList[j][k]=parentList[j][numIn[j]];

  // update the path matrix

  // a) remove all paths that could possibly be wrong

  for (k=0; k<N; k++)
    if (path[k][i])
      for (l=0; l<N; l++)
	if ((l!=k)&&(!coincidence[k][l])&&(path[j][l]))
	  {
	    path[k][l]=0;
	    from->push(k);
	    to->push(l);
	  }

  // b) add all paths that were potentially removed incorrectly

  do
    {
      added=0;

      while (from->notEmpty())
	{
	  k=from->pop();
	  l=to->pop();
	  
	  for (m=0; m<N; m++)
	    if ((path[k][m])&&(path[m][l]))
	      {
		path[k][l]=CONNECTED;
		added=1;
	      }

	  if (!path[k][l])
	    {
	      from2->push(k);
	      to2->push(l);
	    }
	}

      // swap stacks

      swapPointers((void**) &from, (void**) &from2);
      swapPointers((void**) &to, (void**) &to2);

    } while (added);

  // free used stacks

  delete from;
  delete to;
  delete from2;
  delete to2;

  // get back

  return SUCCESS;
};

//==========================================================

int OrientedGraph::reverseEdge(int i, int j)
{
  if (canReverseEdge(i,j))
    {
      removeEdge(i,j);
      return addEdge(j,i);
    }
  else
    return FAIL;
}

//==========================================================

int OrientedGraph::canReverseEdge(int i, int j)
{
  return connected(i,j);
}

//==========================================================

int OrientedGraph::removeAllEdges()
{
  for (int i=0; i<N; i++)
  {
    path[i][i]=CONNECTED;
    numIn[i]=0;
    numOut[i]=0;
    for (int j=0; j<i; j++)
      coincidence[i][j]=coincidence[j][i]=path[i][j]=path[j][i]=NOT_CONNECTED;
  }

  return SUCCESS;
}

//==========================================================

int OrientedGraph::setMark(int i, int val)
{
  mark[i]=val;
  return SUCCESS;
};

//==========================================================

int OrientedGraph::removeMark(int i)
{
  mark[i]=0;
  return SUCCESS;
}

//==========================================================

int OrientedGraph::removeAllMarks()
{
  register int i;

  for (i=0; i<N; i++)
    mark[i]=0;

  return SUCCESS;
}

//==========================================================

int OrientedGraph::setAllMarks(int val)
{
  register int i;
  
  for (i=0; i<N; i++)
    mark[i]=val;

  return SUCCESS;
}

//==========================================================

int OrientedGraph::connected(int i, int j)
{
  return (coincidence[i][j]);
};

//==========================================================

int OrientedGraph::notConnected(int i, int j)
{
  return (coincidence[i][j]);
};

//==========================================================

int OrientedGraph::existsPath(int i, int j)
{
  return (path[i][j]);
};

//==========================================================

int OrientedGraph::getNumIn(int i)
{
  return numIn[i];
}

//==========================================================

int OrientedGraph::getNumOut(int i)
{
  return numOut[i];
}

//==========================================================

int OrientedGraph::getMark(int i)
{
  return mark[i];
};

//==========================================================

int OrientedGraph::getNumberOfVertices()
{
  return N;
}

//==========================================================

int *OrientedGraph::getParentList(int i)
{
  return parentList[i];
}

//==========================================================

int  OrientedGraph::printCoincidenceMatrix(FILE *out)
{
  int i,j;

  fprintf(out,"coincidenceMatrix\n");
  for (i=0; i<N; i++)
    {
      for (j=0; j<N; j++)
	fprintf(out,"%u ",coincidence[i][j]);
      fprintf(out,"\n");
    }
  
  return SUCCESS;
}

//==========================================================

int  OrientedGraph::printPathMatrix(FILE *out)
{
  int i,j;

  fprintf(out,"pathMatrix\n");
  for (i=0; i<N; i++)
    {
      for (j=0; j<N; j++)
	fprintf(out,"%u ",path[i][j]);
      fprintf(out,"\n");
    }
  
  return SUCCESS;
}

//==========================================================

int  OrientedGraph::printNumInArray(FILE *out)
{
  int i,j;

  fprintf(out,"numIn\n");
  for (i=0; i<N; i++)
    {
      fprintf(out,"%u (",numIn[i]);
      for (j=0; j<numIn[i]; j++)
	fprintf(out,"%u ",parentList[i][j]);
      fprintf(out,")");
    }

  fprintf(out,"\n");

  return SUCCESS;
}

//==========================================================

int  OrientedGraph::printNumOutArray(FILE *out)
{
  int i;

  fprintf(out,"numOut\n");
  for (i=0; i<N; i++)
    fprintf(out,"%u ",numOut[i]);
  fprintf(out,"\n");

  return SUCCESS;
}

//==========================================================
//==========================================================
//==========================================================


AcyclicOrientedGraph::AcyclicOrientedGraph(int n):OrientedGraph(n)
{
}

//==========================================================

AcyclicOrientedGraph::~AcyclicOrientedGraph()
{
}

//==========================================================

AcyclicOrientedGraph::addEdge(int i, int j)
{
  if (canAddEdge(i,j))
    return OrientedGraph::addEdge(i,j);
  else
    return FAIL;
}

//==========================================================

AcyclicOrientedGraph::canAddEdge(int i, int j)
{
  return (!existsPath(j,i))&&(!connected(i,j));
}

//==========================================================

int AcyclicOrientedGraph::reverseEdge(int i, int j)
{
  if (connected(i,j))
  {
    removeEdge(i,j);

    if (addEdge(j,i))
      return SUCCESS;
    else
      {
        addEdge(i,j);
	return FAIL;
      }
  }
  else
    return FAIL;
}

//==========================================================

int AcyclicOrientedGraph::canReverseEdge(int i, int j)
{
  int result;

  if (connected(i,j))
    {
      removeEdge(i,j);
      result = (!existsPath(i,j));
      addEdge(i,j);

      return result;
    }
  else
    return FAIL;
}

//==========================================================