00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* Capacitated Network Routing Problems. */ 00006 /* */ 00007 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 #ifndef _CNRP_DG_H 00017 #define _CNRP_DG_H 00018 00019 /* SYMPHONY include files */ 00020 #include "sym_proto.h" 00021 #include "sym_dg.h" 00022 00023 /* Possible scanned stati of dg_net_vertices */ 00024 #define NOT_SCANNED 0 00025 #define SCANNED_SHRUNK 1 00026 #define SCANNED_ALIVE 2 00027 00028 typedef struct DG_NET_EDGE{ 00029 struct DG_NET_VERTEX *head; 00030 struct DG_NET_VERTEX *tail; 00031 double weight; 00032 char deleted; 00033 }dg_net_edge; 00034 00035 typedef struct DG_NET_ELIST{ 00036 struct DG_NET_ELIST *next_edge; /* next edge in the edgelist */ 00037 dg_net_edge *data; /* the data of the edge */ 00038 struct DG_NET_VERTEX *other; /* pointer to the other end of the edge*/ 00039 }dg_net_elist; 00040 00041 typedef struct DG_NET_VERTEX{ 00042 int degree;/*contains the degree of the node in the graph*/ 00043 int orignodenum;/*the node number in the original graph*/ 00044 00045 struct DG_NET_ELIST *first;/*points to the 1st edge in the adjacency list*/ 00046 struct DG_NET_ELIST *last; /*points to the last edge in the adjacency list*/ 00047 00048 int snode_size; /*size of the supernode identified by this 00049 *node. makes sense only at the 00050 *identifier. 0 to start with*/ 00051 struct DG_NET_VERTEX *snode_next; /*the next node in the list of nodes 00052 *belonging to the same supernode. 00053 *NULL to start with*/ 00054 00055 char scanned; 00056 }dg_net_vertex; 00057 00058 typedef struct DG_NET_NETWORK{ 00059 int origvertnum; /*number of vertices in the original graph*/ 00060 int vertnum; /*number of supernodes in the graph*/ 00061 int edgenum; /*number of edges in the graph (size of 'edges'); 00062 *as edges might contain unlinked edges, the real 00063 *number of edges might be smaller!*/ 00064 dg_net_elist *adjlist; /*the array containing the adjacency lists for each 00065 *node*/ 00066 dg_net_edge *edges; /*the list of edges in the graph*/ 00067 dg_net_vertex *verts; /*the list of vertices (everything, not just 00068 *supernodes)*/ 00069 }dg_net_network; 00070 00071 typedef struct CNRP_DG{ 00072 dg_net_network *n; 00073 }cnrp_dg; 00074 00075 00076 dg_net_network *dg_createnet PROTO((int vertnum, 00077 int length, int *xind, double *xval)); 00078 void dg_freenet PROTO((dg_net_network *n)); 00079 void dg_net_shrink_chains PROTO((dg_net_network *n)); 00080 void copy_network_into_graph PROTO((dg_net_network *n, dg_graph *g)); 00081 00082 #endif
1.4.7