Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark > Class Template Reference

brief todo More...

#include <Dijkstra_shortest_paths_with_landmarks.hpp>

Public Types

enum  Color { WHITE , GRAY , BLACK }
 
typedef T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark > Self
 
typedef boost::graph_traits< Graph >::vertex_descriptor Vertex
 
typedef boost::graph_traits< Graph >::edge_descriptor Edge
 
typedef boost::graph_traits< Graph >::vertex_iterator vertex_iterator
 
typedef boost::graph_traits< Graph >::vertices_size_type vertices_size_type
 
typedef boost::graph_traits< Graph >::adjacency_iterator adjacency_iterator
 

Public Member Functions

template<class PredecessorMap , class DistanceMap , class WeightMap >
void operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, const IsLandmark &is_landmark, WeightMap &weights, unsigned k=0) const
 if k = 0, it stops when all other landmarks were visited More...
 
template<class PredecessorMap , class DistanceMap , class WeightMap >
void operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, WeightMap &weights, unsigned k=0) const
 
template<class PredecessorMap , class DistanceMap >
void operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, const IsLandmark &is_landmark, unsigned k=0) const
 
template<class PredecessorMap , class DistanceMap >
void operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, unsigned k=0) const
 

Static Public Member Functions

template<class OutputIterator >
static OutputIterator get_landmarks (Graph &G, const IsLandmark &is_landmark, OutputIterator out)
 this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...
 
template<class OutputIterator >
static OutputIterator get_landmarks (Graph &G, OutputIterator out)
 this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...
 
static unsigned count_landmarks (Graph &G, const IsLandmark &is_landmark=IsLandmark())
 this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...
 
template<class DistanceMap , class OutputIterator >
static OutputIterator get_landmark_shortest_distances (Graph &G, Vertex u, DistanceMap &dist, const IsLandmark &is_landmark, OutputIterator out)
 
template<class DistanceMap , class OutputIterator >
static OutputIterator get_landmark_shortest_distances (Graph &G, Vertex u, DistanceMap &dist, OutputIterator out)
 
template<class PredecessorMap , class OutputIterator >
static OutputIterator get_shortest_path_to_landmark (Graph &G, Vertex u, Vertex v, PredecessorMap &pred, const IsLandmark &is_landmark, OutputIterator out)
 
template<class PredecessorMap , class OutputIterator >
static OutputIterator get_shortest_path_to_landmark (Graph &G, Vertex u, Vertex v, PredecessorMap &pred, OutputIterator out)
 

Detailed Description

template<class Graph, class IsLandmark>
class SBL::CADS::T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark >

brief todo

details todo.

Member Typedef Documentation

◆ adjacency_iterator

typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_iterator

◆ Edge

typedef boost::graph_traits<Graph>::edge_descriptor Edge

◆ Self

typedef T_Dijkstra_shortest_paths_with_landmarks<Graph, IsLandmark> Self

◆ Vertex

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex

◆ vertex_iterator

typedef boost::graph_traits<Graph>::vertex_iterator vertex_iterator

◆ vertices_size_type

typedef boost::graph_traits<Graph>::vertices_size_type vertices_size_type

Member Enumeration Documentation

◆ Color

enum Color
Enumerator
WHITE 
GRAY 
BLACK 

Member Function Documentation

◆ count_landmarks()

static unsigned count_landmarks ( Graph &  G,
const IsLandmark &  is_landmark = IsLandmark() 
)
inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

◆ get_landmark_shortest_distances() [1/2]

OutputIterator get_landmark_shortest_distances ( Graph &  G,
Vertex  u,
DistanceMap &  dist,
const IsLandmark &  is_landmark,
OutputIterator  out 
)
inlinestatic

◆ get_landmark_shortest_distances() [2/2]

static OutputIterator get_landmark_shortest_distances ( Graph &  G,
Vertex  u,
DistanceMap &  dist,
OutputIterator  out 
)
inlinestatic

◆ get_landmarks() [1/2]

static OutputIterator get_landmarks ( Graph &  G,
const IsLandmark &  is_landmark,
OutputIterator  out 
)
inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

◆ get_landmarks() [2/2]

static OutputIterator get_landmarks ( Graph &  G,
OutputIterator  out 
)
inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

◆ get_shortest_path_to_landmark() [1/2]

OutputIterator get_shortest_path_to_landmark ( Graph &  G,
Vertex  u,
Vertex  v,
PredecessorMap &  pred,
const IsLandmark &  is_landmark,
OutputIterator  out 
)
inlinestatic

◆ get_shortest_path_to_landmark() [2/2]

static OutputIterator get_shortest_path_to_landmark ( Graph &  G,
Vertex  u,
Vertex  v,
PredecessorMap &  pred,
OutputIterator  out 
)
inlinestatic

◆ operator()() [1/4]

void operator() ( Graph &  G,
Vertex  origin,
PredecessorMap &  pred,
DistanceMap &  dist,
const IsLandmark &  is_landmark,
unsigned  k = 0 
) const
inline

◆ operator()() [2/4]

void operator() ( Graph &  G,
Vertex  origin,
PredecessorMap &  pred,
DistanceMap &  dist,
const IsLandmark &  is_landmark,
WeightMap &  weights,
unsigned  k = 0 
) const
inline

if k = 0, it stops when all other landmarks were visited

main function computes the k shortest distances to other landmarks from each landmark and outputs the result to an ostream it uses for each landmark a truncated version of dijkstra's algorithm that stops when k other landmarks where visited the greedy-optimal nature of dijkstra's algorithm guarantees that the distances to these k landmarks are indeed the shortest ones

◆ operator()() [3/4]

void operator() ( Graph &  G,
Vertex  origin,
PredecessorMap &  pred,
DistanceMap &  dist,
unsigned  k = 0 
) const
inline

◆ operator()() [4/4]

void operator() ( Graph &  G,
Vertex  origin,
PredecessorMap &  pred,
DistanceMap &  dist,
WeightMap &  weights,
unsigned  k = 0 
) const
inline