| 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 _CNRP_DG_H |
| 17 |
#define _CNRP_DG_H |
| 18 |
|
| 19 |
/* SYMPHONY include files */ |
| 20 |
#include "sym_proto.h" |
| 21 |
#include "sym_dg.h" |
| 22 |
|
| 23 |
/* Possible scanned stati of dg_net_vertices */ |
| 24 |
#define NOT_SCANNED 0 |
| 25 |
#define SCANNED_SHRUNK 1 |
| 26 |
#define SCANNED_ALIVE 2 |
| 27 |
|
| 28 |
typedef struct DG_NET_EDGE{ |
| 29 |
struct DG_NET_VERTEX *head; |
| 30 |
struct DG_NET_VERTEX *tail; |
| 31 |
double weight; |
| 32 |
char deleted; |
| 33 |
}dg_net_edge; |
| 34 |
|
| 35 |
typedef struct DG_NET_ELIST{ |
| 36 |
struct DG_NET_ELIST *next_edge; /* next edge in the edgelist */ |
| 37 |
dg_net_edge *data; /* the data of the edge */ |
| 38 |
struct DG_NET_VERTEX *other; /* pointer to the other end of the edge*/ |
| 39 |
}dg_net_elist; |
| 40 |
|
| 41 |
typedef struct DG_NET_VERTEX{ |
| 42 |
int degree;/*contains the degree of the node in the graph*/ |
| 43 |
int orignodenum;/*the node number in the original graph*/ |
| 44 |
|
| 45 |
struct DG_NET_ELIST *first;/*points to the 1st edge in the adjacency list*/ |
| 46 |
struct DG_NET_ELIST *last; /*points to the last edge in the adjacency list*/ |
| 47 |
|
| 48 |
int snode_size; /*size of the supernode identified by this |
| 49 |
*node. makes sense only at the |
| 50 |
*identifier. 0 to start with*/ |
| 51 |
struct DG_NET_VERTEX *snode_next; /*the next node in the list of nodes |
| 52 |
*belonging to the same supernode. |
| 53 |
*NULL to start with*/ |
| 54 |
|
| 55 |
char scanned; |
| 56 |
}dg_net_vertex; |
| 57 |
|
| 58 |
typedef struct DG_NET_NETWORK{ |
| 59 |
int origvertnum; /*number of vertices in the original graph*/ |
| 60 |
int vertnum; /*number of supernodes in the graph*/ |
| 61 |
int edgenum; /*number of edges in the graph (size of 'edges'); |
| 62 |
*as edges might contain unlinked edges, the real |
| 63 |
*number of edges might be smaller!*/ |
| 64 |
dg_net_elist *adjlist; /*the array containing the adjacency lists for each |
| 65 |
*node*/ |
| 66 |
dg_net_edge *edges; /*the list of edges in the graph*/ |
| 67 |
dg_net_vertex *verts; /*the list of vertices (everything, not just |
| 68 |
*supernodes)*/ |
| 69 |
}dg_net_network; |
| 70 |
|
| 71 |
typedef struct CNRP_DG{ |
| 72 |
dg_net_network *n; |
| 73 |
}cnrp_dg; |
| 74 |
|
| 75 |
|
| 76 |
dg_net_network *dg_createnet PROTO((int vertnum, |
| 77 |
int length, int *xind, double *xval)); |
| 78 |
void dg_freenet PROTO((dg_net_network *n)); |
| 79 |
void dg_net_shrink_chains PROTO((dg_net_network *n)); |
| 80 |
void copy_network_into_graph PROTO((dg_net_network *n, dg_graph *g)); |
| 81 |
|
| 82 |
#endif |