COIN-OR::LEMON - Graph Library

Changeset 2335:27aa03cd3121 in lemon-0.x for lemon/johnson.h


Ignore:
Timestamp:
01/08/07 11:39:59 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3123
Message:

New path concept and path structures

TODO: BellmanFord::negativeCycle()

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/johnson.h

    r2263 r2335  
    2929#include <lemon/dijkstra.h>
    3030#include <lemon/bellman_ford.h>
     31#include <lemon/bits/path_dump.h>
    3132#include <lemon/bits/invalid.h>
    3233#include <lemon/error.h>
     
    630631    ///@{
    631632
    632     /// \brief Copies the shortest path to \c t into \c p
    633     ///   
    634     /// This function copies the shortest path to \c t into \c p.
    635     /// If it \c t is a source itself or unreachable, then it does not
    636     /// alter \c p.
    637     /// \return Returns \c true if a path to \c t was actually copied to \c p,
    638     /// \c false otherwise.
    639     /// \sa DirPath
    640     template <typename Path>
    641     bool getPath(Path &p, Node source, Node target) {
    642       if (connected(source, target)) {
    643         p.clear();
    644         typename Path::Builder b(target);
    645         for(b.setStartNode(target); predEdge(source, target) != INVALID;
    646             target = predNode(target)) {
    647           b.pushFront(predEdge(source, target));
    648         }
    649         b.commit();
    650         return true;
    651       }
    652       return false;
     633    typedef PredMatrixMapPath<Graph, PredMap> Path;
     634
     635    ///Gives back the shortest path.
     636   
     637    ///Gives back the shortest path.
     638    ///\pre The \c t should be reachable from the \c t.
     639    Path path(Node s, Node t)
     640    {
     641      return Path(*graph, *_pred, s, t);
    653642    }
    654643         
Note: See TracChangeset for help on using the changeset viewer.