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 (ted@lehigh.edu)             */
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
122