eg_bellford.c

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
#include "eg_bellford.h"

int EGbellFord (EGdGraphNode_t * s,
                size_t * os,
                EGdGraph_t * G)
{

  unsigned int i;
  EGlistNode_t *nit,
   *eit;
  EGdGraphNode_t *n;
  EGdGraphEdge_t *e;

  EGbellFordInitialize (s, G, os);

  for (i = 0; i < G->nodes->size; i++)
    for (nit = G->nodes->begin; nit; nit = nit->next)
    {
      n = (EGdGraphNode_t *) (nit->this);
      for (eit = n->out_edges->begin; eit; eit = eit->next)
      {
        e = (EGdGraphEdge_t *) (eit->this);
        EGbellFordRelax (e, os);
      }
    }

  return EGbellFordIsNegativeCycle (G, os);

}

int EGbellFordFast (EGdGraphNode_t * s,
                    EGdijkstraCost_t ubound,
                    size_t * os,
                    EGdGraph_t * G)
{

  unsigned int i;
  EGlistNode_t *nit,
   *eit;
  EGdGraphNode_t *n;
  EGdGraphEdge_t *e;

  EGbellFordInitialize (s, G, os);

  for (i = 0; i < G->nodes->size; i++)
    for (nit = G->nodes->begin; nit; nit = nit->next)
    {
      n = (EGdGraphNode_t *) (nit->this);
      for (eit = n->out_edges->begin; eit; eit = eit->next)
      {
        e = (EGdGraphEdge_t *) (eit->this);
        EGbellFordRelax (e, os);
      }
    }

  return EGbellFordIsNegativeCycle (G, os);

}

void EGbellFordInitialize (EGdGraphNode_t * s,
                           EGdGraph_t * G,
                           size_t * os)
{

  EGlistNode_t *it;

  for (it = G->nodes->begin; it; it = it->next)
  {
    EGdijkstraSetDist (it->this, os, EG_DIJKSTRA_COST_MAX);
    EGdijkstraSetNdist (it->this, os, INT_MAX);
    EGdijkstraSetFather (it->this, os, 0);
  }

  EGdijkstraSetDist (s, os, EGdijkstraToCost (0.0));
  EGdijkstraSetNdist (s, os, 0);

  return;

}

void EGbellFordRelax (EGdGraphEdge_t * e,
                      size_t * os)
{

  EGdijkstraCost_t relax =
    EGdijkstraGetDist (e->tail, os) + EGdijkstraGetEdgeLength (e, os);
  int ndist = EGdijkstraGetNdist (e->tail, os) + 1;

  if (EGdijkstraCostIsLess (relax, EGdijkstraGetDist (e->head, os)))
  {
    EGdijkstraSetNdist (e->head, os, ndist);
    EGdijkstraSetDist (e->head, os, relax);
    EGdijkstraSetFather (e->head, os, e);
  }

  return;

}

int EGbellFordIsNegativeCycle (EGdGraph_t * G,
                               size_t * os)
{

  EGdGraphNode_t *n;
  EGdGraphEdge_t *e;
  EGlistNode_t *nit,
   *eit;

  for (nit = G->nodes->begin; nit; nit = nit->next)
  {
    n = (EGdGraphNode_t *) (nit->this);
    for (eit = n->out_edges->begin; eit; eit = eit->next)
    {
      e = (EGdGraphEdge_t *) (eit->this);

      EGdijkstraCost_t lhs =
        EGdijkstraGetDist (e->tail, os) + EGdijkstraGetEdgeLength (e, os);

      if (EGdijkstraCostIsLess (lhs, EGdijkstraGetDist (e->head, os)))
        return 1;
    }
  }

  return 0;

}

---