Debian Codegraph @

SYMPHONY/Applications/VRP/include/vrp_dg.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 _VRP_DG_H
17 #define _VRP_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 VRP_DG{
72 dg_net_network *n;
73 }vrp_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