00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef _NETWORK
00017 #define _NETWORK
00018
00019
00020 #include "sym_proto.h"
00021
00022
00023 #include "cnrp_const.h"
00024
00025 #define NOT_INTEGRAL -1
00026 #define OTHER_END(cur_edge, v) \
00027 (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0
00028
00029
00030
00031
00032
00033
00034
00035 typedef struct EDGE{
00036 int v0;
00037 int v1;
00038 int cost;
00039 double weight;
00040 #ifdef DIRECTED_X_VARS
00041 double weight1;
00042 double weight2;
00043 #endif
00044 char scanned;
00045 char tree_edge;
00046 char deleted;
00047
00048 double q;
00049 #ifdef ADD_FLOW_VARS
00050 double flow1;
00051 double flow2;
00052 #endif
00053 }edge;
00054
00055 typedef struct ELIST{
00056 struct ELIST *next_edge;
00057 struct EDGE *data;
00058 int other_end;
00059 struct VERTEX *other;
00060 }elist;
00061
00062 typedef struct VERTEX{
00063 int enodenum;
00064 int orignodenum;
00065 struct ELIST *first;
00066 struct ELIST *last;
00067 int comp;
00068
00069 char scanned;
00070 double demand;
00071 int degree;
00072 int orig_node_list_size;
00073 int *orig_node_list;
00074
00075
00076 int dfnumber;
00077 int low;
00078 char is_art_point;
00079 char deleted;
00080 double weight;
00081
00082 char orig_node_list2_size;
00083 char *orig_node_list2;
00084
00085
00086 double r;
00087 }vertex;
00088
00089 typedef struct NETWORK{
00090 int vertnum;
00091 char is_integral;
00092
00093 int edgenum;
00094 float mincut;
00095 struct ELIST *adjlist;
00096
00097 struct EDGE *edges;
00098 struct VERTEX *verts;
00099 int *compnodes;
00100 double *new_demand;
00101
00102
00103
00104 struct VERTEX **tnodes;
00105
00106 struct VERTEX **enodes;
00107 }network;
00108
00109 network *create_net PROTO((int *xind, double *xval, int edgenum, double etol,
00110 int *edges, double *demands, int vertnum));
00111 network *create_flow_net PROTO((int *xind, double *xval, int edgenum,
00112 double etol, int *edges, double *demands,
00113 int vertnum));
00114 int connected PROTO((network *n, int *compnodes, double *compdemands,
00115 int *compmembers, double *compcuts, double *compdensity));
00116 int flow_connected PROTO((network *n, int *compnodes, double *compdemands,
00117 int *compmembers, double *compcuts,
00118 double *compdensity, double etol));
00119 void free_net PROTO((network *n));
00120
00121 #endif