Rosetta Utilities  2014.35
Classes | Functions
utility::graph Namespace Reference

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 
)
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 
)
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.

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 
)
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().

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().

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 
)
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() 
)
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.

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().