Classes
class	EXCN_Stop_BFS
	Class to raise to do an immediate stop of a breadth first search. ONLY THROW FROM WITHIN A VISITOR PASSED TO breadth_first_visit_prune/breadth_first_search_prune. More...

class	HideVertexVisitor

class	null_bfs_prune_visitor

class	RingDetection
	basic chemical Bond More...

class	RingEdgeAnnotationVisitor

class	RingSizeVisitor
	A class to implement the behavior of the smallest ring size finding algorithm, accessible through the smallest_ring_size() function below. More...

Functions
template<class IncidenceGraph , class Buffer , class BFSVisitor , class ColorMap >
void	breadth_first_visit_prune (const IncidenceGraph &g, typename boost::graph_traits< IncidenceGraph >::vertex_descriptor s, BFSVisitor vis, ColorMap color, Buffer &Q)
	breadth_first_visit_prune is a slightly modified version of the Boost function breadth_first_visit, allowing the visitor class to prune nodes and edges. See breadth_first_search_prune for details More...

template<class IncidenceGraph , class BFSVisitor , class ColorMap >
void	breadth_first_visit_prune (const IncidenceGraph &, typename boost::graph_traits< IncidenceGraph >::vertex_descriptor s, BFSVisitor vis, ColorMap color)

template<class VertexListGraph , class Buffer , class BFSVisitor , class ColorMap >
void	breadth_first_search_prune (const VertexListGraph &g, typename boost::graph_traits< VertexListGraph >::vertex_descriptor s, BFSVisitor vis, ColorMap color, Buffer &Q)
	breadth_first_search_prune is a slightly modified versions of the Boost functions breadth_first_search allowing the visitor class to prune nodes and edges. More...

template<class VertexListGraph , class BFSVisitor , class ColorMap >
void	breadth_first_search_prune (const VertexListGraph &g, typename boost::graph_traits< VertexListGraph >::vertex_descriptor s, BFSVisitor vis, ColorMap color)

template<class VertexListGraph , class BFSVisitor >
void	breadth_first_search_prune (const VertexListGraph &g, typename boost::graph_traits< VertexListGraph >::vertex_descriptor s, BFSVisitor vis)

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >
void	depth_first_visit_sort_impl (const IncidenceGraph &g, typename boost::graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor &vis, ColorMap color, SortFunc const &func)
	depth_first_visit_sort_impl is a slightly modified version of the recursive version of the Boost function depth_first_visit_impl, allowing the visitor class to prune nodes and edges. See depth_first_search_sort for details More...

template<class VertexListGraph , class DFSVisitor , class ColorMap , class SortFunc >
void	depth_first_search_sort (const VertexListGraph &g, DFSVisitor vis, ColorMap color, typename boost::graph_traits< VertexListGraph >::vertex_descriptor start_vertex, SortFunc const &func)
	A sorted depth first search. The parameter func should be a callable object which takes two graph edge descriptors, and returns true if the first should go before the second in ordering. More...

template<class VertexListGraph , class DFSVisitor , class ColorMap , class SortFunc >
void	depth_first_search_sort (const VertexListGraph &g, DFSVisitor vis, ColorMap color, SortFunc const &func)
	A sorted depth first search. The parameter func should be a callable object which takes two graph edge descriptors, and returns true if the first should go before the second in ordering. More...

template<class VertexListGraph , class SortFunc , class P , class T , class R >
void	depth_first_search_sort (const VertexListGraph &g, SortFunc const &func, const boost::bgl_named_params< P, T, R > &params)
	Named Parameter Variant. More...

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >
void	depth_first_visit (const IncidenceGraph &g, typename boost::graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor vis, ColorMap color, SortFunc const &func)

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >
void	depth_first_visit (const IncidenceGraph &g, typename boost::graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor vis, ColorMap color, SortFunc func=SortFunc())

template<class Graph >
platform::Size	smallest_ring_size (typename boost::graph_traits< Graph >::vertex_descriptor const &vd, Graph const &graph, platform::Size const &max_ring_size=2 *999999)
	A boost graph-based function to find the size of the smallest ring for a given vertex. Will return the maximum ring size, or 999999 for no ring. If there is a maximum ring size, That can be set to limit the amount of search needed. More...

template<class Graph >
std::map< typename boost::graph_traits< Graph > ::vertex_descriptor, std::map < typename boost::graph_traits < Graph >::vertex_descriptor, bool > >	annotate_ring_edges (Graph &graph)

Function Documentation

template<class Graph >

std::map< typename boost::graph_traits<Graph>::vertex_descriptor, std::map< typename boost::graph_traits<Graph>::vertex_descriptor, bool > > utility::graph::annotate_ring_edges ( Graph & graph )

template<class VertexListGraph , class Buffer , class BFSVisitor , class ColorMap >

void utility::graph::breadth_first_search_prune	(	const VertexListGraph &	g,
		typename boost::graph_traits< VertexListGraph >::vertex_descriptor	s,
		BFSVisitor	vis,
		ColorMap	color,
		Buffer &	Q
	)

breadth_first_search_prune is a slightly modified versions of the Boost functions breadth_first_search allowing the visitor class to prune nodes and edges.

Note the calling order is slightly different (and has to be explicit), as I didn't want to recapitulate the boost frontend magic.

It assumes all of the relevant functions in the visitor class return bools, with the following meanings:

vis.initialize_vertex(u, g) – return value ignored vis.discover_vertex(u, g); – if true, don't add vertex to queue (but still mark as grey) vis.examine_vertex(u, g); – if true, don't examine any out edges for vertex (but still mark black) vis.examine_edge(e, g); – if true, ignore edge (don't follow) vis.tree_edge(e, g); – if true, ignore discovered vertex (don't mark as grey) vis.non_tree_edge(e, g); – if true, don't bother with black/grey function calls vis.gray_target(e, g); – return value ignored vis.black_target(e, g); – return value ignored vis.finish_vertex(u, g); – return value ignored

Any of the above functions can throw a EXCN_Stop_BFS exception, which will immediately halt the search.

References breadth_first_visit_prune().

Referenced by smallest_ring_size().

template<class VertexListGraph , class BFSVisitor , class ColorMap >

void utility::graph::breadth_first_search_prune	(	const VertexListGraph &	g,
		typename boost::graph_traits< VertexListGraph >::vertex_descriptor	s,
		BFSVisitor	vis,
		ColorMap	color
	)

References breadth_first_visit_prune().

template<class VertexListGraph , class BFSVisitor >

void utility::graph::breadth_first_search_prune	(	const VertexListGraph &	g,
		typename boost::graph_traits< VertexListGraph >::vertex_descriptor	s,
		BFSVisitor	vis
	)

References breadth_first_visit_prune(), and extract_scores_and_constraints::get.

template<class IncidenceGraph , class Buffer , class BFSVisitor , class ColorMap >

void utility::graph::breadth_first_visit_prune	(	const IncidenceGraph &	g,
		typename boost::graph_traits< IncidenceGraph >::vertex_descriptor	s,
		BFSVisitor	vis,
		ColorMap	color,
		Buffer &	Q
	)

breadth_first_visit_prune is a slightly modified version of the Boost function breadth_first_visit, allowing the visitor class to prune nodes and edges. See breadth_first_search_prune for details

References basic::options::OptionKeys::hotspot::target, and test.T850_SubClassing::v.

Referenced by breadth_first_search_prune(), and breadth_first_visit_prune().

template<class IncidenceGraph , class BFSVisitor , class ColorMap >

void utility::graph::breadth_first_visit_prune	(	const IncidenceGraph &	,
		typename boost::graph_traits< IncidenceGraph >::vertex_descriptor	s,
		BFSVisitor	vis,
		ColorMap	color
	)

References breadth_first_visit_prune().

template<class VertexListGraph , class DFSVisitor , class ColorMap , class SortFunc >

void utility::graph::depth_first_search_sort	(	const VertexListGraph &	g,
		DFSVisitor	vis,
		ColorMap	color,
		typename boost::graph_traits< VertexListGraph >::vertex_descriptor	start_vertex,
		SortFunc const &	func
	)

A sorted depth first search. The parameter func should be a callable object which takes two graph edge descriptors, and returns true if the first should go before the second in ordering.

This version will start at start_vertex, but will restart arbitrarily for any disconnected graph portions.

References depth_first_visit_sort_impl(), and assign_charges::first.

Referenced by depth_first_search_sort().

template<class VertexListGraph , class DFSVisitor , class ColorMap , class SortFunc >

void utility::graph::depth_first_search_sort	(	const VertexListGraph &	g,
		DFSVisitor	vis,
		ColorMap	color,
		SortFunc const &	func
	)

A sorted depth first search. The parameter func should be a callable object which takes two graph edge descriptors, and returns true if the first should go before the second in ordering.

This version will start at an arbitrary vertex, and restart for disconnected portions of the graph

References depth_first_search_sort().

template<class VertexListGraph , class SortFunc , class P , class T , class R >

void utility::graph::depth_first_search_sort	(	const VertexListGraph &	g,
		SortFunc const &	func,
		const boost::bgl_named_params< P, T, R > &	params
	)

Named Parameter Variant.

References depth_first_search_sort(), and assign_charges::first.

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >

void utility::graph::depth_first_visit	(	const IncidenceGraph &	g,
		typename boost::graph_traits< IncidenceGraph >::vertex_descriptor	u,
		DFSVisitor	vis,
		ColorMap	color,
		SortFunc const &	func
	)

References depth_first_visit_sort_impl().

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >

void utility::graph::depth_first_visit	(	const IncidenceGraph &	g,
		typename boost::graph_traits< IncidenceGraph >::vertex_descriptor	u,
		DFSVisitor	vis,
		ColorMap	color,
		SortFunc	func = `SortFunc()`
	)

References depth_first_visit_sort_impl().

template<class IncidenceGraph , class DFSVisitor , class ColorMap , class SortFunc >

void utility::graph::depth_first_visit_sort_impl	(	const IncidenceGraph &	g,
		typename boost::graph_traits< IncidenceGraph >::vertex_descriptor	u,
		DFSVisitor &	vis,
		ColorMap	color,
		SortFunc const &	func
	)

depth_first_visit_sort_impl is a slightly modified version of the recursive version of the Boost function depth_first_visit_impl, allowing the visitor class to prune nodes and edges. See depth_first_search_sort for details

References basic::options::OptionKeys::hotspot::target, and test.T850_SubClassing::v.

Referenced by depth_first_search_sort(), and depth_first_visit().

template<class Graph >

platform::Size utility::graph::smallest_ring_size	(	typename boost::graph_traits< Graph >::vertex_descriptor const &	vd,
		Graph const &	graph,
		platform::Size const &	max_ring_size = `2*999999`
	)

A boost graph-based function to find the size of the smallest ring for a given vertex. Will return the maximum ring size, or 999999 for no ring. If there is a maximum ring size, That can be set to limit the amount of search needed.

References breadth_first_search_prune().

Classes

Functions

Function Documentation