RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * 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.

 *

 */

#ifndef LEMON_SUURBALLE_H

#define LEMON_SUURBALLE_H

///\ingroup shortest_path

///\file

///\brief An algorithm for finding arc-disjoint paths between two

/// nodes having minimum total length.

#include <vector>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

namespace lemon {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  ///

  /// \warning Length values should be \e non-negative \e integers.

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

             typename LEN = typename GR::template ArcMap<int> >

#endif

  class Suurballe

  {

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef ConstMap<Arc, int> ConstArcMap;

    typedef typename GR::template NodeMap<Arc> PredMap;

  public:

    /// The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// The type of the length map.

    typedef LEN LengthMap;

    /// The type of the lengths.

    typedef typename LengthMap::Value Length;

    /// The type of the flow map.

    typedef typename Digraph::template ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef typename Digraph::template NodeMap<Length> PotentialMap;

    /// The type of the path structures.

  private:

    class ResidualDijkstra

    {

      typedef typename Digraph::template NodeMap<int> HeapCrossRef;

      typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      // The digraph the algorithm runs on

      const Digraph &_graph;

      // The main maps

      const FlowMap &_flow;

      const LengthMap &_length;

      PotentialMap &_potential;

      // The distance map

      PotentialMap _dist;

      // The pred arc map

      PredMap &_pred;

      // The processed (i.e. permanently labeled) nodes

      std::vector<Node> _proc_nodes;

      Node _s;

      Node _t;

    public:

      /// Constructor.

                        const FlowMap &flow,

                        const LengthMap &length,

                        PotentialMap &potential,

                        PredMap &pred,

                        Node s, Node t ) :

      /// \brief Run the algorithm. It returns \c true if a path is found

      /// from the source node to the target node.

      bool run() {

        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

        Heap heap(heap_cross_ref);

        heap.push(_s, 0);

        _pred[_s] = INVALID;

        _proc_nodes.clear();

        // Process nodes

        while (!heap.empty() && heap.top() != _t) {

          Node u = heap.top(), v;

          Length d = heap.prio() + _potential[u], nd;

          _dist[u] = heap.prio();

          heap.pop();

          _proc_nodes.push_back(u);

          // Traverse outgoing arcs

          for (OutArcIt e(_graph, u); e != INVALID; ++e) {

            if (_flow[e] == 0) {

              v = _graph.target(e);

              switch(heap.state(v)) {

              case Heap::PRE_HEAP:

                heap.push(v, d + _length[e] - _potential[v]);

                _pred[v] = e;

                break;

              case Heap::IN_HEAP:

                nd = d + _length[e] - _potential[v];

                if (nd < heap[v]) {

                  heap.decrease(v, nd);

                  _pred[v] = e;

                }

                break;

              case Heap::POST_HEAP:

                break;

              }

            }

          }

          // Traverse incoming arcs

          for (InArcIt e(_graph, u); e != INVALID; ++e) {

            if (_flow[e] == 1) {

              v = _graph.source(e);

              switch(heap.state(v)) {

              case Heap::PRE_HEAP:

                heap.push(v, d - _length[e] - _potential[v]);

                _pred[v] = e;

                break;

              case Heap::IN_HEAP:

                nd = d - _length[e] - _potential[v];

                if (nd < heap[v]) {

                  heap.decrease(v, nd);

                  _pred[v] = e;

                }

                break;

              case Heap::POST_HEAP:

                break;

              }

            }

          }

        }

        if (heap.empty()) return false;

        // Update potentials of processed nodes

        Length t_dist = heap.prio();

        for (int i = 0; i < int(_proc_nodes.size()); ++i)

          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;

        return true;

      }

    }; //class ResidualDijkstra

  private:

    // The digraph the algorithm runs on

    const Digraph &_graph;

    // The length map

    const LengthMap &_length;

    // Arc map of the current flow

    FlowMap *_flow;

    bool _local_flow;

    // Node map of the current potentials

    PotentialMap *_potential;

    bool _local_potential;

    // The source node

    Node _source;

    // The target node

    Node _target;

    // Container to store the found paths

    std::vector< SimplePath<Digraph> > paths;

    int _path_num;

    // The pred arc map

    PredMap _pred;

    // Implementation of the Dijkstra algorithm for finding augmenting

    // shortest paths in the residual network

    ResidualDijkstra *_dijkstra;

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param length The length (cost) values of the arcs.

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

      delete _dijkstra;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    ///

    ///

    /// \return <tt>(*this)</tt>

    Suurballe& flowMap(FlowMap &map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }

      _flow = ↦

      return *this;

    }

    /// \brief Set the potential map.

    ///

    /// This function sets the potential map.

    ///

    ///

    /// \return <tt>(*this)</tt>

    Suurballe& potentialMap(PotentialMap &map) {

      if (_local_potential) {

        delete _potential;

        _local_potential = false;

      }

      _potential = ↦

      return *this;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call the run()

    /// function.

    /// \n

    /// If you only need the flow that is the union of the found

    /// arc-disjoint paths, you may call init() and findFlow().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    ///

    /// \param k The number of paths to be found.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    /// \c s to \c t in the digraph. Otherwise it returns the number of

    /// arc-disjoint paths found.

    ///

    /// \code

    ///   s.findPaths();

    /// \endcode

      findPaths();

      return _path_num;

    }

    /// \brief Initialize the algorithm.

    ///

    /// This function initializes the algorithm.

      // Initialize maps

      if (!_flow) {

        _flow = new FlowMap(_graph);

        _local_flow = true;

      }

      if (!_potential) {

        _potential = new PotentialMap(_graph);

        _local_potential = true;

      }

      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;

      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;

    }

    ///

    /// This function executes the successive shortest path algorithm to

    /// arc-disjoint paths.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    ///

    /// \pre \ref init() must be called before using this function.

      // Find shortest paths

      _path_num = 0;

      while (_path_num < k) {

        // Run Dijkstra

        if (!_dijkstra->run()) break;

        ++_path_num;

        // Set the flow along the found shortest path

        Node u = _target;

        Arc e;

        while ((e = _pred[u]) != INVALID) {

          if (u == _graph.target(e)) {

            (*_flow)[e] = 1;

            u = _graph.source(e);

          } else {

            (*_flow)[e] = 0;

            u = _graph.target(e);

          }

        }

      }

      return _path_num;

    }

    /// \brief Compute the paths from the flow.

    ///

    ///

    /// \pre \ref init() and \ref findFlow() must be called before using

    /// this function.

    void findPaths() {

      FlowMap res_flow(_graph);

      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];

      paths.clear();

      paths.resize(_path_num);

      for (int i = 0; i < _path_num; ++i) {

        Node n = _source;

        while (n != _target) {

          OutArcIt e(_graph, n);

          for ( ; res_flow[e] == 0; ++e) ;

          n = _graph.target(e);

          paths[i].addBack(e);

          res_flow[e] = 0;

        }

      }

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.

    /// \n The algorithm should be executed before using them.

    /// @{

    /// found flow.

    ///

    /// the flow that is the union of the found arc-disjoint paths.

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    const FlowMap& flowMap() const {

      return *_flow;

    }

    /// \brief Return the potential of the given node.

    ///

    /// This function returns the potential of the given node.

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    Length potential(const Node& node) const {

      return (*_potential)[node];

    }

    ///

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    }

    /// \brief Return the number of the found paths.

    ///

    /// This function returns the number of the found paths.

    ///

    /// \pre \ref run() or \ref findFlow() must be called before using

    /// this function.

    int pathNum() const {

      return _path_num;

    }

    /// \brief Return a const reference to the specified path.

    ///

    /// This function returns a const reference to the specified path.

    ///

    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.

    ///

    /// \pre \ref run() or \ref findPaths() must be called before using

    /// this function.

    Path path(int i) const {

      return paths[i];

    }

    /// @}

  }; //class Suurballe

  ///@}

} //namespace lemon

#endif //LEMON_SUURBALLE_H

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * 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.

 *

 */

#include <iostream>

#include <lemon/list_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/suurballe.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "@arcs\n"

  "@attributes\n"

  "source  1\n"

  "target 12\n"

  "@end\n";

// Check the feasibility of the flow

template <typename Digraph, typename FlowMap>

bool checkFlow( const Digraph& gr, const FlowMap& flow,

                typename Digraph::Node s, typename Digraph::Node t,

                int value )

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  for (ArcIt e(gr); e != INVALID; ++e)

    if (!(flow[e] == 0 || flow[e] == 1)) return false;

  for (NodeIt n(gr); n != INVALID; ++n) {

    int sum = 0;

    for (OutArcIt e(gr, n); e != INVALID; ++e)

      sum += flow[e];

    for (InArcIt e(gr, n); e != INVALID; ++e)

      sum -= flow[e];

    if (n == s && sum != value) return false;

    if (n == t && sum != -value) return false;

    if (n != s && n != t && sum != 0) return false;

  }

  return true;

}

// Check the optimalitiy of the flow

template < typename Digraph, typename CostMap,

           typename FlowMap, typename PotentialMap >

bool checkOptimality( const Digraph& gr, const CostMap& cost,

                      const FlowMap& flow, const PotentialMap& pi )

{

  // Check the "Complementary Slackness" optimality condition

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  bool opt = true;

  for (ArcIt e(gr); e != INVALID; ++e) {

    typename CostMap::Value red_cost =

      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];

    opt = (flow[e] == 0 && red_cost >= 0) ||

          (flow[e] == 1 && red_cost <= 0);

    if (!opt) break;

  }

  return opt;

}

// Check a path

template <typename Digraph, typename Path>

bool checkPath( const Digraph& gr, const Path& path,

                typename Digraph::Node s, typename Digraph::Node t)

{

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Node n = s;

  for (int i = 0; i < path.length(); ++i) {

    if (gr.source(path.nth(i)) != n) return false;

    n = gr.target(path.nth(i));

  }

  return n == t;

}

int main()

{

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  ListDigraph digraph;

  ListDigraph::ArcMap<int> length(digraph);

  std::istringstream input(test_lgf);

  DigraphReader<ListDigraph>(digraph, input).

    run();

  // Find 2 paths

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 510, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  // Find 3 paths

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  // Find 5 paths (only 3 can be found)

  {

          "The flow is not feasible");

    check(suurballe.totalLength() == 1040, "The flow is not optimal");

    check(checkOptimality(digraph, length, suurballe.flowMap(),

                          suurballe.potentialMap()),

          "Wrong potentials");

    for (int i = 0; i < suurballe.pathNum(); ++i)

  }

  return 0;

}

        arc = curr < next ?

          std::make_pair(curr, next) : std::make_pair(next, curr);

        if (arcs.find(arc) == arcs.end()) {

          arcs.insert(arc);

          g.addEdge(nodes[curr], nodes[next]);

          ++cnt;

        }

      }

      Beach::iterator pbit = bit; --pbit;

      int ppv = pbit->first.prev;

      Beach::iterator nbit = bit; ++nbit;

      int nnt = nbit->first.next;

      if (bit->second != spikeheap.end()) spikeheap.erase(bit->second);

      if (pbit->second != spikeheap.end()) spikeheap.erase(pbit->second);

      if (nbit->second != spikeheap.end()) spikeheap.erase(nbit->second);

      beach.erase(nbit);

      beach.erase(bit);

      beach.erase(pbit);

      SpikeHeap::iterator pit = spikeheap.end();

      if (ppv != -1 && ppv != next &&

          circle_form(points[ppv], points[prev], points[next])) {

        double x = circle_point(points[ppv], points[prev], points[next]);

        if (x < sweep) x = sweep;

        pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));

        pit->second.it =

          beach.insert(std::make_pair(Part(ppv, prev, next), pit));

      } else {

        beach.insert(std::make_pair(Part(ppv, prev, next), pit));

      }

      SpikeHeap::iterator nit = spikeheap.end();

      if (nnt != -1 && prev != nnt &&

          circle_form(points[prev], points[next], points[nnt])) {

        double x = circle_point(points[prev], points[next], points[nnt]);

        if (x < sweep) x = sweep;

        nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));

        nit->second.it =

          beach.insert(std::make_pair(Part(prev, next, nnt), nit));

      } else {

        beach.insert(std::make_pair(Part(prev, next, nnt), nit));

      }

    }

  }

  for (Beach::iterator it = beach.begin(); it != beach.end(); ++it) {

    int curr = it->first.curr;

    int next = it->first.next;

    if (next == -1) continue;

    std::pair<int, int> arc;

    arc = curr < next ?

      std::make_pair(curr, next) : std::make_pair(next, curr);

    if (arcs.find(arc) == arcs.end()) {

      arcs.insert(arc);

      g.addEdge(nodes[curr], nodes[next]);

      ++cnt;

    }

  }

}

void sparse(int d)

{

  Counter cnt("Number of arcs removed: ");

  Bfs<ListGraph> bfs(g);

  for(std::vector<Edge>::reverse_iterator ei=arcs.rbegin();

      ei!=arcs.rend();++ei)

    {

      Node a=g.u(*ei);

      Node b=g.v(*ei);

      g.erase(*ei);

      bfs.run(a,b);

      if(bfs.predArc(b)==INVALID || bfs.dist(b)>d)

        g.addEdge(a,b);

      else cnt++;

    }

}

void sparse2(int d)

{

  Counter cnt("Number of arcs removed: ");

  for(std::vector<Edge>::reverse_iterator ei=arcs.rbegin();

      ei!=arcs.rend();++ei)

    {

      Node a=g.u(*ei);

      Node b=g.v(*ei);

      g.erase(*ei);

      ConstMap<Arc,int> cegy(1);

      if(k<2 || sur.totalLength()>d)

        g.addEdge(a,b);

      else cnt++;

//       else std::cout << "Remove arc " << g.id(a) << "-" << g.id(b) << '\n';

    }

}

void sparseTriangle(int d)

{

  Counter cnt("Number of arcs added: ");

  std::vector<Parc> pedges;

  for(NodeIt n(g);n!=INVALID;++n)

    for(NodeIt m=++(NodeIt(n));m!=INVALID;++m)

      {

        Parc p;

        p.a=n;

        p.b=m;

        p.len=(coords[m]-coords[n]).normSquare();

        pedges.push_back(p);

      }

  std::sort(pedges.begin(),pedges.end(),pedgeLess);

  for(std::vector<Parc>::iterator pi=pedges.begin();pi!=pedges.end();++pi)

    {

      Line li(pi->a,pi->b);

      EdgeIt e(g);

      for(;e!=INVALID && !cross(e,li);++e) ;

      Edge ne;

      if(e==INVALID) {

        ConstMap<Arc,int> cegy(1);

        if(k<2 || sur.totalLength()>d)

          {

            ne=g.addEdge(pi->a,pi->b);

            arcs.push_back(ne);

            cnt++;

          }

      }

    }

}

template <typename Graph, typename CoordMap>

class LengthSquareMap {

public:

  typedef typename Graph::Edge Key;

  typedef typename CoordMap::Value::Value Value;

  LengthSquareMap(const Graph& graph, const CoordMap& coords)

    : _graph(graph), _coords(coords) {}

  Value operator[](const Key& key) const {

    return (_coords[_graph.v(key)] -

            _coords[_graph.u(key)]).normSquare();

  }

private:

  const Graph& _graph;

  const CoordMap& _coords;

};

void minTree() {

  std::vector<Parc> pedges;

  Timer T;

  std::cout << T.realTime() << "s: Creating delaunay triangulation...\n";

  delaunay();

  std::cout << T.realTime() << "s: Calculating spanning tree...\n";

  LengthSquareMap<ListGraph, ListGraph::NodeMap<Point> > ls(g, coords);

  ListGraph::EdgeMap<bool> tree(g);