| 1 | /*------------------------------------------------------------\ |
|---|
| 2 | | | |
|---|
| 3 | | Tool : systemcass | |
|---|
| 4 | | | |
|---|
| 5 | | File : graph.h | |
|---|
| 6 | | | |
|---|
| 7 | | Author : Pétrot Frédéric | |
|---|
| 8 | | Taktak Sami | |
|---|
| 9 | | Buchmann Richard | |
|---|
| 10 | | | |
|---|
| 11 | | Date : 09_07_2004 | |
|---|
| 12 | | | |
|---|
| 13 | \------------------------------------------------------------*/ |
|---|
| 14 | #ifndef __GRAPH_H__ |
|---|
| 15 | #define __GRAPH_H__ |
|---|
| 16 | |
|---|
| 17 | #include "sc_fwd.h" |
|---|
| 18 | #include <vector> |
|---|
| 19 | |
|---|
| 20 | /* Graph.h: translation of a netlist into a Stanford Graphbase graph. |
|---|
| 21 | * This structure is more natural than the bipartite graph for many |
|---|
| 22 | * algorithms that consider the relationship between components |
|---|
| 23 | * globally, not on a connectors per connector basis. |
|---|
| 24 | * It is very much inspired from Don Knuth Stanford Graph Base, but |
|---|
| 25 | * is a real simplification. */ |
|---|
| 26 | |
|---|
| 27 | enum vertex_type { |
|---|
| 28 | CONNECTOR = 0x0, INSTANCE = 0x4, STRONG_COMPONENT = 0x8 |
|---|
| 29 | }; |
|---|
| 30 | |
|---|
| 31 | #define KEEP_ARC 240898 |
|---|
| 32 | |
|---|
| 33 | typedef union { |
|---|
| 34 | struct vertex_struct *V; |
|---|
| 35 | struct arc_struct *A; |
|---|
| 36 | struct graph_struct *G; |
|---|
| 37 | char *S; |
|---|
| 38 | long I; |
|---|
| 39 | } util; |
|---|
| 40 | |
|---|
| 41 | typedef struct vertex_struct { |
|---|
| 42 | struct arc_struct *arcs; |
|---|
| 43 | union { |
|---|
| 44 | void *data; |
|---|
| 45 | }; |
|---|
| 46 | util u, v, w, x, y, z; |
|---|
| 47 | } Vertex; |
|---|
| 48 | |
|---|
| 49 | typedef struct arc_struct { |
|---|
| 50 | struct vertex_struct *tip; |
|---|
| 51 | struct arc_struct *next; |
|---|
| 52 | long len; |
|---|
| 53 | util a, b; |
|---|
| 54 | } Arc; |
|---|
| 55 | |
|---|
| 56 | #define ID_FIELD_SIZE 161 |
|---|
| 57 | typedef struct graph_struct { |
|---|
| 58 | Vertex *vertices; |
|---|
| 59 | long n; |
|---|
| 60 | long m; |
|---|
| 61 | char *id; |
|---|
| 62 | util uu, vv, ww, xx, yy, zz; |
|---|
| 63 | } Graph; |
|---|
| 64 | |
|---|
| 65 | extern Graph *gb_new_graph(int n); |
|---|
| 66 | extern void new_arc(Vertex *u, Vertex *v); |
|---|
| 67 | |
|---|
| 68 | typedef std::vector<void *> component_list_t; |
|---|
| 69 | typedef std::vector<component_list_t *> strong_component_list_t; |
|---|
| 70 | extern strong_component_list_t *strong_component(Graph *g); |
|---|
| 71 | |
|---|
| 72 | extern bool has_cycle (const strong_component_list_t&); |
|---|
| 73 | #if 0 |
|---|
| 74 | extern const component_list_t* get_cycle (const strong_component_list_t&); |
|---|
| 75 | extern void print_cycle (std::ostream&,const component_list_t*); |
|---|
| 76 | #endif |
|---|
| 77 | |
|---|
| 78 | #endif /* __GRAPH_H__ */ |
|---|
