#line 396 "k_shortest.w"

// Copyright (C) 2003 Vladimir Prus

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/dag_shortest_paths.hpp>

#include "vector_property_map.hpp"

#include <iostream>

namespace boost {

    
#line 142 "k_shortest.w"
    
    template<class G>
    class Shortest_paths_finder {
    public:
        
#line 384 "k_shortest.w"
        
        typedef typename graph_traits<G>::vertex_descriptor vertex;
        typedef typename graph_traits<G>::edge_descriptor edge;
        typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
        typedef typename graph_traits<G>::in_edge_iterator in_edge_iterator;
        typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
        
#line 146 "k_shortest.w"
    
    
        
#line 293 "k_shortest.w"
        
        template<class PredecessorMap>
        struct best_incoming_edge_recorder 
        : public base_visitor< best_incoming_edge_recorder<PredecessorMap> >
        {
            typedef on_edge_relaxed event_filter;
            best_incoming_edge_recorder(PredecessorMap pm)
            : pm(pm) 
            {}
            template<class Edge, class Graph>
            void operator()(Edge e, const Graph& g) const {
                put(pm, target(e, g), e);
            }
            PredecessorMap pm;
        };
        
#line 148 "k_shortest.w"
    
    
        Shortest_paths_finder(const G& g, vertex source, vertex sink)
        : g(g), m_source(source), m_sink(sink)
        {
          best_incoming_edge_recorder< vector_property_map<edge, index_map> > rec(best_incoming);
          dag_shortest_paths(this->g, source, 
              predecessor_map(predecessor).distance_map(distance)
              .visitor(make_dijkstra_visitor(rec))
              );
    
            vertex_iterator vi, ve;
            for (tie(vi, ve) = vertices(g); vi != ve; ++vi) {
              alternative[*vi] = *vi;
              root[*vi] = *vi;
            }
    
        }
    
        
#line 253 "k_shortest.w"
        
        bool find_alternative()
        {
            bool result = find_alternative(m_sink);
            m_sink = alternative[m_sink];
            cout << "new sink = " << m_sink << "\n";
            return result;
        }
        
        bool find_alternative(vertex v)
        {
            // Make sure alternative to 'vertex' is not computed yet.
            assert(alternative[v] == v);
        
            if (in_degree(root[v], g) == 0)
                return false;
        
            vertex pred = best_predecessor(v);
        
            // If the alternative is not computed, try to compute it now
            // The condition also handles the case where alternative does not
            // exists, in which case we better avoid recursive call... but anyway.
            cout << "at " << v << " pred = " << pred << "\n";
        
            // If there's alternative to the best predecessor, or we can compute it
            if (alternative[pred] != pred || find_alternative(pred)) {
                cout << "chaning best predecessor to " << alternative[pred] << "\n";
                change_best_predecessor(add_alternative(v), alternative[pred]);
            } else if (in_degree(root[v], g) > 1) {
                cout << "removing best predecessor\n";
                remove_best_predecessor(add_alternative(v));
            } else {
                return false;
            }
            return true;
        }
        
        
#line 167 "k_shortest.w"
    
    
        
#line 330 "k_shortest.w"
        
        template<class OutputIterator>
        void shortest_path(OutputIterator result) const
        {
          vector<vertex> path;
        
          for(vertex v = m_sink;; v = predecessor[v]) {
            path.push_back(root[v]);
            if (predecessor[v] == v)
                break;
          }
          copy(path.rbegin(), path.rend(), result);
        
        }
        
#line 169 "k_shortest.w"
    
       
    private:
       G g;
       vertex m_source;
       vertex m_sink; 
    
       
#line 188 "k_shortest.w"
       
       typedef property_map<G, vertex_index_t>::type index_map;
       
       vector_property_map<vertex, index_map> predecessor;
       vector_property_map<edge, index_map> best_incoming;
       vector_property_map<int, index_map> distance;
       
       vector_property_map<vertex, index_map> alternative, root;
       
       // Creates an alternative to v. Updates 'alternative' and 'root'
       // maps, but does nothing about predecessor and distance.
       vertex add_alternative(vertex v);
       
       vertex best_predecessor(vertex v) 
       {
       assert(predecessor[v] == source(best_incoming[v], g));
           return predecessor[v];
       }
       
       void change_best_predecessor(vertex v, vertex n)
       {
           int weight = get(edge_weight, g, best_incoming[v]);
           remove_edge(best_incoming[v], g);   
           edge e = add_edge(n, root[v], g).first;
       
           put(edge_weight, g, e, weight);
       
           adjust(v);
       }
       
       void remove_best_predecessor(vertex v)
       {
           remove_edge(best_predecessor(v), root[v], g);
           adjust(v);
       }
       
       void adjust(vertex v)
       {
           vertex r = root[v];
       
           typename graph_traits<G>::in_edge_iterator ii, ie;
           tie(ii, ie) = in_edges(r, g);
           if (ii == ie)
               return;
           distance[v] = distance[source(*ii, g)] + get(edge_weight, g, *ii);
           predecessor[v] = source(*ii, g);
           best_incoming[v] = *ii;
       
           while(++ii != ie) {
               int nd = distance[source(*ii, g)] + get(edge_weight, g, *ii);
               if (nd < distance[v]) {
                   distance[v] = nd;
                   predecessor[v] = source(*ii, g);
                   best_incoming[v] = *ii;
               }
           }
           cout << "best predecessor of " << v << "(root " << root[v] << ") is " 
                << predecessor[v] << "\n";
       }
       
       
#line 176 "k_shortest.w"
    
    
    };
    
#line 409 "k_shortest.w"


    
#line 311 "k_shortest.w"
    
    template<class G>
    Shortest_paths_finder<G>::vertex
    Shortest_paths_finder<G>::add_alternative(vertex v)
    {
        // Create the alternative vertex
        typename graph_traits<G>::vertex_descriptor alt = add_vertex(g);
        alternative[alt] = alt;
        alternative[v] = alt;
        root[alt] = root[v];
        // We duplicate all prec-related data now
        predecessor[alt] = predecessor[v];
        best_incoming[alt] = best_incoming[v];
        distance[alt] = distance[v];
        return alt;
    }
    
#line 411 "k_shortest.w"


    
#line 348 "k_shortest.w"
    
    template<class G>
    void k_shortest(const G& g, int k)
    {
        
#line 384 "k_shortest.w"
        
        typedef typename graph_traits<G>::vertex_descriptor vertex;
        typedef typename graph_traits<G>::edge_descriptor edge;
        typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
        typedef typename graph_traits<G>::in_edge_iterator in_edge_iterator;
        typedef typename graph_traits<G>::out_edge_iterator out_edge_iterator;
        
#line 352 "k_shortest.w"
    
        
#line 377 "k_shortest.w"
        
        function_requires< BidirectionalGraphConcept<G> >() ;
        function_requires< ReadablePropertyGraphConcept<G, edge, edge_weight_t> >();
        
#line 353 "k_shortest.w"
    
       
        if (num_vertices(g) == 0)
            return;
    
        Shortest_paths_finder<G> f(g, *vertices(g).first, *prior(vertices(g).second));
    
        do {
          vector<vertex> p;
          f.shortest_path(back_inserter(p));
    cout << "---------__";
          for (size_t i = 0; i < p.size(); ++i)
            cout << p[i] << " ";
           cout << "\n";
          for (size_t i = 0; i < p.size(); ++i)
            cout << p[i]+1 << " ";
          cout << "\n";
        } while(f.find_alternative());        
    }
    
#line 413 "k_shortest.w"


}