Program Listing for File AllPairsShortestPaths.h

↰ Return to documentation for file (ADS/graph/AllPairsShortestPaths.h)

/*--------------------------------------------------------------------------*/
/*---------------------- File AllPairsShortestPaths.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_AllPairsShortestPaths
 #define __ADS_AllPairsShortestPaths
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/graph/Graph.h"
#include "ADS/graph/ShortestPaths.h"

#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

template< class D >
struct AllPairs {
 std::vector< std::vector< D > > d;
 std::vector< std::vector< int > > p;
 bool negativeCycle = false;
 };

template< Graph G >
AllPairs< typename G::Weight > floydWarshall( const G & g );

template< class D >
void addEdge( AllPairs< D > & R , int a , int b , const D & w );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/graph/impl/AllPairsShortestPaths.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* AllPairsShortestPaths.h included */

/*--------------------------------------------------------------------------*/
/*-------------------- End File AllPairsShortestPaths.h --------------------*/
/*--------------------------------------------------------------------------*/