source: sources/src/graph.h @ 5

Last change on this file since 5 was 1, checked in by buchmann, 17 years ago

Initial import from CVS repository

File size: 2.4 KB
Line 
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
27enum vertex_type {
28   CONNECTOR = 0x0, INSTANCE = 0x4, STRONG_COMPONENT = 0x8
29};
30
31#define KEEP_ARC 240898
32
33typedef 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
41typedef 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
49typedef 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
57typedef 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
65extern Graph *gb_new_graph(int n);
66extern void new_arc(Vertex *u, Vertex *v);
67
68typedef std::vector<void *> component_list_t;
69typedef std::vector<component_list_t *> strong_component_list_t;
70extern strong_component_list_t *strong_component(Graph *g);
71
72extern bool                    has_cycle   (const strong_component_list_t&);
73#if 0
74extern const component_list_t* get_cycle   (const strong_component_list_t&);
75extern void                    print_cycle (std::ostream&,const component_list_t*);
76#endif
77
78#endif /* __GRAPH_H__ */
Note: See TracBrowser for help on using the repository browser.