Rosetta 3.4
Public Types | Public Member Functions | Protected Member Functions | Friends
core::graph::Graph Class Reference

A Graph with constant time edge insertion and deletion. Extensible. More...

#include <Graph.hh>

Inheritance diagram for core::graph::Graph:
Inheritance graph
[legend]
Collaboration diagram for core::graph::Graph:
Collaboration graph
[legend]

List of all members.

Public Types

typedef utility::vector1< Node * > NodeVector
typedef Node::EdgeListIter EdgeListIter
typedef Node::EdgeListConstIter EdgeListConstIter
typedef
utility::pointer::ReferenceCount 
parent

Public Member Functions

virtual ~Graph ()
 virtual destructor. Derived classes must ensure they've destroyed all their nodes and edges through a call to "destroy_everything" before this function is arrived at
 Graph ()
 ctor
 Graph (platform::Size num_nodes)
 num nodes ctor
 Graph (Graph const &source)
 copy ctor. Must not be called by derived class copy ctors.
Graphoperator= (Graph const &source)
 assignment operator. source and this must have the same type.
void copy_connectivity (Graph const &source)
 copy the edge connectivity from a source graph with a potentially unknown type.
platform::Size num_nodes () const
 the number of nodes in the graph
void set_num_nodes (platform::Size num_nodes)
 set the number of nodes in the graph -- deletes any existing edges in the graph
Edgeadd_edge (platform::Size node1, platform::Size node2)
 add an edge between two vertices. Invokes "create_edge" from the derived class. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge.
Edgeadd_edge (Edge const *example_edge)
 add an edge to this graph copying the data from an edge in another graph. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge.
bool get_edge_exists (platform::Size node1, platform::Size node2) const
 is an edge already present in the graph? O(V) worst case. O(1) iff all vertices have O(1) edges
void drop_all_edges ()
 delete all the edges present in the graph
void drop_all_edges_for_node (platform::Size node)
 delete all the edges for a single vertex in the graph
void print_vertices () const
 send summary information to the screen for all vertices in the graph
void output_connectivity (std::ostream &os) const
 send an edge list to the stream os.
void output_dimacs (std::ostream &os) const
 describe this graph in dimacs form to the stream os.
ObjexxFCL::FArray2D_int all_pairs_shortest_paths () const
 O(V^3). Computes all pairs shortest paths using Warshall's algorithm and writes all the path distances to the two-dimensional table.
Node const * get_node (platform::Size index) const
Nodeget_node (platform::Size index)
platform::Size num_edges () const
EdgeListConstIter const_edge_list_begin () const
 returns a const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex
EdgeListIter edge_list_begin ()
 returns a non-const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex
EdgeListConstIter const_edge_list_end () const
 returns a const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex
EdgeListIter edge_list_end ()
 returns a non-const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex
Edgefind_edge (platform::Size node1, platform::Size node2)
 returns a pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Focuses the graph on this edge for fast subsequent retrieval.
Edge const * find_edge (platform::Size node1, platform::Size node2) const
 returns a const pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Focuses the graph on this edge for fast subsequent retrieval.
Edgefocused_edge ()
 returns a pointer to the focused edge
Edge const * focused_edge () const
 returns a const-pointer to the focused edge
virtual void delete_edge (Edge *edge)
 remove an edge from the graph. (NEW AS OF 12/9/07) Never call C++'s "delete" function on an edge pointer directly. Derived classes must implement this function. If they wish to use unordered_object_pools to manage their memory
platform::Size getTotalMemoryUsage () const
 returns a count of all the memory used by every vertex and edge in a graph by invoking the polymorphic count_static_memory and count_dynamic_memory of each (possibly derived) node and edge object as well as for the (possibly derived) graph class.

Protected Member Functions

virtual platform::Size count_static_memory () const
virtual platform::Size count_dynamic_memory () const
void drop_edge (EdgeListIter edge_iter)
 remove an edge from the entire-graph edge list. Called only by class Edge during its destructor
void delete_everything ()
 deallocate all nodes and edges from the graph
virtual Nodecreate_new_node (platform::Size node_index)
 factory method for node creation, defined by derived graph classes, called by the base class
virtual Edgecreate_new_edge (platform::Size index1, platform::Size index2)
 factory method for edge creation, defined by derived graph classes, called by the base class
virtual Edgecreate_new_edge (Edge const *example_edge)
 factory method for edge copy-construction. Derived class should downcast the example_edge pointer and may read that edge's data.
boost::unordered_object_pool
< EdgeListElement > & 
edge_list_element_pool ()
 Used by class Node only, this is the pool from which edge lists are to allocate their edge lists elements from.

Friends

class Node
class Edge

Detailed Description

A Graph with constant time edge insertion and deletion. Extensible.


Member Typedef Documentation


Constructor & Destructor Documentation

core::graph::Graph::~Graph ( ) [virtual]

virtual destructor. Derived classes must ensure they've destroyed all their nodes and edges through a call to "destroy_everything" before this function is arrived at

destructor

References delete_everything().

core::graph::Graph::Graph ( )

ctor

default constructor; creates an empty graph (no nodes, no edges)

Referenced by count_static_memory().

core::graph::Graph::Graph ( platform::Size  num_nodes)

num nodes ctor

Do not call this constructor from a derived class in the initialization list, since this constructor calls the polymorphic function create_new_node, and polymorphism does not work during constructors or destructors.

Parameters:
num_ig_nodes- [in] - number of nodes that this graph will contain

References create_new_node(), and num_nodes().

core::graph::Graph::Graph ( Graph const &  source)

copy ctor. Must not be called by derived class copy ctors.

copy constructor relies on factory methods and virtual "copy_from" methods

This copy constructor should NOT be used by derived classes. At the time this is called, the identity of this has not yet been resolved -- this constructor will produce Node and Edge objects when it calls "create_new_node" and not DerivedNode or DerivedEdge objects. Derived class copy constructors should call the base class assignment operator once the initial construction has been completed.

References add_edge(), const_edge_list_begin(), const_edge_list_end(), core::graph::Edge::copy_from(), create_new_node(), and find_edge().


Member Function Documentation

Edge * core::graph::Graph::add_edge ( platform::Size  index1,
platform::Size  index2 
)

add an edge between two vertices. Invokes "create_edge" from the derived class. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge.

creates a new edge between nodes index1 and index2. Nodes do not have to be listed in order. For speed, does NOT check to see if edge already exists -- except in debug mode.

uses factory method create_new_edge and adds the created edge to the graph's edge list. Not threadsafe. Only a single thread should add edges to the graph at a time.

Parameters:
index1- [in] - index of one of the two nodes the edge is to connect
index2- [in] - index of the second of the two nodes the edge is to connect

References create_new_edge(), get_edge_exists(), core::graph::EdgeList::last(), core::graph::EdgeList::push_back(), and core::graph::Edge::set_pos_in_owners_list().

Referenced by core::scoring::EnergyGraph::add_energy_edge(), protocols::pmut_scan::PointMutScanDriver::calculate_neighbor_table(), core::scoring::TwelveANeighborGraph::conditionally_add_edge(), core::scoring::TenANeighborGraph::conditionally_add_edge(), copy_connectivity(), Graph(), core::pack::interaction_graph::SimpleInteractionGraph::initialize(), operator=(), and core::scoring::ScoreFunction::setup_for_lr2benmeth_minimization_for_respair().

Edge * core::graph::Graph::add_edge ( Edge const *  example_edge)

add an edge to this graph copying the data from an edge in another graph. Returns a pointer to the edge after its been added, allowing the calling function to immediately set data for this edge.

for use in Graph operator=

Uses the edge copy constructor so that data stored on edges of one graph may be placed rapidly into the new edge of this graph.

References core::graph::EdgeList::begin(), create_new_edge(), get_edge_exists(), core::graph::Edge::get_first_node_ind(), core::graph::Edge::get_second_node_ind(), core::graph::EdgeList::push_front(), and core::graph::Edge::set_pos_in_owners_list().

FArray2D_int core::graph::Graph::all_pairs_shortest_paths ( ) const

O(V^3). Computes all pairs shortest paths using Warshall's algorithm and writes all the path distances to the two-dimensional table.

compute all node distances and return FArray2D with that information

O(n^3)

References core::graph::EdgeList::begin(), and core::graph::EdgeList::end().

EdgeListConstIter core::graph::Graph::const_edge_list_begin ( ) const [inline]

returns a const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References core::graph::EdgeList::const_begin().

Referenced by copy_connectivity(), core::pack::create_minimization_graph(), Graph(), and operator=().

EdgeListConstIter core::graph::Graph::const_edge_list_end ( ) const [inline]

returns a const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References core::graph::EdgeList::const_end().

Referenced by copy_connectivity(), core::pack::create_minimization_graph(), Graph(), and operator=().

void core::graph::Graph::copy_connectivity ( Graph const &  source)

copy the edge connectivity from a source graph with a potentially unknown type.

copy the connectivity of the source graph, but do not copy the data stored in the nodes and edges of the source graph. Useful for when copying a graph of a different type (e.g. from an EnergyGraph into a Graph)

References add_edge(), const_edge_list_begin(), const_edge_list_end(), drop_all_edges(), and set_num_nodes().

Referenced by core::pack::stochastic_pack().

platform::Size core::graph::Graph::count_dynamic_memory ( ) const [protected, virtual]
platform::Size core::graph::Graph::count_static_memory ( ) const [protected, virtual]
Edge * core::graph::Graph::create_new_edge ( platform::Size  index1,
platform::Size  index2 
) [protected, virtual]

factory method for edge creation, defined by derived graph classes, called by the base class

factory method for edge creation Should be overriden in derived classes

Reimplemented in core::pack::interaction_graph::SimpleInteractionGraph, core::scoring::constraints::ConstraintGraph, core::scoring::EnergyGraph, core::scoring::MinimizationGraph, core::scoring::TenANeighborGraph, and core::scoring::TwelveANeighborGraph.

References boost::unordered_object_pool< T, UserAllocator >::construct().

Referenced by add_edge().

Edge * core::graph::Graph::create_new_edge ( Edge const *  example_edge) [protected, virtual]
Node * core::graph::Graph::create_new_node ( platform::Size  node_index) [protected, virtual]

factory method for node creation, defined by derived graph classes, called by the base class

factory method for node creation Should be overriden in derived classes

Reimplemented in core::pack::interaction_graph::SimpleInteractionGraph, core::scoring::constraints::ConstraintGraph, core::scoring::EnergyGraph, core::scoring::MinimizationGraph, core::scoring::TenANeighborGraph, and core::scoring::TwelveANeighborGraph.

References Node.

Referenced by Graph(), and set_num_nodes().

void core::graph::Graph::delete_edge ( Edge edge) [virtual]

remove an edge from the graph. (NEW AS OF 12/9/07) Never call C++'s "delete" function on an edge pointer directly. Derived classes must implement this function. If they wish to use unordered_object_pools to manage their memory

Reimplemented in core::pack::interaction_graph::SimpleInteractionGraph, core::scoring::constraints::ConstraintGraph, core::scoring::EnergyGraph, core::scoring::MinimizationGraph, core::scoring::TenANeighborGraph, and core::scoring::TwelveANeighborGraph.

References boost::unordered_object_pool< T, UserAllocator >::destroy().

Referenced by core::graph::delete_all_intragroup_edges(), delete_everything(), drop_all_edges(), and core::graph::Node::drop_all_edges().

void core::graph::Graph::delete_everything ( ) [protected]
void core::graph::Graph::drop_all_edges ( )

delete all the edges present in the graph

deletes all edges in the graph

References core::graph::EdgeList::begin(), delete_edge(), and core::graph::EdgeList::end().

Referenced by core::scoring::EnergyGraph::active_score_types(), copy_connectivity(), and operator=().

void core::graph::Graph::drop_all_edges_for_node ( platform::Size  node)

delete all the edges for a single vertex in the graph

deletes all edges adjacent to the node specified

Parameters:
node- [in] - index of the node

References core::graph::Node::drop_all_edges(), and get_node().

void core::graph::Graph::drop_edge ( EdgeListIter  iter) [protected]

remove an edge from the entire-graph edge list. Called only by class Edge during its destructor

removes edge from edge list at iterator iter

each edge keeps track of its position in its owner's graph's edge list so it can efficiently delete itself should it need to.

Parameters:
iter- [in] - the iterator in the non-const edge list pointing at the edge that's deleting itself
citer- [in] - the iterator in the const edge list pointing at the edge that's deleting itself

References core::graph::EdgeList::erase().

Referenced by core::graph::Edge::~Edge().

EdgeListIter core::graph::Graph::edge_list_begin ( ) [inline]

returns a non-const iterator to the beginning of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References core::graph::EdgeList::begin().

Referenced by core::graph::delete_all_intragroup_edges(), core::scoring::symmetry::SymmetricScoreFunction::setup_for_minimizing(), and core::scoring::ScoreFunction::setup_for_minimizing().

boost::unordered_object_pool< EdgeListElement >& core::graph::Graph::edge_list_element_pool ( ) [inline, protected]

Used by class Node only, this is the pool from which edge lists are to allocate their edge lists elements from.

EdgeListIter core::graph::Graph::edge_list_end ( ) [inline]

returns a non-const iterator to the end of the (unordered) edge list for the graph. this edge list contains all the edges in the graph, not simply those for a particular vertex

References core::graph::EdgeList::end().

Referenced by core::graph::delete_all_intragroup_edges().

Edge * core::graph::Graph::find_edge ( platform::Size  node1,
platform::Size  node2 
)

returns a pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Focuses the graph on this edge for fast subsequent retrieval.

returns the edge connecting node1 and node2

graph keeps a pointer to the last edge that was accessed to that search is fairly efficient.

Parameters:
node1- [in] - index of the first node
node2- [in] - index of the second node

References core::graph::Edge::same_edge().

Referenced by core::pack::compare_mingraph_and_energy_graph(), core::pack::compare_simple_inteaction_graph_alt_state_and_energy_graph(), core::scoring::EnergyGraph::find_energy_edge(), core::scoring::MinimizationGraph::find_minimization_edge(), get_edge_exists(), Graph(), core::pack::interaction_graph::SimpleInteractionGraph::initialize(), and core::scoring::ScoreFunction::setup_for_lr2benmeth_minimization_for_respair().

Edge const * core::graph::Graph::find_edge ( platform::Size  node1,
platform::Size  node2 
) const

returns a const pointer to the edge connecting nodes node1 and node2, if that edge exists in the graph, o.w. returns 0. Focuses the graph on this edge for fast subsequent retrieval.

returns the edge connecting node1 and node2 (const version)

graph keeps a pointer to the last edge that was accessed to that search is fairly efficient.

Parameters:
node1- [in] - index of the first node
node2- [in] - index of the second node

References core::graph::Edge::same_edge().

Edge const* core::graph::Graph::focused_edge ( ) const [inline]

returns a const-pointer to the focused edge

Edge* core::graph::Graph::focused_edge ( ) [inline]

returns a pointer to the focused edge

bool core::graph::Graph::get_edge_exists ( platform::Size  node1,
platform::Size  node2 
) const

is an edge already present in the graph? O(V) worst case. O(1) iff all vertices have O(1) edges

returns true if an edge between node1 and node2 exists

Parameters:
node1- [in] - index of the one of the nodes
node2- [in] - index of the other node

References find_edge().

Referenced by add_edge(), and core::pack::interaction_graph::SimpleInteractionGraph::initialize().

Node const* core::graph::Graph::get_node ( platform::Size  index) const [inline]

Referenced by protocols::toolbox::rotamer_set_operations::RigidBodyMoveRSO::alter_rotamer_set(), core::pack::rotamer_set::RotamerSet_::build_rotamers_for_concrete(), core::pack::interaction_graph::SimpleInteractionGraph::commit_change(), protocols::toolbox::pose_metric_calculators::NumberHBondsCalculator::compute_Hbonds_for_residue(), core::pack::rotamer_set::RotamerSet_::compute_one_body_energy_maps(), core::scoring::geometric_solvation::ExactOccludedHbondSolEnergy::compute_polar_group_sol_energy(), core::pack::interaction_graph::SurfacePotential::compute_pose_surface_energy(), core::pack::interaction_graph::SimpleInteractionGraph::consider_substitution(), drop_all_edges_for_node(), core::scoring::hbonds::HBondEnergy::evaluate_rotamer_background_energies(), core::scoring::hbonds::HBondEnergy::evaluate_rotamer_pair_energies(), protocols::enzdes::EnzdesFlexibleRegion::extract_lig_designability_score(), core::scoring::WaterAdductHBondPotential::fill_h2o_hbond_set(), core::scoring::hbonds::fill_hbond_set(), core::graph::find_connected_components(), protocols::enzdes::EnzdesFlexibleRegion::get_12A_neighbors(), core::scoring::EnergyGraph::get_energy_node(), core::scoring::MinimizationGraph::get_minimization_node(), core::pack::interaction_graph::SimpleInteractionGraph::get_simple_node(), core::pack::interaction_graph::SimpleInteractionGraph::initialize(), core::pack::interaction_graph::SurfaceBackgroundNode< V, E, G >::initialize_num_neighbors_counting_self(), core::pack::interaction_graph::SurfaceNode< V, E, G >::initialize_num_neighbors_counting_self(), protocols::simple_filters::RotamerBoltzmannWeight::interface_interaction_energy(), protocols::match::NumNeighborsMPM::modified_match_positions(), core::pack::interaction_graph::LinearMemNode::project_deltaE_for_substitution(), protocols::toolbox::pose_metric_calculators::NonlocalContactsCalculator::recompute(), core::pack::reinitialize_mingraph_neighborhood_for_residue(), core::pack::interaction_graph::SimpleInteractionGraph::reject_change(), core::scoring::geometric_solvation::OccludedHbondSolEnergy_onebody::residue_energy(), core::scoring::geometric_solvation::ExactOccludedHbondSolEnergy::residue_energy(), core::pack::interaction_graph::SimpleInteractionGraph::set_pose_no_initialize(), core::io::sequence_comparation::DesignContrast::setNeighbors(), core::scoring::hbonds::HBondEnergy::sidechain_sidechain_energy(), core::optimization::symmetry::SymMinimizerMap::SymMinimizerMap(), and core::pack::interaction_graph::SimpleInteractionGraph::total_energy().

Node* core::graph::Graph::get_node ( platform::Size  index) [inline]
platform::Size core::graph::Graph::getTotalMemoryUsage ( ) const

returns a count of all the memory used by every vertex and edge in a graph by invoking the polymorphic count_static_memory and count_dynamic_memory of each (possibly derived) node and edge object as well as for the (possibly derived) graph class.

References core::graph::EdgeList::const_begin(), core::graph::EdgeList::const_end(), count_dynamic_memory(), count_static_memory(), and num_nodes().

platform::Size core::graph::Graph::num_edges ( ) const [inline]

Referenced by output_dimacs().

platform::Size core::graph::Graph::num_nodes ( ) const [inline]
Graph & core::graph::Graph::operator= ( Graph const &  source)

assignment operator. source and this must have the same type.

operator = (). Relies on factory methods and virtual "copy_from" methods

operator= must only be performed on graphs of the same type e.g. an EnergyGraph may be copied from another EnergyGraph, but should not be copied from a Graph.

References add_edge(), const_edge_list_begin(), const_edge_list_end(), drop_all_edges(), and set_num_nodes().

Referenced by core::scoring::constraints::ConstraintGraph::ConstraintGraph(), core::scoring::EnergyGraph::EnergyGraph(), core::scoring::MinimizationGraph::MinimizationGraph(), core::scoring::MinimizationGraph::operator=(), core::scoring::EnergyGraph::operator=(), core::scoring::ContextGraph::operator=(), and core::scoring::constraints::ConstraintGraph::operator=().

void core::graph::Graph::output_connectivity ( std::ostream &  os) const

send an edge list to the stream os.

writes out a list of all the edges in the graph

Parameters:
os- [in] - the output stream to write to

References core::graph::EdgeList::begin(), and core::graph::EdgeList::end().

void core::graph::Graph::output_dimacs ( std::ostream &  os) const

describe this graph in dimacs form to the stream os.

writes out a connectivity description of the graph in the famous dimacs format. (where the first column "DIMACS:" should be sed'ed out)

Parameters:
os- [in] - the output stream to write to

References core::graph::EdgeList::begin(), core::graph::EdgeList::end(), num_edges(), and core::graph::EdgeList::size().

void core::graph::Graph::print_vertices ( ) const

send summary information to the screen for all vertices in the graph

calls print() on each of the nodes in the graph

void core::graph::Graph::set_num_nodes ( platform::Size  num_nodes)

Friends And Related Function Documentation

friend class Edge [friend]
friend class Node [friend]

Referenced by create_new_node().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines