vrp_dg.h

Go to the documentation of this file.

/*===========================================================================*/
/*                                                                           */
/* This file is part of a demonstration application for use with the         */
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
/* the Vehicle Routing Problem and the Traveling Salesman Problem.           */
/*                                                                           */
/* (c) Copyright 2000-2013 Ted Ralphs. All Rights Reserved.                  */
/*                                                                           */
/* This application was developed by Ted Ralphs (ted@lehigh.edu)             */
/*                                                                           */
/* This software is licensed under the Eclipse Public License. Please see    */
/* accompanying file for terms.                                              */
/*                                                                           */
/*===========================================================================*/

#ifndef _VRP_DG_H
#define _VRP_DG_H

/* SYMPHONY include files */
#include "sym_proto.h"
#include "sym_dg.h"

/* Possible scanned stati of dg_net_vertices */
#define NOT_SCANNED    0 
#define SCANNED_SHRUNK 1
#define SCANNED_ALIVE  2

typedef struct DG_NET_EDGE{
   struct DG_NET_VERTEX *head;
   struct DG_NET_VERTEX *tail;
   double                weight;  
   char                  deleted;
}dg_net_edge;

typedef struct DG_NET_ELIST{
   struct DG_NET_ELIST  *next_edge; /* next edge in the edgelist */
   dg_net_edge          *data;      /* the data of the edge */
   struct DG_NET_VERTEX *other;     /* pointer to the other end of the edge*/
}dg_net_elist;

typedef struct DG_NET_VERTEX{
   int                  degree;/*contains the degree of the node in the graph*/
   int                  orignodenum;/*the node number in the original graph*/

   struct DG_NET_ELIST *first;/*points to the 1st edge in the adjacency list*/
   struct DG_NET_ELIST *last; /*points to the last edge in the adjacency list*/

   int                  snode_size;  /*size of the supernode identified by this
                      *node. makes sense only at the 
                      *identifier. 0 to start with*/
   struct DG_NET_VERTEX *snode_next; /*the next node in the list of nodes
                      *belonging to the same supernode.
                      *NULL to start with*/

   char                 scanned;
}dg_net_vertex;

typedef struct DG_NET_NETWORK{
   int         origvertnum; /*number of vertices in the original graph*/
   int         vertnum;     /*number of supernodes in the graph*/
   int         edgenum;     /*number of edges in the graph (size of 'edges');
                 *as edges might contain unlinked edges, the real
                 *number of edges might be smaller!*/
   dg_net_elist   *adjlist; /*the array containing the adjacency lists for each
                 *node*/
   dg_net_edge    *edges;   /*the list of edges in the graph*/
   dg_net_vertex  *verts;   /*the list of vertices (everything, not just
                 *supernodes)*/
}dg_net_network;

typedef struct VRP_DG{
   dg_net_network *n;
}vrp_dg;


dg_net_network *dg_createnet PROTO((int vertnum,
                    int length, int *xind, double *xval));
void dg_freenet PROTO((dg_net_network *n));
void dg_net_shrink_chains PROTO((dg_net_network *n));
void copy_network_into_graph PROTO((dg_net_network *n, dg_graph *g));

#endif