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