Rosetta
2021.16

A Graph with constant time edge insertion and deletion. Extensible. More...
#include <Graph.hh>
Public Types  
typedef utility::vector1< Node * >  NodeVector 
typedef Node::EdgeListIter  EdgeListIter 
typedef Node::EdgeListConstIter  EdgeListConstIter 
typedef utility::VirtualBase  parent 
Public Member Functions  
GraphCOP  get_self_ptr () const 
self pointers More...  
GraphOP  get_self_ptr () 
~Graph () override  
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 More...  
Graph ()  
ctor More...  
Graph (platform::Size num_nodes)  
num nodes ctor More...  
Graph (Graph const &source)  
copy ctor. Must not be called by derived class copy ctors. More...  
Graph &  operator= (Graph const &source) 
assignment operator. source and this must have the same type. More...  
void  copy_connectivity (Graph const &source) 
copy the edge connectivity from a source graph with a potentially unknown type. More...  
platform::Size  num_nodes () const 
the number of nodes in the graph More...  
void  set_num_nodes (platform::Size num_nodes) 
set the number of nodes in the graph – deletes any existing edges in the graph More...  
Edge *  add_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. More...  
Edge *  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. More...  
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 More...  
void  drop_all_edges () 
delete all the edges present in the graph More...  
void  drop_all_edges_for_node (platform::Size node) 
delete all the edges for a single vertex in the graph More...  
void  print_vertices () const 
send summary information to the screen for all vertices in the graph More...  
void  output_connectivity (std::ostream &os) const 
send an edge list to the stream os. More...  
void  output_dimacs (std::ostream &os) const 
describe this graph in dimacs form to the stream os. More...  
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 twodimensional table. More...  
Node const *  get_node (platform::Size index) const 
Node *  get_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 More...  
EdgeListIter  edge_list_begin () 
returns a nonconst 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 More...  
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 More...  
EdgeListIter  edge_list_end () 
returns a nonconst 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 More...  
Edge *  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. More...  
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. More...  
Edge *  focused_edge () 
returns a pointer to the focused edge More...  
Edge const *  focused_edge () const 
returns a constpointer to the focused edge More...  
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 More...  
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. More...  
Public Member Functions inherited from utility::VirtualBase  
VirtualBase ()=default  
Default constructor. More...  
virtual  ~VirtualBase ()=default 
The virtual destructor is one of the main reasons for the VirtualBase class. More...  
VirtualBase (VirtualBase const &)=default  
VirtualBase (VirtualBase &&)=default  
VirtualBase &  operator= (VirtualBase const &)=default 
VirtualBase &  operator= (VirtualBase &&)=default 
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 entiregraph edge list. Called only by class Edge during its destructor More...  
void  delete_everything () 
deallocate all nodes and edges from the graph More...  
virtual void  delete_node (Node *) 
Only called by delete_everything(). Does not need to be overriden unless derived class generates nodes in a fancy way. More...  
virtual Node *  create_new_node (platform::Size node_index) 
factory method for node creation, defined by derived graph classes, called by the base class More...  
virtual Edge *  create_new_edge (platform::Size index1, platform::Size index2) 
factory method for edge creation, defined by derived graph classes, called by the base class More...  
virtual Edge *  create_new_edge (Edge const *example_edge) 
factory method for edge copyconstruction. Derived class should downcast the example_edge pointer and may read that edge's data. More...  
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. More...  
Private Attributes  
platform::Size  num_nodes_ 
NodeVector  nodes_ 
platform::Size  num_edges_ 
boost::unordered_object_pool < EdgeListElement > *  edge_list_element_pool_ 
the pool from which edge lists are to allocate their edge list elements More...  
EdgeList  edge_list_ 
boost::unordered_object_pool < Edge > *  edge_pool_ 
the pool from which class Graph allocates Edge objects. Not used by derived classes More...  
Edge *  focused_edge_ 
Quickaccess to a frequently needed edge – the most recently sought edge in a call to find_edge() or the most recently added edge. More...  
Friends  
class  Node 
class  Edge 

override 
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(), edge_list_element_pool_, and edge_pool_.
utility::graph::Graph::Graph  (  ) 
ctor
default constructor; creates an empty graph (no nodes, no edges)
Referenced by count_static_memory().
utility::graph::Graph::Graph  (  platform::Size  num_nodes  ) 
num nodes ctor
Danger! Danger! The C++ standard prevents function overrides from being called from a base class constructor. If you use this constructor without subsequently calling set_num_nodes(), you'll end up with a graph populated with utility::graph::Node nodes instead of derived nodes.
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.
num_ig_nodes   [in]  number of nodes that this graph will contain 
References create_new_node(), test.T200_Scoring::ii, nodes_, and num_nodes().
utility::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(), utility::graph::Edge::copy_from(), create_new_node(), find_edge(), test.T200_Scoring::ii, nodes_, and num_nodes_.
Edge * utility::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.
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(), debug_assert, edge_list_, focused_edge_, get_edge_exists(), utility::graph::EdgeList::last(), num_edges_, utility::graph::EdgeList::push_back(), utility::graph::Edge::set_pos_in_owners_list(), and erraser_analysis::temp.
Referenced by copy_connectivity(), Graph(), and operator=().
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 utility::graph::EdgeList::begin(), create_new_edge(), debug_assert, edge_list_, focused_edge_, get_edge_exists(), utility::graph::Edge::get_first_node_ind(), utility::graph::Edge::get_second_node_ind(), num_edges_, utility::graph::EdgeList::push_front(), and utility::graph::Edge::set_pos_in_owners_list().
FArray2D_int utility::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 twodimensional table.
compute all node distances and return FArray2D with that information
O(n^3)
References debug_assert, edge_list_, test.T200_Scoring::ii, and num_nodes_.

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 utility::graph::EdgeList::const_begin(), and edge_list_.
Referenced by copy_connectivity(), Graph(), and operator=().

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 utility::graph::EdgeList::const_end(), and edge_list_.
Referenced by copy_connectivity(), Graph(), and operator=().
void utility::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(), num_nodes_, and set_num_nodes().

protectedvirtual 
References num_edges_, and num_nodes_.
Referenced by getTotalMemoryUsage().

protectedvirtual 
References Graph().
Referenced by getTotalMemoryUsage().

protectedvirtual 
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
References edge_pool_.
Referenced by add_edge().
factory method for edge copyconstruction. Derived class should downcast the example_edge pointer and may read that edge's data.
References edge_pool_, utility::graph::Edge::get_first_node_ind(), and utility::graph::Edge::get_second_node_ind().

protectedvirtual 
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
References Node.
Referenced by Graph(), and set_num_nodes().

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
References edge_pool_.
Referenced by utility::graph::delete_all_intragroup_edges(), delete_everything(), utility::graph::Node::drop_all_edges(), and drop_all_edges().

protected 
deallocate all nodes and edges from the graph
deletes each edge in the graph and then deletes each node
its important to note that nodes must outlive their incident edges
References utility::graph::EdgeList::begin(), delete_edge(), delete_node(), edge_list_, utility::graph::EdgeList::end(), focused_edge_, test.T200_Scoring::ii, nodes_, and num_nodes_.
Referenced by set_num_nodes(), and ~Graph().

protectedvirtual 
Only called by delete_everything(). Does not need to be overriden unless derived class generates nodes in a fancy way.
Referenced by delete_everything().
void utility::graph::Graph::drop_all_edges  (  ) 
delete all the edges present in the graph
deletes all edges in the graph
References utility::graph::EdgeList::begin(), delete_edge(), edge_list_, and utility::graph::EdgeList::end().
Referenced by copy_connectivity(), and operator=().
void utility::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
node   [in]  index of the node 
References utility::graph::Node::drop_all_edges(), and get_node().

protected 
remove an edge from the entiregraph 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.
iter   [in]  the iterator in the nonconst 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 edge_list_, utility::graph::EdgeList::erase(), focused_edge_, and num_edges_.
Referenced by utility::graph::Edge::~Edge().

inline 
returns a nonconst 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 utility::graph::EdgeList::begin(), and edge_list_.
Referenced by utility::graph::delete_all_intragroup_edges().

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

inline 
returns a nonconst 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 edge_list_, and utility::graph::EdgeList::end().
Referenced by utility::graph::delete_all_intragroup_edges().
Edge * utility::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.
node1   [in]  index of the first node 
node2   [in]  index of the second node 
References focused_edge_, nodes_, and utility::graph::Edge::same_edge().
Referenced by get_edge_exists(), and Graph().
Edge const * utility::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.
node1   [in]  index of the first node 
node2   [in]  index of the second node 
References focused_edge_, nodes_, and utility::graph::Edge::same_edge().

inline 
returns a pointer to the focused edge
References focused_edge_.

inline 
returns a constpointer to the focused edge
References focused_edge_.
bool utility::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
node1   [in]  index of the one of the nodes 
node2   [in]  index of the other node 
References find_edge().
Referenced by add_edge().

inline 
References debug_assert, ObjexxFCL::index(), nodes_, and num_nodes_.
Referenced by drop_all_edges_for_node(), and utility::graph::find_connected_components().

inline 
References debug_assert, ObjexxFCL::index(), nodes_, and num_nodes_.

inline 
self pointers

inline 
platform::Size utility::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 utility::graph::EdgeList::const_begin(), utility::graph::EdgeList::const_end(), count_dynamic_memory(), count_static_memory(), edge_list_, test.T200_Scoring::ii, nodes_, and num_nodes().

inline 
References num_edges_.
Referenced by output_dimacs().

inline 
the number of nodes in the graph
References num_nodes_.
Referenced by utility::graph::delete_all_intragroup_edges(), utility::graph::find_connected_components(), getTotalMemoryUsage(), Graph(), and set_num_nodes().
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(), test.T200_Scoring::ii, nodes_, num_nodes_, and set_num_nodes().
void utility::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
os   [in]  the output stream to write to 
References demo.D060_Folding::counter, and edge_list_.
void utility::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)
os   [in]  the output stream to write to 
References edge_list_, num_edges(), num_nodes_, and utility::graph::EdgeList::size().
void utility::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
References test.T200_Scoring::ii, nodes_, and num_nodes_.
void utility::graph::Graph::set_num_nodes  (  platform::Size  num_nodes  ) 
set the number of nodes in the graph – deletes any existing edges in the graph
alternative to integer constructor; first create an empty graph and later tell the graph how many nodes it has. If the graph is not already empty, it will delete everything its holding.
References create_new_node(), delete_everything(), test.T200_Scoring::ii, nodes_, num_nodes(), and num_nodes_.
Referenced by copy_connectivity(), and operator=().

friend 

friend 
Referenced by create_new_node().

private 

private 
the pool from which edge lists are to allocate their edge list elements
Referenced by edge_list_element_pool(), and ~Graph().

private 
the pool from which class Graph allocates Edge objects. Not used by derived classes
Referenced by create_new_edge(), delete_edge(), and ~Graph().

mutableprivate 
Quickaccess to a frequently needed edge – the most recently sought edge in a call to find_edge() or the most recently added edge.
Referenced by add_edge(), delete_everything(), drop_edge(), find_edge(), and focused_edge().

private 
Referenced by delete_everything(), utility::graph::Edge::Edge(), find_edge(), get_node(), getTotalMemoryUsage(), Graph(), operator=(), print_vertices(), and set_num_nodes().

private 
Referenced by add_edge(), count_dynamic_memory(), drop_edge(), and num_edges().

private 