Debian Codegraph @

SYMPHONY/Applications/VRP/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 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
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 /* VRP include files */
23 #include "vrp_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 char scanned;
41 char tree_edge;
42 char deleted;
43 /*__BEGIN_EXPERIMENTAL_SECTION__*/
44 float q;
45 int row;
46 char can_be_doubled; /* tells whether this edge can potentially be used
47 for a 1-customer route */
48 struct EDGE *other_data;
49 #ifdef COMPILE_OUR_DECOMP
50 char status;
51 #endif
52 /*___END_EXPERIMENTAL_SECTION___*/
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 /*__BEGIN_EXPERIMENTAL_SECTION__*/
61 char superlink;
62 int edgenum;
63 struct EDGE **edges;
64 /*___END_EXPERIMENTAL_SECTION___*/
65 }elist;
66
67 typedef struct VERTEX{
68 int enodenum; /* the node number in the contracted graph */
69 int orignodenum;/* the node number in the original graph */
70 struct ELIST *first; /* points to the first edge in the adjacency list */
71 struct ELIST *last; /* points to the last edge in the adjacency list */
72 int comp; /* contains the component number if the graph is
73 disconnected */
74 char scanned;
75 int demand; /* contains the demand for this node */
76 int degree; /* contains the degree of the node in the graph */
77 int orig_node_list_size;
78 int *orig_node_list; /* contains a list of the nodes that have been
79 contracted into this node to make a
80 "super node" */
81 int dfnumber;
82 int low;
83 char is_art_point;
84 char deleted;
85 /*__BEGIN_EXPERIMENTAL_SECTION__*/
86 float r;
87 /*___END_EXPERIMENTAL_SECTION___*/
88 }vertex;
89
90 typedef struct NETWORK{
91 int vertnum; /* the number of vertices in the graph */
92 char is_integral; /* indicates whether the graph is integral or
93 not */
94 int edgenum; /* the number of edges in the graph */
95 float mincut; /* the value of the current mincut */
96 struct ELIST *adjlist; /* the array containing the adajacency lists for
97 each node */
98 struct EDGE *edges; /* the list of edges in the graph */
99 struct VERTEX *verts; /* the list of vertices */
100 int *compnodes; /* number of nodes in each component */
101 double *new_demand; /* the amounts of demand for each node that gets
102 added to it when the network is contracted */
103 /*__BEGIN_EXPERIMENTAL_SECTION__*/
104 struct VERTEX **tnodes; /* a binary tree of the exiisting vertices used by
105 the min_cut routine */
106 struct VERTEX **enodes; /* a list of the nodes that still exist */
107 /*___END_EXPERIMENTAL_SECTION___*/
108 }network;
109
110 network *createnet PROTO((int *xind, double *xval, int edgenum, double etol,
111 int *edges, int *demands, int vertnum));
112 /*__BEGIN_EXPERIMENTAL_SECTION__*/
113 network *createnet2 PROTO((int *xind, double *xval, int edgenum, double etol,
114 int *edges, int *demands, int vertnum,
115 char *status));
116 /*___END_EXPERIMENTAL_SECTION___*/
117 int connected PROTO((network *n, int *compnodes, int *compdemands,
118 int *compmembers, double *compcuts, double *compdensity));
119 void free_net PROTO((network *n));
120
121 #endif