[1] | 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__ */ |
---|