- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# /home/coin/svn-release/Blis-0.94.1/Blis/examples/VRP/VrpNetwork.h

Go to the documentation of this file.

    00001 /*===========================================================================*
    00002  * This file is part of a solver for the Vehicle Routing Problem             *
    00003  * developed using the BiCePS Linear Integer Solver (BLIS).                  *
    00004  *                                                                           *
    00005  * This solver is distributed under the Eclipse Public License as part of    *
    00006  * the COIN-OR repository (http://www.coin-or.org).                          *
    00007  *                                                                           *
    00008  * Authors: Yan Xu, Lehigh University                                        *
    00009  *          Ted Ralphs, Lehigh University                                    *
    00010  *                                                                           *
    00011  * Copyright (C) 2007 Yan Xu and Ted Ralphs.                                 *
    00012  * All Rights Reserved.                                                      *
    00013  *===========================================================================*/
    00014
    00015 #ifndef VrpNetwork_h_
    00016 #define VrpNetwork_h_
    00017
    00018 #include <vector>
    00019
    00020 #include "CoinPackedVector.hpp"
    00021 #include "VrpConstants.h"
    00022 #include "VrpVariable.h"
    00023
    00024 //#############################################################################
    00025
    00026 #define OTHER_END(cur_edge, v) \
    00027         (cur_edge->data->v0 == v) ? cur_edge->data->v1 : cur_edge->data->v0
    00028
    00029 #ifndef MIN
    00030 #define MIN(x, y) (x < y ? x : y)
    00031 #endif
    00032
    00033 #ifndef MAX
    00034 #define MAX(x, y) (x > y ? x : y)
    00035 #endif
    00036
    00037 /*-----------------------------------------------------------------------*\
    00038 | These are data tructures used in constructing the solution graph used   |
    00039 | by the cut generator to locate cuts. The graph is stored using          |
    00040 | adjacency lists                                                         |
    00041 \*-----------------------------------------------------------------------*/
    00042
    00043 typedef struct EDGE{
    00044    int v0;
    00045    int v1;
    00046    int cost;
    00047    double weight;
    00048    bool scanned;
    00049    bool tree_edge;
    00050    bool deleted;
    00051 }edge;
    00052
    00053 typedef struct ELIST{
    00054    struct ELIST  *next_edge; /* next edge in the edgelist */
    00055    struct EDGE   *data;      /* the data of the edge */
    00056    int            other_end; /* the other end of the edge */
    00057    struct VERTEX *other;
    00058 }elist;
    00059
    00060 typedef struct VERTEX{
    00061   int           enodenum;   /* the node number in the contracted graph */
    00062   int           orignodenum;/* the node number in the original graph */
    00063   struct ELIST *first; /* points to the first edge in the adjacency list */
    00064   struct ELIST *last;  /* points to the last edge in the adjacency list */
    00065   int           comp;  /* contains the component number if the graph is
    00066                           disconnected */
    00067   bool          scanned;
    00068   int           demand; /* contains the demand for this node */
    00069   int           degree; /* contains the degree of the node in the graph */
    00070   int           orig_node_list_size;
    00071   int          *orig_node_list; /* contains a list of the nodes that have been
    00072                                    contracted into this node to make a
    00073                                    "super node" */
    00074   int           dfnumber;
    00075   int           low;
    00076   bool          is_art_point;
    00077   bool          deleted;
    00078 }vertex;
    00079
    00080 class VrpNetwork{
    00081
    00082    friend class VrpModel;
    00083    friend class VrpCutGenerator;
    00084    friend class VrpSolution;
    00085
    00086  private:
    00087
    00088    int             edgenum_;     /* the number of edges in the graph */
    00089    int             maxEdgenum_;  /* the number of edges allocated */
    00090    int             vertnum_;     /* the number of vertices in the graph */
    00091    bool            isIntegral_;  /* indicates whether the graph is integral or
    00092                                     not */
    00093    int             numComps_;     /* number of components */
    00094    struct EDGE    *edges_;       /* the list of edges in the graph */
    00095    struct VERTEX  *verts_;       /* the list of vertices */
    00096    double          mincut_;      /* the value of the current mincut */
    00097    struct ELIST   *adjList_;     /* the array containing the adajacency lists
    00098                                     for each node */
    00099    int            *compNodes_;   /* number of nodes in each component */
    00100    int            *compDemands_; /* demand in each component */
    00101    double         *compCuts_;    /* weight of cprresponding cut */
    00102    int            *compMembers_; /* which component each vertex belongs to */
    00103    int            *newDemand_;   /* the amounts of demand for each node to add
    00104                                     when the network is contracted */
    00105
    00106  public:
    00107
    00108    VrpNetwork() : edgenum_(0), vertnum_(0), isIntegral_(false), mincut_(0){
    00109       adjList_ = 0;
    00110       edges_ = 0;
    00111       verts_ = 0;
    00112       compNodes_ = 0;
    00113       compDemands_ = 0;
    00114       compCuts_ = 0;
    00115       compMembers_ = 0;
    00116       newDemand_ = 0;
    00117    }
    00118
    00119    VrpNetwork(int edgenum, int vertnum);
    00120
    00121    virtual ~VrpNetwork() {
    00122       gutsOfDestructor();
    00123    }
    00124
    00125    void createNet(CoinPackedVector *sol, int *demand,
    00126                   std::vector<VrpVariable *> edgeList, double etol,
    00127                   int vertnum);
    00128
    00129    void computeCompNums(vertex *v, int parent_comp, int *num_comps,
    00130                         bool parent_is_art_point);
    00131
    00132    void depthFirstSearch(vertex *v, int *count1, int *count2);
    00133
    00134    int connected();
    00135
    00136    int biconnected();
    00137
    00138    void reduce_graph(double etol);
    00139
    00140    void gutsOfDestructor();
    00141
    00142 };
    00143
    00144 #endif