Rosetta  2020.37
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
utility::graph::RingDetection< Graph > Class Template Reference

basic chemical Bond More...

#include <RingDetection.hh>

Inheritance diagram for utility::graph::RingDetection< Graph >:
Inheritance graph
[legend]

Public Member Functions

 RingDetection (const Graph &graph)
 constructor from a graph (either GraphWithData or ConstGraph) More...
 
RingDetectionClone () const
 clone the object More...
 
const std::list< std::vector
< size_t > > & 
GetPaths () const
 Get the paths between vertices in the graph. More...
 
const utility::vector1
< utility::vector1< VD > > 
GetRings () const
 Get all rings in the graph. More...
 
- Public Member Functions inherited from utility::graph::null_bfs_prune_visitor
template<class Vertex , class Graph >
bool initialize_vertex (Vertex, Graph &)
 
template<class Vertex , class Graph >
bool discover_vertex (Vertex, Graph &)
 
template<class Vertex , class Graph >
bool examine_vertex (Vertex, Graph &)
 
template<class Edge , class Graph >
bool examine_edge (Edge, Graph &)
 
template<class Edge , class Graph >
bool tree_edge (Edge, Graph &)
 
template<class Edge , class Graph >
bool non_tree_edge (Edge, Graph &)
 
template<class Edge , class Graph >
bool gray_target (Edge, Graph &)
 
template<class Edge , class Graph >
bool black_target (Edge, Graph &)
 
template<class Vertex , class Graph >
bool finish_vertex (Vertex, Graph &)
 

Private Types

typedef boost::graph_traits
< Graph >::edge_descriptor 
Edge
 
typedef boost::graph_traits
< Graph >::vertex_descriptor 
VD
 
typedef boost::graph_traits
< Graph >::vertex_iterator 
VIter
 
typedef boost::graph_traits
< Graph >::edge_iterator 
EIter
 
typedef boost::graph_traits
< Graph >::out_edge_iterator 
OutEdgeIter
 

Private Member Functions

 RingDetection ()
 default constructor - needs an initialization graph More...
 
void Initialize (const Graph &graph)
 initialize paths_ with all edges from graph (which is either a GraphWithData or a ConstGraph) More...
 
void Remove (const std::size_t vertex)
 Remove vertices, store new paths and rings. More...
 
std::vector< size_t > CombinePaths (const std::size_t COMMON_vertex, const std::vector< size_t > &path_a, const std::vector< size_t > &path_b) const
 Combine two paths at their common vertex. More...
 
bool Overlap (const std::vector< bool > &vertex_is_in_path_a, const std::vector< std::size_t > &path_b) const
 Check if two paths overlap. More...
 
void SetupAdjacencyVector (std::vector< bool > &vertex_is_in_path, const std::vector< size_t > &path) const
 set the adjacency vector with a given path More...
 
size_t LengthOfSmallestCycleWithVertex (const Graph &graph, const std::size_t &vertex, const std::vector< size_t > &CAN_VISIT=std::vector< size_t >())
 LengthOfSmallestCycleWithVertex finds the length of the shortest cycle beginning at vertex. More...
 

Private Attributes

std::list< std::vector< size_t > > paths_
 paths between vertices in the graph More...
 
std::list< std::vector< size_t > > rings_
 rings in the graph More...
 
size_t graph_size_
 size of the graph More...
 
boost::unordered_map< size_t, VDindex_to_vd_
 
boost::unordered_map< VD, size_t > vd_to_index_
 

Detailed Description

template<class Graph>
class utility::graph::RingDetection< Graph >

basic chemical Bond

name, element, certain properties and parameters from .params file

Member Typedef Documentation

template<class Graph >
typedef boost::graph_traits<Graph>::edge_descriptor utility::graph::RingDetection< Graph >::Edge
private
template<class Graph >
typedef boost::graph_traits<Graph>::edge_iterator utility::graph::RingDetection< Graph >::EIter
private
template<class Graph >
typedef boost::graph_traits<Graph>::out_edge_iterator utility::graph::RingDetection< Graph >::OutEdgeIter
private
template<class Graph >
typedef boost::graph_traits<Graph>::vertex_descriptor utility::graph::RingDetection< Graph >::VD
private
template<class Graph >
typedef boost::graph_traits<Graph>::vertex_iterator utility::graph::RingDetection< Graph >::VIter
private

Constructor & Destructor Documentation

template<class Graph >
utility::graph::RingDetection< Graph >::RingDetection ( )
private

default constructor - needs an initialization graph

Referenced by utility::graph::RingDetection< Graph >::Clone().

template<class Graph >
utility::graph::RingDetection< Graph >::RingDetection ( const Graph graph)
inline

constructor from a graph (either GraphWithData or ConstGraph)

Parameters
graphgraph for exhaustive ring detection
Note
prefer using ConstGraph here, it is often many times faster than GraphWithData

References utility::graph::RingDetection< Graph >::Initialize(), utility::graph::RingDetection< Graph >::paths_, and utility::graph::RingDetection< Graph >::Remove().

Member Function Documentation

template<class Graph >
RingDetection* utility::graph::RingDetection< Graph >::Clone ( ) const
inline
template<class Graph >
std::vector< size_t> utility::graph::RingDetection< Graph >::CombinePaths ( const std::size_t  COMMON_vertex,
const std::vector< size_t > &  path_a,
const std::vector< size_t > &  path_b 
) const
inlineprivate

Combine two paths at their common vertex.

Parameters
COMMON_vertexvertex to join paths at
PATH_Afirst path to be combined
PATH_Bsecond path to be combined
Returns
combined path

References erraser_util::copy().

Referenced by utility::graph::RingDetection< Graph >::Remove().

template<class Graph >
const std::list< std::vector< size_t> >& utility::graph::RingDetection< Graph >::GetPaths ( ) const
inline

Get the paths between vertices in the graph.

Returns
list of paths

References utility::graph::RingDetection< Graph >::paths_.

template<class Graph >
const utility::vector1<utility::vector1<VD> > utility::graph::RingDetection< Graph >::GetRings ( ) const
inline
template<class Graph >
void utility::graph::RingDetection< Graph >::Initialize ( const Graph graph)
inlineprivate
template<class Graph >
size_t utility::graph::RingDetection< Graph >::LengthOfSmallestCycleWithVertex ( const Graph graph,
const std::size_t &  vertex,
const std::vector< size_t > &  CAN_VISIT = std::vector< size_t>() 
)
inlineprivate

LengthOfSmallestCycleWithVertex finds the length of the shortest cycle beginning at vertex.

Parameters
graphthe graph in which the vertex resides
vertexindex of the vertex to find the girth from
CAN_VISIT0 if the associated vertex cannot be visited (normally vertices that are already known to be non-cyclical), non-zero if it can
Returns
length of the shortest cycle beginning at vertex (may be undefined)
Note
any vertices that are unreachable from the vertex at vertex are skipped
this works appropriately on both directed and undirected graphs

References distance(), utility::graph::RingDetection< Graph >::graph_size_, utility::graph::RingDetection< Graph >::index_to_vd_, max(), min(), amino_acids::size, basic::options::OptionKeys::hotspot::target, and utility::graph::RingDetection< Graph >::vd_to_index_.

Referenced by utility::graph::RingDetection< Graph >::Initialize().

template<class Graph >
bool utility::graph::RingDetection< Graph >::Overlap ( const std::vector< bool > &  vertex_is_in_path_a,
const std::vector< std::size_t > &  path_b 
) const
inlineprivate

Check if two paths overlap.

Parameters
vertex_IS_IN_PATH_Aadjacency vector for path a
PATH_Bsecond path to be combined
Returns
if paths overlap

Referenced by utility::graph::RingDetection< Graph >::Remove().

template<class Graph >
void utility::graph::RingDetection< Graph >::Remove ( const std::size_t  vertex)
inlineprivate
template<class Graph >
void utility::graph::RingDetection< Graph >::SetupAdjacencyVector ( std::vector< bool > &  vertex_is_in_path,
const std::vector< size_t > &  path 
) const
inlineprivate

set the adjacency vector with a given path

Parameters
vertex_IS_IN_PATHthe vector to setup such that vertex_IS_IN_PATH[ x] == true iff x is in PATH
PATHthe path to use in setting up the adjacency vector

References utility::graph::RingDetection< Graph >::graph_size_.

Referenced by utility::graph::RingDetection< Graph >::Remove().

Member Data Documentation

template<class Graph >
size_t utility::graph::RingDetection< Graph >::graph_size_
private
template<class Graph >
boost::unordered_map<size_t, VD> utility::graph::RingDetection< Graph >::index_to_vd_
private
template<class Graph >
std::list< std::vector< size_t> > utility::graph::RingDetection< Graph >::paths_
private
template<class Graph >
std::list< std::vector< size_t> > utility::graph::RingDetection< Graph >::rings_
private
template<class Graph >
boost::unordered_map<VD, size_t> utility::graph::RingDetection< Graph >::vd_to_index_
private

The documentation for this class was generated from the following file: