| 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 | |
|---|
| 74 | #endif /* __GRAPH_H__ */ |
|---|
| 75 | |
|---|
| 76 | /* |
|---|
| 77 | # Local Variables: |
|---|
| 78 | # tab-width: 4; |
|---|
| 79 | # c-basic-offset: 4; |
|---|
| 80 | # c-file-offsets:((innamespace . 0)(inline-open . 0)); |
|---|
| 81 | # indent-tabs-mode: nil; |
|---|
| 82 | # End: |
|---|
| 83 | # |
|---|
| 84 | # vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4 |
|---|
| 85 | */ |
|---|
| 86 | |
|---|
