checkcycles.cc

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

// ################################################################################
//
// name:          computeCounts.cc
//
// author:        Martin Pelikan
//
// purpose:       a function that checks what edges would create cycles with a
//                newly added edge and assigns negative gain for the corresponding
//                edge additions
//
// last modified: February 1999
//
// ################################################################################

#include "checkCycles.h"
#include "graph.h"

// ================================================================================
//
// name:          checkCycles
//
// function:      sets the gain for all edge additions creating a cycle with a
//                recently added edge to -1
//
// parameters:    newFrom......starting point of a recently added edge
//                newTo........ending point of a recently added edge
//                gain.........the matrix of gains for edge additions to update
//                G............the current network
//
// returns:       (int) 0
//
// ================================================================================

int checkCycles(int newFrom, int newTo, float **gain, AcyclicOrientedGraph *G)
{
  int k,l,n;

  // stores the number of nodes in a variable

  n = G->size();

  // set the gains for all edges that create cycles with newly added edge to -1

  for (k=0; k<n; k++)                 	
    for (l=0; l<k; l++)
      {
	// does the new edge forbid creating an edge k,l by means of a path that might create a cycle with this?
	
	if ((gain[k][l]>0)&&(G->existsPath(l,newFrom)&&(G->existsPath(newTo,k))))
	  gain[k][l]=-1;
	
	// does the new edge forbid creating an edge l,k by means of a path that might create a cycle with this?
	
	if ((gain[l][k]>0)&&(G->existsPath(k,newFrom)&&(G->existsPath(newTo,l))))
	  gain[l][k]=-1;
      }
  
  return 0;
};