source: sources/src/graph.cc @ 16

/*------------------------------------------------------------\
|                                                             |
| Tool    :                  systemcass                       |
|                                                             |
| File    :                 graph.cc                          |
|                                                             |
| Author  :                 Petrot Frédéric                   |
|                           Taktak Sami                       |
|                           Buchmann Richard                  |
|                                                             |
| Date    :                   09_07_2004                      |
|                                                             |
\------------------------------------------------------------*/

/* 
 * This file is part of the Disydent Project
 * Copyright (C) Laboratoire LIP6 - Département ASIM
 * Universite Pierre et Marie Curie
 * 
 * Home page          : http://www-asim.lip6.fr/disydent
 * E-mail             : mailto:richard.buchmann@lip6.fr
 * 
 * This library is free software; you  can redistribute it and/or modify it
 * under the terms  of the GNU Library General Public  License as published
 * by the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * Disydent 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 the GNU C Library; see the  file COPYING. If not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 * $Log: graph.cc,v $
 * Revision 1.10  2006/06/12 14:02:04  buchmann
 * - Now sort transition and generation functions by fonction pointer
 *   (Thank to Nicolas Pouillon)
 * - Add Nicolas Pouillon as contributor into splash screen
 * - Rename files and classes from "dependancy" to "dependency".
 * - Add some references to bibliography file
 * - Add licence note to every files
 * - Rename "module graph" to "process graph"
 * - Now dump module graph when using --t option and CASS scheduling at the same
 *   time
 *
 * Bug fixes :
 * - check user time ( != 0) before computing simulation performance
 * - Remove reinterpret_cast (for pending write) because of unexpected results
 * - Add ASSERT in trace functions
 *
 * Revision 1.9  2005/10/12 10:00:59  buchmann
 * Bug fix :
 * - test to avoid malloc(0)
 *
 * Remove :
 * - unused variable
 *
 * Revision 1.8  2005/09/14 14:08:24  buchmann
 * Add Werror flag to compile the debug library.
 * Split sc_clock implementation from sc_port to sc_clock.
 * Add a helper message to write mealy functions avoiding combinational cycle.
 *
 * Bug fix :
 * - cvs rules is no longer circular
 * - bit2string
 * - port binding (sc_in to sc_out)
 * - error message from FSM rules checker
 * - sc_time copy operator
 *
 * Code cleaning :
 * - remove duplicated code (entity.cc and sc_port.cc)
 * - remove duplicated declarations (internal_ext.h and internal.h)
 *
 * Revision 1.7  2005/03/29 14:04:30  buchmann
 * Bug fix :
 * -  Evaluation order of Mealy functions
 *
 * Print more informations when DUMP_STAGE is defined.
 *
 * Revision 1.6  2005/01/20 09:15:12  buchmann
 * add following functions to sc_uint classes :
 * - operator []
 * - range (left,right)
 *
 * support to port dependancy declarations.
 * print used precompiled options in verbose mode.
 * use pedantic flag.
 * add some rules to generate documentations.
 *
 * Revision 1.5  2004/09/27 14:40:13  buchmann
 * bug fix :
 * - allow the use of user-defined structs in sc_signal/sc_in/sc_out/sc_inout
 * - use sc_dt namespace like official SystemC engine
 *
 * add :
 * - dump the signal/port/module dependancy graph in dot format
 *
 * Graph library is now splitted from the SystemCASS specific code.
 *
 */

#include <cstdio>
#include <map>

#include "graph.h"
#include "sc_sensitive.h"
#include "sc_module.h"
#include "sc_port.h"

using namespace std;

/* Sorry for that, Mr Knuth :-) */

Graph *gb_new_graph(int n)
{
Graph *g;

   g = (Graph *) malloc(sizeof(Graph));
   g->n = n;
   if (n)
   {
     g->vertices = (Vertex *) malloc(n * sizeof(Vertex));
     (void)memset(g->vertices, 0, n * sizeof(Vertex));
   } else {
     g->vertices = NULL;
   }
   return g;
}

static void gb_new_arc(Vertex *u, Vertex *v, long l)
{
Arc *a;

   a       = (Arc *) malloc(sizeof(Arc));
   a->next = u->arcs;
   u->arcs = a;
   a->tip  = v;
   a->len  = l;
}

/* end Sorry */

#define VERTEX 220898

#define type     u.I

void new_arc(Vertex *u, Vertex *v)
{
Arc *a;
#ifdef DEBUG
        if ((u == NULL) || (v == NULL))
                exit(29042004);
#endif
   for (a = u->arcs; a; a = a->next)
      if (a->tip == v)
         return;
   gb_new_arc(u, v, 0L);
}

#define rank z.I
#define parent y.V
#define untagged x.A
#define link w.V
#define min v.V

#define infinity g->n

/* strong_component: extracts and topologically sorts the strong components of
 * a graph.
 * The returned data structure is a chain_list of chain_lists.
 * The first list implicitely lists the components in order, and the pointed
 * to ones list the components contents (one or more vertices) */

extern strong_component_list_t *strong_component(Graph *g)
{
  long nn;
  Vertex *active_stack;
  Vertex *settled_stack;
  Vertex *vv;
  
  register Vertex *v;
  
  strong_component_list_t *strongcomponents = new strong_component_list_t;
        typedef std::vector<void*> void_list_t;
  void_list_t *component;

  if (g->vertices == NULL)
    return strongcomponents;

 /* Make all vertices unseen and all arcs untagged */
 for (v = g->vertices + g->n - 1; v >= g->vertices; v--) {
   v->rank = 0;
   v->untagged = v->arcs;
 }
 nn = 0;
 active_stack = settled_stack = NULL;

 for (vv = g->vertices; vv < g->vertices + g->n; vv++)
   if (vv->rank == 0) { /* vv is still unseen */
     v = vv;
     v->parent = NULL;
     
     v->rank = ++nn;
     v->link = active_stack;
     active_stack = v;
     v->min = v;
     
     do { /* Eplore one step from the current vertex v, possibly moving to another vertex 
             and calling it v */
       register Vertex *u;               /* a vertex adjacent to v */
       register Arc *a = v->untagged;    /* v's first remaining untagged arc, if any */
       if (a) {
         u = a->tip;
         v->untagged = a->next;    /* tag the arc from v to u */
         if (u->rank) {    /* we've seen u already */
           if (u->rank < v->min->rank) /* non-tree arc, jutt update v->min */
             v->min = u;
         } else {   /* u is presently unseen */
           u->parent = v; /* the arcfrom v to u is a new tree arc */
           v = u;         /* u will now be the currnt vertex */
           v->rank = ++nn;  /* make vertex v active */
           v->link = active_stack;
           active_stack = v;
           v->min = v;
         }
       } else { /* all arcs from v are tagged, so v matures */
         u = v->parent; /* prepare to backtrack in the tree */
         if (v->min == v) {
           /* Remove v and all its successors on the activestack from the tree,
              and mark them as a strong component of the graph */
           register Vertex *t; /* runs though the vertices of the new strong component */
           
           t = active_stack;
           active_stack = v->link;
           v->link = settled_stack;
           settled_stack = t; /* we've moved the top of one stack to the other */
           component = new void_list_t;
           /* singe vetex */
           if (t != v) { /* NOT singe vetex */
             while (t != v) {
               component->push_back(t->data);
               t->rank = infinity; /* now t is settled */
               t->parent = v;  /* and v represents the new strong component */
               t = t->link;
             }
           }
           component->push_back(v->data);
           strongcomponents->push_back(component);
           v->rank = infinity; /* v too is settled */
           v->parent = v; /* and represents its own strong component */
         } else /* the arc from u to v has just matured, making v->min visible from u */
           if (v->min->rank < u->min->rank) u->min = v->min;
         v = u; /* the former parent of v is the new current vertex v */
       }
     } while (v != NULL);
   }

 return strongcomponents;
}

bool 
has_cycle (const strong_component_list_t &l)
{       
        strong_component_list_t::const_iterator it;
        for (it = l.begin (); it != l.end (); ++it)
        {
                if ((*it)->size() > 1)
                        return true;
        }
        return false;
}

#if 0
const component_list_t*
get_cycle (const strong_component_list_t &l)
{       
        strong_component_list_t::const_iterator it;
        for (it = l.begin (); it != l.end (); ++it)
        {
    const component_list_t *c = *it;
                if (c->size() > 1)
                        return c;
        }
        return NULL;
}

void
print_cycle (std::ostream &o, 
             const component_list_t *c)
{
  if (c == NULL)
    return;
  component_list_t::const_iterator it;
  for (it = c->begin (); it != c->end (); ++it)
  {
    void *v = *it;
    o << hex << (int) v << " ";
  }
  o << "\n";
}
#endif