Rosetta  2020.46
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Typedefs | Functions | Variables
utility::graph Namespace Reference

Classes

class  Array0
 Class Array0 is a c-style array wrapper that does bounds checking in debug mode. It indexes from 0 just like regular c-arrays. Class Array0 does not manage it's own memory. It does not allocate memory if you want to make it larger, nor does it deallocate memory when you destroy it. Bounds checking only ensures that the user does not go outside of the memory Array0 thinks it's in charge of. If the user should happen to point the array0 at memory that has not been allocated, Array0 is not responsible for segmentation fault that will likely occur. Garbage in, garbage out. More...
 
class  ArrayPool
 
class  ArrayPoolElement
 
class  Digraph
 A Digraph with constant time edge insertion and deletion. Extensible. More...
 
class  DirectedEdge
 
class  DirectedEdgeList
 Custom edge list class. Returns const-iterators which only return DirectedEdge const *'s and non-const-iterators which can return either const or non-const DirectedEdge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of DirectedEdgeListElements. Implemented as a doubly linked list, though there's no practical way to start at the end of a list and work backward since decrementing the end iterator is not a valid operation. More...
 
class  DirectedEdgeListConstIterator
 Custom DirectedEdge list const iterator class, which returns only const DirectedEdge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. More...
 
class  DirectedEdgeListElement
 An extensible directed graph class. More...
 
class  DirectedEdgeListIterator
 Custom DirectedEdge list (non-const) iterator class, which can return non-const DirectedEdge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. The former workaround to this problem was to define two sets of edge lists on each vertex: a list< DirectedEdge * > and a list< DirectedEdge const * >. More...
 
class  DirectedNode
 
class  DisjointSets
 
struct  DS_Node
 
class  Edge
 
class  EdgeList
 Custom edge list class. Returns const-iterators which only return Edge const *'s and non-const-iterators which can return either const or non-const Edge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of EdgeListElements. Implemented as a doubly linked list, though there's no practical way to start at the end of a list and work backward since decrementing the end iterator is not a valid operation. More...
 
class  EdgeListConstIterator
 Custom Edge list const iterator class, which returns only const Edge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. The former workaround to this problem was to define two sets of edge lists on each vertex: a list< Edge * > and a list< Edge const * >. More...
 
class  EdgeListElement
 An extensible graph class. More...
 
class  EdgeListIterator
 Custom Edge list (non-const) iterator class, which can return non-const Edge pointers. This iterator cannot be used to change the structure of its list without access to that list directly. Customized since STL's const-iterator cannot be prevented from giving non-const access to its data. The former workaround to this problem was to define two sets of edge lists on each vertex: a list< Edge * > and a list< Edge const * >. More...
 
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  Graph
 A Graph with constant time edge insertion and deletion. Extensible. More...
 
class  HideVertexVisitor
 
class  LowMemEdge
 An Edge class for LowMemGraph. Will often be overriden. Be careful with this class! It doesn't use actual virtual functions. Never do this: LowMemEdgeOP op = MyDerivedEdgeOP() Instead, if you wish to use an owning pointer, you must do this: MyDerivedEdgeOP op = MyDerivedEdgeOP() More...
 
class  LowMemEdgeListConstIter
 Const iterator for edges. More...
 
class  LowMemEdgeListIter
 Non-const iterator for edges. More...
 
class  LowMemGraph
 A graph with low memory use and constant time edge insertion. Extensible. For general use, use utility::graph::DefaultLowMemGraph. More...
 
class  LowMemGraphBase
 Pure virtual baseclass that was required to avoid templating Edges and Nodes. More...
 
class  LowMemNode
 An Node class for LowMemGraph. Will often be overriden Be careful with this class! It doesn't use actual virtual functions. Never do this: LowMemNodeOP op = MyDerivedNodeOP() Instead, if you wish to use an owning pointer, you must do this: MyDerivedNodeOP op = MyDerivedNodeOP() More...
 
class  NegSpaceElement
 NegSpaceElement represents a single element in the singly-linked list of negative space in an array pool. More...
 
class  Node
 
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...
 
class  UEEdge
 
class  UEVertex
 
class  UpperEdgeGraph
 

Typedefs

typedef
utility::pointer::shared_ptr
< ArrayPool< platform::Real > > 
RealArrayPoolOP
 
typedef
utility::pointer::shared_ptr
< ArrayPool< platform::Real >
const > 
RealArrayPoolCOP
 
typedef
utility::pointer::shared_ptr
< Digraph
DigraphOP
 
typedef
utility::pointer::shared_ptr
< Digraph const > 
DigraphCOP
 
typedef
utility::pointer::shared_ptr
< Graph
GraphOP
 
typedef
utility::pointer::shared_ptr
< Graph const > 
GraphCOP
 
typedef LowMemGraph
< LowMemNode, LowMemEdge
DefaultLowMemGraph
 
typedef
utility::pointer::shared_ptr
< DefaultLowMemGraph
DefaultLowMemGraphOP
 
typedef
utility::pointer::shared_ptr
< DefaultLowMemGraph const > 
DefaultLowMemGraphCOP
 

Functions

std::string neg_space_element_allocation_error_message (platform::Size block_size, platform::Size neg_space_element_size)
 
std::string block_allocation_error_message (platform::Size block_size, platform::Size array_size, platform::Size t_size)
 
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())
 
void visit (Digraph const &g, platform::Size node_index, utility::vector1< platform::Size > &visited_status, std::list< platform::Size > &toposort_order, bool &is_DAG)
 
platform::Size find_unmarked_node (utility::vector1< platform::Size > &visited_status, platform::Size last_descend_from)
 
std::pair< std::list
< platform::Size >, bool
topological_sort (Digraph const &g)
 Construct a topological sort for the input directed graph, if it is a DAG, and return whether or not the input graph is actually a DAG. More...
 
bool digraph_is_a_DAG (Digraph const &g)
 Return whether or not the input directed graph is a DAG – this invokes the topological_sort function and simply returns the second element in the pair that it returns. More...
 
bool all_visited (utility::vector1< bool > const &visited)
 
utility::vector1< std::pair
< platform::Size,
platform::Size > > 
find_connected_components (Graph const &g)
 returns a vector1 of connected component descriptions: each entry holds a representative vertex from that connected component (first entry in pair) and the connected-component size (second entry in pair). O( V+E ). More...
 
void delete_all_intragroup_edges (Graph &g, utility::vector1< platform::Size > const &node_groups)
 
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)
 

Variables

platform::Size const NOT_VISITED = 0
 
platform::Size const TEMPORARY_VISITED = 1
 
platform::Size const VISITED = 2
 
bool output_interaction_graph_memory_usage = false
 

Typedef Documentation

typedef utility::pointer::shared_ptr< DefaultLowMemGraph const > utility::graph::DefaultLowMemGraphCOP
typedef utility::pointer::shared_ptr< Digraph const > utility::graph::DigraphCOP
typedef utility::pointer::shared_ptr< Digraph > utility::graph::DigraphOP
typedef utility::pointer::shared_ptr< Graph const > utility::graph::GraphCOP
typedef utility::pointer::shared_ptr< Graph > utility::graph::GraphOP
typedef utility::pointer::shared_ptr< ArrayPool< platform::Real > const > utility::graph::RealArrayPoolCOP

Function Documentation

bool utility::graph::all_visited ( utility::vector1< bool > const &  visited)
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)
std::string utility::graph::block_allocation_error_message ( platform::Size  block_size,
platform::Size  array_size,
platform::Size  t_size 
)
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(), and test.T009_Exceptions::e.

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 test.T009_Exceptions::e, 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 
)
void utility::graph::delete_all_intragroup_edges ( Graph &  g,
utility::vector1< platform::Size > const &  node_groups 
)
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 
)
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, and test.T850_SubClassing::v.

Referenced by depth_first_search_sort(), and depth_first_visit().

bool utility::graph::digraph_is_a_DAG ( Digraph const &  g)

Return whether or not the input directed graph is a DAG – this invokes the topological_sort function and simply returns the second element in the pair that it returns.

References pyrosetta.tests.__main__::result, and topological_sort().

utility::vector1< std::pair< platform::Size, platform::Size > > utility::graph::find_connected_components ( Graph const &  g)

returns a vector1 of connected component descriptions: each entry holds a representative vertex from that connected component (first entry in pair) and the connected-component size (second entry in pair). O( V+E ).

DFS search to identify connected components O(V) memory, O(V+E) time.

References all_visited(), utility::graph::Node::const_edge_list_begin(), utility::graph::Node::const_edge_list_end(), debug_assert, utility::graph::Graph::get_node(), test.T200_Scoring::ii, and utility::graph::Graph::num_nodes().

platform::Size utility::graph::find_unmarked_node ( utility::vector1< platform::Size > &  visited_status,
platform::Size  last_descend_from 
)

References test.T200_Scoring::ii, and NOT_VISITED.

Referenced by topological_sort().

std::string utility::graph::neg_space_element_allocation_error_message ( platform::Size  block_size,
platform::Size  neg_space_element_size 
)
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().

std::pair< std::list< platform::Size >, bool > utility::graph::topological_sort ( Digraph const &  g)

Construct a topological sort for the input directed graph, if it is a DAG, and return whether or not the input graph is actually a DAG.

References find_unmarked_node(), NOT_VISITED, utility::graph::Digraph::num_nodes(), and visit().

Referenced by digraph_is_a_DAG().

void utility::graph::visit ( Digraph const &  g,
platform::Size  node_index,
utility::vector1< platform::Size > &  visited_status,
std::list< platform::Size > &  toposort_order,
bool is_DAG 
)

Variable Documentation

platform::Size const utility::graph::NOT_VISITED = 0
bool utility::graph::output_interaction_graph_memory_usage = false
platform::Size const utility::graph::TEMPORARY_VISITED = 1

Referenced by visit().

platform::Size const utility::graph::VISITED = 2

Referenced by visit().