boost Namespace Reference

Additions to Boost namespace for BGL compatibility of custom graph classes. More...

Data Structures
struct	vertex_and_edge_list_plus_incidence_graph_tag
struct	graph_traits< const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph >
struct	graph_traits< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph >
struct	property_map< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph, edge_weight_t >
struct	property_traits< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeWeightMap >
struct	property_traits< const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeWeightMap >
struct	property_map< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph, vertex_index_t >
struct	property_traits< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexIndexMap >
struct	property_traits< const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexIndexMap >

Functions
template<typename VertexDescriptor , class DistanceMap , class PredecessorMap , class ColorMap >
void	gor1_scan_helper (const VertexDescriptor &vertex, const VertexDescriptor &targetVertex, const double vertexDistance, const double edgeWeight, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map, std::stack< VertexDescriptor > &B)
template<typename VertexDescriptor , class IncidenceGraph , class DistanceMap , class PredecessorMap , class ColorMap >
std::enable_if_t< std::is_same< IncidenceGraph, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph >::value, void >	gor1_ig_scan (const VertexDescriptor &vertex, const IncidenceGraph &graph, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map, std::stack< VertexDescriptor > &B)
template<class IncidenceGraph , class DistanceMap , class PredecessorMap , class ColorMap , typename VertexDescriptor >
std::enable_if_t< std::is_same< IncidenceGraph, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph >::value, bool >	gor1_ig_shortest_paths (const IncidenceGraph &graph, const VertexDescriptor &root_vertex, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map)
template<typename VertexDescriptor , class GraphClass , class DistanceMap , class PredecessorMap , class ColorMap >
void	gor1_eg_scan (const VertexDescriptor &vertex, const GraphClass &graphWrapper, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map, std::stack< VertexDescriptor > &B)
template<class GraphClass , class DistanceMap , class PredecessorMap , class ColorMap , typename VertexDescriptor >
std::enable_if_t< std::is_same< GraphClass, Scine::Molassembler::DistanceGeometry::ExplicitBoundsGraph >::value, bool >	gor1_eg_shortest_paths (const GraphClass &graphWrapper, const VertexDescriptor &root_vertex, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map)
std::pair< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::vertex_iterator, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::vertex_iterator >	vertices (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor	num_vertices (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
std::pair< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::edge_iterator, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::edge_iterator >	edges (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor	num_edges (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor	source (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor &e, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor	target (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor &e, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
std::pair< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor, bool >	edge (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor &u, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor &v, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeWeightMap	get (const boost::edge_weight_t &, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeWeightMap	get (const boost::edge_weight_t &, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
double	get (const boost::edge_weight_t &p, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor &x)
double	get (const boost::edge_weight_t &p, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor &x)
void	put (const boost::edge_weight_t &, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::EdgeDescriptor &, double)
Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexIndexMap	get (const boost::vertex_index_t &, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &)
std::pair< Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::edge_iterator, Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::edge_iterator >	out_edges (const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph::VertexDescriptor &u, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
unsigned long	out_degree (const unsigned long &u, const Scine::Molassembler::DistanceGeometry::ImplicitBoundsGraph &g)
template<class IncidenceGraph , class DistanceMap , class PredecessorMap , class ColorMap , class Visitor , typename VertexDescriptor >
bool	gor1_simplified_shortest_paths (const IncidenceGraph &graph, const VertexDescriptor &root_vertex, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map, Visitor &visitor)
	Simplified GOR1 single source shortest paths algorithm. More...
template<class IncidenceGraph , class DistanceMap , class PredecessorMap , class ColorMap , typename VertexDescriptor >
bool	gor1_simplified_shortest_paths (const IncidenceGraph &graph, const VertexDescriptor &root_vertex, PredecessorMap &predecessor_map, ColorMap &color_map, DistanceMap &distance_map)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Detailed Description

Additions to Boost namespace for BGL compatibility of custom graph classes.

Function Documentation

gor1_simplified_shortest_paths()

template<class IncidenceGraph , class DistanceMap , class PredecessorMap , class ColorMap , class Visitor , typename VertexDescriptor >

bool boost::gor1_simplified_shortest_paths	(	const IncidenceGraph &	graph,
		const VertexDescriptor &	root_vertex,
		PredecessorMap &	predecessor_map,
		ColorMap &	color_map,
		DistanceMap &	distance_map,
		Visitor &	visitor
	)

Simplified GOR1 single source shortest paths algorithm.

Implements the algorithm described in

• Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73(2), 129–174. https://doi.org/10.1007/BF02592101

Reference C implementation in

• https://github.com/skvadrik/cherkassky_goldberg_radzik

Complexity \(\Theta(V E)\)

Template Parameters

IncidenceGraph	Type modeling Boost's IncidenceGraph concept
DistanceMap	Type mapping vertex descriptors to distance
PredecessorMap	Type mapping vertex descriptors to their predecessor vertex
ColorMap	Type mapping vertex descriptors to a color
Visitor	Type that performs event visitation operations
VertexDescriptor	Type of the Graph's vertex descriptor

Parameters

graph	The graph that vertex is contained in
root_vertex	The source vertex from which shortest distances are to be calculated
predecessor_map	The map of vertices to their predecessors
color_map	The map of vertices to their color
distance_map	The map of vertices to their distance
visitor	A visitor that matches the DummyGor1Visitor interface

Note

This function, in boost style, expects you to set up some of the data structures used internally in the algorithm, whether you care about them or not for the off chance you want all of them and structured bindings weren't a thing when boost came about.

// Setup prior to call
const unsigned N = boost::num_vertices(g);
std::vector<double> distances(N);
std::vector<VertexType> predecessors(N);
 
auto predecessor_map = boost::make_iterator_property_map(
  predecessors.begin(),
  get(boost::vertex_index, g)
);
 
auto distance_map = boost::make_iterator_property_map(
  distances.begin(),
  get(boost::vertex_index, g)
);
 
using ColorMapType = boost::two_bit_color_map<>;
ColorMapType color_map {N};