alpar@2360: /* -*- C++ -*- alpar@2360: * alpar@2360: * This file is a part of LEMON, a generic C++ optimization library alpar@2360: * alpar@2391: * Copyright (C) 2003-2007 alpar@2360: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2360: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2360: * alpar@2360: * Permission to use, modify and distribute this software is granted alpar@2360: * provided that this copyright notice appears in all copies. For alpar@2360: * precise terms see the accompanying LICENSE file. alpar@2360: * alpar@2360: * This software is provided "AS IS" with no warranty of any kind, alpar@2360: * express or implied, and with no claim as to its suitability for any alpar@2360: * purpose. alpar@2360: * alpar@2360: */ alpar@2360: alpar@2360: ///\ingroup demos alpar@2360: ///\file alpar@2367: ///\brief Demonstrating the usage of LEMON's algorithm for solving the alpar@2367: /// Constrained shortest Path Problem alpar@2360: /// alpar@2367: /// \include csp_demo.cc alpar@2360: alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: alpar@2360: alpar@2360: using namespace lemon; alpar@2360: alpar@2360: alpar@2360: int main (int, char*[]) alpar@2360: { alpar@2360: alpar@2360: typedef ListGraph Graph; alpar@2360: typedef Graph::Node Node; alpar@2360: typedef Graph::Edge Edge; alpar@2360: typedef Graph::EdgeIt EdgeIt; alpar@2360: typedef Graph::EdgeMap LengthMap; alpar@2360: alpar@2360: Graph g; alpar@2360: alpar@2360: const int N=100; alpar@2360: const int M=20000; alpar@2360: std::vector nodes; alpar@2360: std::vector edges; alpar@2360: alpar@2360: for(int i=0;i csp(g,cost,delay); alpar@2367: for(double d=0;d<2;d+=.001) alpar@2360: { alpar@2360: double lo_bo; alpar@2360: std::cout << d << ": "; alpar@2360: SimplePath r = csp.larac(nodes[0],nodes[1],d,lo_bo); alpar@2360: if(r.empty()) std::cout << "INFEASIBLE\n"; alpar@2360: else std::cout << "delay: " << csp.delay(r) alpar@2360: << " cost: " << csp.cost(r) alpar@2360: << " (lb: " << lo_bo alpar@2360: << " gap: " << csp.cost(r)-lo_bo alpar@2360: << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100 alpar@2360: << "%)" << std::endl; alpar@2360: } alpar@2360: alpar@2360: return 0; alpar@2360: }