eg_dagsp.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_dagsp.h"

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

  int rval;
  EGmemPool_t *mem;
  EGlist_t *sort;
  EGlistNode_t *nit,
   *eit;
  EGdGraphNode_t *n;
  EGdGraphEdge_t *e;

  mem = G->mem;
  sort = EGnewList (mem);

  EGdagspInitialize (s, G, os);

  rval = EGdagspTopologicSort (G, s, sort, os, mem);
  CHECKRVAL (rval);

  for (nit = sort->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);
      EGdagspRelax (e, os);
    }
  }

  EGfreeList (sort);

  return 0;

}

void EGdagspInitialize (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);
    EGdijkstraSetFather (it->this, os, 0);
    EGdijkstraSetMarker (it->this, os, 0);
  }

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

  return;

}

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

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

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

  return;

}

/* marks: 
   
   0 untouched
   1 in list
   2 done

*/

int EGdagspTopologicSort (EGdGraph_t * G,
                          EGdGraphNode_t * s,
                          EGlist_t * sort,
                          size_t * os,
                          EGmemPool_t * mem)
{
  int rval = 0;
  EGlist_t *dfs_list;
  EGlistNode_t **it,
   *eit;
  EGdGraphNode_t *current_node;
  EGdGraphEdge_t *e;
  TEST (sort->size, "sort not empty");
  it = EGmemPoolSMalloc (mem, EGlistNode_t *, G->node_id_max);
  dfs_list = EGnewList (mem);
  current_node = s;
  EGlistPushBack (dfs_list, current_node);
  it[current_node->id] = current_node->out_edges->begin;

  while (dfs_list->size)
  {
    current_node = (EGdGraphNode_t *) (dfs_list->end->this);
    eit = it[current_node->id];

    /* skip terminated nodes and search for directed cycles */
    while (eit)
    {
      e = (EGdGraphEdge_t *) (eit->this);
      if (EGdijkstraGetMarker (e->head, os) == 1)
      {
        rval = 1;
        goto CLEANUP;
      }
      if (EGdijkstraGetMarker (e->head, os) == 0)
        break;
      eit = eit->next;
    }

    /* if current node is 'finished' */
    if (!eit)
    {
      EGlistPushHead (sort, current_node);
      EGdijkstraSetMarker (current_node, os, 2);
      EGlistErase (dfs_list, dfs_list->end, nullFree);
      continue;
    }

    /* mark the node as 'incomplete' */
    EGdijkstraSetMarker (current_node, os, 1);
    EGlistPushBack (dfs_list, e->head);
    it[e->head->id] = e->head->out_edges->begin;
    it[current_node->id] = it[current_node->id]->next;
  }

CLEANUP:
  EGmemPoolSFree (it, EGlistNode_t *, G->node_id_max, mem);
  EGfreeList (dfs_list);
  return rval;
}

---