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 LowMemGraph< LowMemNode, LowMemEdge > utility::graph::DefaultLowMemGraph

typedef utility::pointer::shared_ptr< DefaultLowMemGraph const > utility::graph::DefaultLowMemGraphCOP

typedef utility::pointer::shared_ptr< DefaultLowMemGraph > utility::graph::DefaultLowMemGraphOP

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

typedef utility::pointer::shared_ptr< ArrayPool< platform::Real > > utility::graph::RealArrayPoolOP

Function Documentation

bool utility::graph::all_visited ( utility::vector1< bool > const & visited )

References test.T200_Scoring::ii.

Referenced by find_connected_components().

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
	)

References utility::to_string().

Referenced by utility::graph::ArrayPool< T >::create_new_block().

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
	)

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 ObjexxFCL::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 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
	)

References breadth_first_visit_prune().

void utility::graph::delete_all_intragroup_edges	(	Graph &	g,
		utility::vector1< platform::Size > const &	node_groups
	)

References debug_assert, utility::graph::Graph::delete_edge(), utility::graph::Graph::edge_list_begin(), utility::graph::Graph::edge_list_end(), and utility::graph::Graph::num_nodes().

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

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
	)

References utility::to_string().

Referenced by utility::graph::ArrayPool< T >::create_new_block().

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
	)

References utility::graph::DirectedNode::const_outgoing_edge_list_begin(), utility::graph::DirectedNode::const_outgoing_edge_list_end(), utility::graph::Digraph::get_node(), NOT_VISITED, TEMPORARY_VISITED, and VISITED.

Referenced by topological_sort().

Variable Documentation

platform::Size const utility::graph::NOT_VISITED = 0

Referenced by find_unmarked_node(), topological_sort(), and visit().

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

Classes

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation