Debian Codegraph @

SYMPHONY/Applications/CNRP/include/network.h

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* Capacitated Network Routing Problems. */
6 /* */
7 /* (c) Copyright 2000-2013 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 #ifndef _NETWORK
17 #define _NETWORK
18
19 /* SYMPHONY include files */
20 #include "sym_proto.h"
21
22 /* CNRP include files */
23 #include "cnrp_const.h"
24
25 #define NOT_INTEGRAL -1
26 #define OTHER_END(cur_edge, v) \
27 (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0
28
29 /*-----------------------------------------------------------------------*\
30 | These are data tructures used in constructing the solution graph used |
31 | by the cut generator to locate cuts. The graph is stored using |
32 | adjacency lists |
33 \*-----------------------------------------------------------------------*/
34
35 typedef struct EDGE{
36 int v0;
37 int v1;
38 int cost;
39 double weight;
40 #ifdef DIRECTED_X_VARS
41 double weight1;
42 double weight2;
43 #endif
44 char scanned;
45 char tree_edge;
46 char deleted;
47 /*For minimum cut*/
48 double q;
49 #ifdef ADD_FLOW_VARS
50 double flow1;
51 double flow2;
52 #endif
53 }edge;
54
55 typedef struct ELIST{
56 struct ELIST *next_edge; /* next edge in the edgelist */
57 struct EDGE *data; /* the data of the edge */
58 int other_end; /* the other end of the edge */
59 struct VERTEX *other;
60 }elist;
61
62 typedef struct VERTEX{
63 int enodenum; /* the node number in the contracted graph */
64 int orignodenum;/* the node number in the original graph */
65 struct ELIST *first; /* points to the first edge in the adjacency list */
66 struct ELIST *last; /* points to the last edge in the adjacency list */
67 int comp; /* contains the component number if the graph is
68 disconnected */
69 char scanned;
70 double demand; /* contains the demand for this node */
71 int degree; /* contains the degree of the node in the graph */
72 int orig_node_list_size;
73 int *orig_node_list; /* contains a list of the nodes that have been
74 contracted into this node to make a
75 "super node" */
76 int dfnumber;
77 int low;
78 char is_art_point;
79 char deleted;
80 double weight; /*For contracting the graph*/
81 /*For minimum cut*/
82 char orig_node_list2_size;
83 char *orig_node_list2; /* contains a list of the nodes that have been
84 contracted into this node to make a
85 "super node" */
86 double r;
87 }vertex;
88
89 typedef struct NETWORK{
90 int vertnum; /* the number of vertices in the graph */
91 char is_integral; /* indicates whether the graph is integral or
92 not */
93 int edgenum; /* the number of edges in the graph */
94 float mincut; /* the value of the current mincut */
95 struct ELIST *adjlist; /* the array containing the adajacency lists for
96 each node */
97 struct EDGE *edges; /* the list of edges in the graph */
98 struct VERTEX *verts; /* the list of vertices */
99 int *compnodes; /* number of nodes in each component */
100 double *new_demand; /* the amounts of demand for each node that gets
101 added to it when the network is contracted */
102
103 /*For minimum cut algorithm*/
104 struct VERTEX **tnodes; /*a binary tree of the existing vertices used by the
105 min_cut routine*/
106 struct VERTEX **enodes; /*a list of the nodes that still exist*/
107 }network;
108
109 network *create_net PROTO((int *xind, double *xval, int edgenum, double etol,
110 int *edges, double *demands, int vertnum));
111 network *create_flow_net PROTO((int *xind, double *xval, int edgenum,
112 double etol, int *edges, double *demands,
113 int vertnum));
114 int connected PROTO((network *n, int *compnodes, double *compdemands,
115 int *compmembers, double *compcuts, double *compdensity));
116 int flow_connected PROTO((network *n, int *compnodes, double *compdemands,
117 int *compmembers, double *compcuts,
118 double *compdensity, double etol));
119 void free_net PROTO((network *n));
120
121 #endif