#include <RingDetection.hh>

Inheritance diagram for utility::graph::RingDetection< Graph >:

Public Member Functions
	RingDetection (const Graph &graph)
	constructor from a graph (either GraphWithData or ConstGraph) More...

RingDetection *	Clone () 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, VD >	index_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

◆ Edge

template<class Graph >

typedef boost::graph_traits<Graph>::edge_descriptor utility::graph::RingDetection< Graph >::Edge

private

◆ EIter

template<class Graph >

typedef boost::graph_traits<Graph>::edge_iterator utility::graph::RingDetection< Graph >::EIter

private

◆ OutEdgeIter

template<class Graph >

typedef boost::graph_traits<Graph>::out_edge_iterator utility::graph::RingDetection< Graph >::OutEdgeIter

private

◆ VD

template<class Graph >

typedef boost::graph_traits<Graph>::vertex_descriptor utility::graph::RingDetection< Graph >::VD

private

◆ VIter

template<class Graph >

typedef boost::graph_traits<Graph>::vertex_iterator utility::graph::RingDetection< Graph >::VIter

private

Constructor & Destructor Documentation

◆ RingDetection() [1/2]

template<class Graph >

utility::graph::RingDetection< Graph >::RingDetection ( )

private

default constructor - needs an initialization graph

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

◆ RingDetection() [2/2]

template<class Graph >

utility::graph::RingDetection< Graph >::RingDetection ( const Graph & graph )

inline

constructor from a graph (either GraphWithData or ConstGraph)

Parameters

graph graph 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

◆ Clone()

template<class Graph >

RingDetection* utility::graph::RingDetection< Graph >::Clone ( ) const

inline

clone the object

References utility::graph::RingDetection< Graph >::RingDetection().

◆ CombinePaths()

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_vertex	vertex to join paths at
PATH_A	first path to be combined
PATH_B	second path to be combined

Returns: combined path

References erraser_util::copy().

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

◆ GetPaths()

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

◆ GetRings()

template<class Graph >

const utility::vector1<utility::vector1<VD> > utility::graph::RingDetection< Graph >::GetRings ( ) const

inline

Get all rings in the graph.

Returns: list of rings (all closed paths)

References utility::graph::RingDetection< Graph >::index_to_vd_, basic::options::OptionKeys::rings::rings, and utility::graph::RingDetection< Graph >::rings_.

◆ Initialize()

template<class Graph >

void utility::graph::RingDetection< Graph >::Initialize ( const Graph & graph )

inlineprivate

initialize paths_ with all edges from graph (which is either a GraphWithData or a ConstGraph)

References utility::graph::RingDetection< Graph >::graph_size_, utility::graph::RingDetection< Graph >::index_to_vd_, utility::graph::RingDetection< Graph >::LengthOfSmallestCycleWithVertex(), utility::graph::RingDetection< Graph >::paths_, basic::options::OptionKeys::hotspot::target, and utility::graph::RingDetection< Graph >::vd_to_index_.

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

◆ LengthOfSmallestCycleWithVertex()

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

graph	the graph in which the vertex resides
vertex	index of the vertex to find the girth from
CAN_VISIT	0 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 build_jacobian::distance, utility::graph::RingDetection< Graph >::graph_size_, create_a3b_hbs::i, utility::graph::RingDetection< Graph >::index_to_vd_, max(), min(), dummy-distribution::row, subloop_histogram::size, basic::options::OptionKeys::hotspot::target, and utility::graph::RingDetection< Graph >::vd_to_index_.

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

◆ Overlap()

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_A	adjacency vector for path a
PATH_B	second path to be combined

Returns: if paths overlap

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

◆ Remove()

template<class Graph >

void utility::graph::RingDetection< Graph >::Remove ( const std::size_t vertex )

inlineprivate

Remove vertices, store new paths and rings.

Parameters

vertex vertex to be removed

References utility::graph::RingDetection< Graph >::CombinePaths(), utility::graph::RingDetection< Graph >::graph_size_, utility::graph::RingDetection< Graph >::Overlap(), SewAssembler::path_size, utility::graph::RingDetection< Graph >::paths_, utility::graph::RingDetection< Graph >::rings_, and utility::graph::RingDetection< Graph >::SetupAdjacencyVector().

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

◆ SetupAdjacencyVector()

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_PATH	the vector to setup such that vertex_IS_IN_PATH[ x] == true iff x is in PATH
PATH	the path to use in setting up the adjacency vector

References utility::graph::RingDetection< Graph >::graph_size_, and closure_error::path.

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

Member Data Documentation

◆ graph_size_

template<class Graph >

size_t utility::graph::RingDetection< Graph >::graph_size_

private

size of the graph

Referenced by utility::graph::RingDetection< Graph >::Initialize(), utility::graph::RingDetection< Graph >::LengthOfSmallestCycleWithVertex(), utility::graph::RingDetection< Graph >::Remove(), and utility::graph::RingDetection< Graph >::SetupAdjacencyVector().

◆ index_to_vd_

template<class Graph >

boost::unordered_map<size_t, VD> utility::graph::RingDetection< Graph >::index_to_vd_

private

Referenced by utility::graph::RingDetection< Graph >::GetRings(), utility::graph::RingDetection< Graph >::Initialize(), and utility::graph::RingDetection< Graph >::LengthOfSmallestCycleWithVertex().

◆ paths_

template<class Graph >

std::list< std::vector< size_t> > utility::graph::RingDetection< Graph >::paths_

private

paths between vertices in the graph

Referenced by utility::graph::RingDetection< Graph >::GetPaths(), utility::graph::RingDetection< Graph >::Initialize(), utility::graph::RingDetection< Graph >::Remove(), and utility::graph::RingDetection< Graph >::RingDetection().

◆ rings_

template<class Graph >

std::list< std::vector< size_t> > utility::graph::RingDetection< Graph >::rings_

private

rings in the graph

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

◆ vd_to_index_

template<class Graph >

boost::unordered_map<VD, size_t> utility::graph::RingDetection< Graph >::vd_to_index_

private

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

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

src/utility/graph/RingDetection.hh

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ Edge

◆ EIter

◆ OutEdgeIter

◆ VD

◆ VIter

Constructor & Destructor Documentation

◆ RingDetection() [1/2]

◆ RingDetection() [2/2]

Member Function Documentation

◆ Clone()

◆ CombinePaths()

◆ GetPaths()

◆ GetRings()

◆ Initialize()

◆ LengthOfSmallestCycleWithVertex()

◆ Overlap()

◆ Remove()

◆ SetupAdjacencyVector()

Member Data Documentation

◆ graph_size_

◆ index_to_vd_

◆ paths_

◆ rings_

◆ vd_to_index_

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