/*------------------------------------------------------------\
|                                                             |
| Tool    :                  systemcass                       |
|                                                             |
| File    :                 graph.h                           |
|                                                             |
| Author  :                 Pétrot Frédéric                   |
|                           Taktak Sami                       |
|                           Buchmann Richard                  |
|                                                             |
| Date    :                   09_07_2004                      |
|                                                             |
\------------------------------------------------------------*/
#ifndef __GRAPH_H__
#define __GRAPH_H__

#include "sc_fwd.h"
#include <vector>

/* Graph.h: translation of a netlist into a Stanford Graphbase graph.
 * This structure is more natural than the bipartite graph for many
 * algorithms that consider the relationship between components
 * globally, not on a connectors per connector basis.
 * It is very much inspired from Don Knuth Stanford Graph Base, but 
 * is a real simplification. */

enum vertex_type {
   CONNECTOR = 0x0, INSTANCE = 0x4, STRONG_COMPONENT = 0x8
};

#define KEEP_ARC 240898

typedef union {
   struct vertex_struct *V;
   struct arc_struct *A;
   struct graph_struct *G;
   char *S;
   long I;
} util;

typedef struct vertex_struct {
  struct arc_struct *arcs;
	union {
		void             *data;
	};
  util u, v, w, x, y, z;
} Vertex;

typedef struct arc_struct {
   struct vertex_struct *tip;
   struct arc_struct *next;
   long len;
   util a, b;
} Arc;

#define ID_FIELD_SIZE 161
typedef struct graph_struct {
   Vertex *vertices;
   long n;
   long m;
   char *id;
   util uu, vv, ww, xx, yy, zz;
} Graph;

extern Graph *gb_new_graph(int n);
extern void new_arc(Vertex *u, Vertex *v);

typedef std::vector<void *> component_list_t;
typedef std::vector<component_list_t *> strong_component_list_t;
extern strong_component_list_t *strong_component(Graph *g);

extern bool                    has_cycle   (const strong_component_list_t&);
#if 0
extern const component_list_t* get_cycle   (const strong_component_list_t&);
extern void                    print_cycle (std::ostream&,const component_list_t*);
#endif

#endif /* __GRAPH_H__ */