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

#include <Digraph.hh>

Public Types

typedef DirectedEdgeListIterator DirectedEdgeListIter
 
typedef
DirectedEdgeListConstIterator 
DirectedEdgeListConstIter
 

Public Member Functions

virtual ~DirectedNode ()
 virtual destructor More...
 
 DirectedNode (Digraph *, platform::Size node_id)
 Main constructor, no default constructor nor copy constructor. More...
 
virtual void copy_from (DirectedNode const *source)
 invoked during graph assignment operators to copy any node data from one graph to another graph. The source node must be the same type as this node. More...
 
virtual void add_incoming_edge (DirectedEdge *edge_ptr, DirectedEdgeListIter &)
 adds an edge pointer to node's edge list as an incoming edge i.e. this node is the head of the arrow; returns an iterator to the new list element. Virtual so derived classes can observe when incoming edges are added. More...
 
virtual void add_outgoing_edge (DirectedEdge *edge_ptr, DirectedEdgeListIter &)
 adds an edge pointer to node's edge list as an outgoing edge i.e. this node is the tail of the arrow; returns an iterator to the new list element. Virtual so derived classes can observe when incoming edges are added. More...
 
void drop_edge (DirectedEdgeListIter edge_iterator)
 removes an edge iterator from the node's edge list. Only called by DirectedEdge class. More...
 
void drop_all_edges ()
 deletes all edges incident upon this node More...
 
DirectedEdge const * find_edge_to (platform::Size tail_node) const
 a "slow" (linear) search for an edge. More...
 
DirectedEdgefind_edge_to (platform::Size tail_node)
 a "slow" (linear) search for an edge. More...
 
DirectedEdge const * find_edge_from (platform::Size head_node) const
 a "slow" (linear) search for an edge. More...
 
DirectedEdgefind_edge_from (platform::Size head_node)
 a "slow" (linear) search for an edge. More...
 
virtual void print () const
 send summaray data about this node to the screen More...
 
DirectedEdgeListIter edge_list_begin ()
 returns a non-const iterator to the beginning of its edge list More...
 
DirectedEdgeListConstIter const_edge_list_begin () const
 returns a const iterator to the beginning of its edge list More...
 
DirectedEdgeListIter edge_list_end ()
 returns a non-const iterator to the end of its edge list More...
 
DirectedEdgeListConstIter const_edge_list_end () const
 returns a const iterator to the end of its edge list More...
 
DirectedEdgeListIter incoming_edge_list_begin ()
 returns a non-const iterator to the beginning of its incoming-edge list More...
 
DirectedEdgeListConstIter const_incoming_edge_list_begin () const
 returns a const iterator to the beginning of its incoming-edge list More...
 
DirectedEdgeListIter incoming_edge_list_end ()
 returns a non-const iterator to the end of its lower-edge list More...
 
DirectedEdgeListConstIter const_incoming_edge_list_end () const
 returns a const iterator to the end of its lower-edge list More...
 
DirectedEdgeListIter outgoing_edge_list_begin ()
 returns a non-const iterator to the beginning of its outgoing-edge list More...
 
DirectedEdgeListConstIter const_outgoing_edge_list_begin () const
 returns a const iterator to the beginning of its outgoing-edge list More...
 
DirectedEdgeListIter outgoing_edge_list_end ()
 returns a non-const iterator to the end of its outgoing-edge list More...
 
DirectedEdgeListConstIter const_outgoing_edge_list_end () const
 returns a const iterator to the end of its outgoing-edge list More...
 
platform::Size get_node_index () const
 the index for this node More...
 
platform::Size num_edges () const
 the number of edges incident on this node, which may include a loop edge More...
 
platform::Size num_neighbors_counting_self () const
 the number of neighbors counting "self" as a neighbor. More...
 
platform::Size indegree () const
 the number of incoming edges More...
 
platform::Size outdegree () const
 the number of outgoing edges More...
 
virtual platform::Size count_static_memory () const
 memory accounting scheme More...
 
virtual platform::Size count_dynamic_memory () const
 memory accounting scheme More...
 

Protected Member Functions

Digraphget_owner () const
 derived class access to the owner More...
 

Private Member Functions

 DirectedNode ()
 
 DirectedNode (DirectedNode const &)
 
DirectedNodeoperator= (DirectedNode &)
 

Private Attributes

platform::Size node_index_
 
platform::Size num_incident_edges_
 
platform::Size indegree_
 
platform::Size outdegree_
 
DirectedEdgeList incident_edge_list_
 
DirectedEdgeListIter first_outgoing_edge_
 
Digraphowner_
 

Member Typedef Documentation

Constructor & Destructor Documentation

utility::graph::DirectedNode::~DirectedNode ( )
virtualdefault

virtual destructor

utility::graph::DirectedNode::DirectedNode ( Digraph owner,
platform::Size  node_id 
)

Main constructor, no default constructor nor copy constructor.

utility::graph::DirectedNode::DirectedNode ( )
private

Referenced by count_static_memory().

utility::graph::DirectedNode::DirectedNode ( DirectedNode const &  )
private

Member Function Documentation

void utility::graph::DirectedNode::add_incoming_edge ( DirectedEdge edge_ptr,
DirectedEdgeListIter eiter 
)
virtual

adds an edge pointer to node's edge list as an incoming edge i.e. this node is the head of the arrow; returns an iterator to the new list element. Virtual so derived classes can observe when incoming edges are added.

Add an "incoming" edge (i.e. this is the tail node)

Parameters
edge_ptr- [in] - the new edge

References utility::graph::DirectedEdgeList::begin(), incident_edge_list_, indegree_, utility::graph::DirectedEdgeList::insert(), and num_incident_edges_.

void utility::graph::DirectedNode::add_outgoing_edge ( DirectedEdge edge_ptr,
DirectedEdgeListIter eiter 
)
virtual

adds an edge pointer to node's edge list as an outgoing edge i.e. this node is the tail of the arrow; returns an iterator to the new list element. Virtual so derived classes can observe when incoming edges are added.

Add an "outgoing" edge (i.e. this is the head node)

Parameters
edge_ptr- [in] - the new edge

References utility::graph::DirectedEdgeList::end(), first_outgoing_edge_, incident_edge_list_, utility::graph::DirectedEdgeList::insert(), num_incident_edges_, and outdegree_.

DirectedEdgeListConstIter utility::graph::DirectedNode::const_edge_list_begin ( ) const
inline

returns a const iterator to the beginning of its edge list

References utility::graph::DirectedEdgeList::const_begin(), and incident_edge_list_.

DirectedEdgeListConstIter utility::graph::DirectedNode::const_edge_list_end ( ) const
inline

returns a const iterator to the end of its edge list

References utility::graph::DirectedEdgeList::const_end(), and incident_edge_list_.

DirectedEdgeListConstIter utility::graph::DirectedNode::const_incoming_edge_list_begin ( ) const
inline

returns a const iterator to the beginning of its incoming-edge list

References utility::graph::DirectedEdgeList::const_begin(), and incident_edge_list_.

DirectedEdgeListConstIter utility::graph::DirectedNode::const_incoming_edge_list_end ( ) const
inline

returns a const iterator to the end of its lower-edge list

References first_outgoing_edge_.

DirectedEdgeListConstIter utility::graph::DirectedNode::const_outgoing_edge_list_begin ( ) const
inline

returns a const iterator to the beginning of its outgoing-edge list

References first_outgoing_edge_.

Referenced by utility::graph::visit().

DirectedEdgeListConstIter utility::graph::DirectedNode::const_outgoing_edge_list_end ( ) const
inline

returns a const iterator to the end of its outgoing-edge list

References utility::graph::DirectedEdgeList::const_end(), and incident_edge_list_.

Referenced by utility::graph::visit().

void utility::graph::DirectedNode::copy_from ( DirectedNode const *  source)
virtual

invoked during graph assignment operators to copy any node data from one graph to another graph. The source node must be the same type as this node.

copy-from for use in Digraph::operator= and copy ctors; derived classes must define their own version of this function

platform::Size utility::graph::DirectedNode::count_dynamic_memory ( ) const
virtual

memory accounting scheme

recursively descend through heirarchy accounting for heap memory usage. Each derived class in the heirarchy should recursively add the amount of dynamic memory its parent allocates by calling parent::count_dynamic_memory

References num_incident_edges_.

platform::Size utility::graph::DirectedNode::count_static_memory ( ) const
virtual

memory accounting scheme

called on most-derived class. The most-derived class should NOT recursively call this method on its parent class. The sizeof function will handle the whole DirectedNode (or DerivedDirectedNode).

References DirectedNode().

void utility::graph::DirectedNode::drop_all_edges ( )

deletes all edges incident upon this node

As edges delete themselves, they invalidate any iterators that point to their (former) positions in the node and graph edge lists. Therefore, before calling delete on an edge object, one must grab the next iterator in a list. Below, nextiter copies iter and is incremented before iter's edge is deleted. Note also that "++iter" does not appear in the for loop.

References utility::graph::DirectedEdgeList::begin(), utility::graph::Digraph::delete_edge(), utility::graph::DirectedEdgeList::end(), incident_edge_list_, and owner_.

Referenced by utility::graph::Digraph::drop_all_edges_for_node().

void utility::graph::DirectedNode::drop_edge ( DirectedEdgeListIter  eiter)

removes an edge iterator from the node's edge list. Only called by DirectedEdge class.

edges efficiently delete themselves from the edge lists of the nodes they are incident upon by keeping a pair of iterators. DirectedEdges request nodes delete them by handing the iterator back to the node.

Parameters
edge- [in] - the iterator for this node's edge list that points at the edge which is trying to delete itself

References utility::graph::DirectedEdgeList::erase(), first_outgoing_edge_, incident_edge_list_, indegree_, node_index_, num_incident_edges_, and outdegree_.

Referenced by utility::graph::DirectedEdge::~DirectedEdge().

DirectedEdgeListIter utility::graph::DirectedNode::edge_list_begin ( )
inline

returns a non-const iterator to the beginning of its edge list

References utility::graph::DirectedEdgeList::begin(), and incident_edge_list_.

DirectedEdgeListIter utility::graph::DirectedNode::edge_list_end ( )
inline

returns a non-const iterator to the end of its edge list

References utility::graph::DirectedEdgeList::end(), and incident_edge_list_.

DirectedEdge const * utility::graph::DirectedNode::find_edge_from ( platform::Size  other_node) const

a "slow" (linear) search for an edge.

Constant time if each vertex has a constant number of edges. DirectedEdges are identified by the index of the node to which the edge connects this node. Returns NULL when there is no such connecting edge.

Parameters
other_node- [in] - the index of the node that the desired edge connects this node to
DirectedEdge * utility::graph::DirectedNode::find_edge_from ( platform::Size  head_node)

a "slow" (linear) search for an edge.

non-const edge finding method; changes no data, but returns a non-const pointer

References utility::graph::DirectedEdgeList::begin(), basic::options::OptionKeys::cutoutdomain::end, first_outgoing_edge_, incident_edge_list_, node_index_, and basic::options::OptionKeys::cutoutdomain::start.

DirectedEdge const * utility::graph::DirectedNode::find_edge_to ( platform::Size  other_node) const

a "slow" (linear) search for an edge.

Constant time if each vertex has a constant number of edges. DirectedEdges are identified by the index of the node to which the edge connects this node. Returns NULL when there is no such connecting edge.

Parameters
other_node- [in] - the index of the node that the desired edge connects this node to
DirectedEdge * utility::graph::DirectedNode::find_edge_to ( platform::Size  tail_node)

a "slow" (linear) search for an edge.

non-const edge finding method; changes no data, but returns a non-const pointer

References basic::options::OptionKeys::cutoutdomain::end, utility::graph::DirectedEdgeList::end(), first_outgoing_edge_, incident_edge_list_, node_index_, and basic::options::OptionKeys::cutoutdomain::start.

platform::Size utility::graph::DirectedNode::get_node_index ( ) const
inline

the index for this node

References node_index_.

Referenced by print().

Digraph* utility::graph::DirectedNode::get_owner ( ) const
inlineprotected

derived class access to the owner

References owner_.

DirectedEdgeListIter utility::graph::DirectedNode::incoming_edge_list_begin ( )
inline

returns a non-const iterator to the beginning of its incoming-edge list

References utility::graph::DirectedEdgeList::begin(), and incident_edge_list_.

DirectedEdgeListIter utility::graph::DirectedNode::incoming_edge_list_end ( )
inline

returns a non-const iterator to the end of its lower-edge list

References first_outgoing_edge_.

platform::Size utility::graph::DirectedNode::indegree ( ) const
inline

the number of incoming edges

References indegree_.

platform::Size utility::graph::DirectedNode::num_edges ( ) const
inline

the number of edges incident on this node, which may include a loop edge

References num_incident_edges_.

platform::Size utility::graph::DirectedNode::num_neighbors_counting_self ( ) const
inline

the number of neighbors counting "self" as a neighbor.

References num_incident_edges_.

DirectedNode& utility::graph::DirectedNode::operator= ( DirectedNode )
private
platform::Size utility::graph::DirectedNode::outdegree ( ) const
inline

the number of outgoing edges

References outdegree_.

DirectedEdgeListIter utility::graph::DirectedNode::outgoing_edge_list_begin ( )
inline

returns a non-const iterator to the beginning of its outgoing-edge list

References first_outgoing_edge_.

DirectedEdgeListIter utility::graph::DirectedNode::outgoing_edge_list_end ( )
inline

returns a non-const iterator to the end of its outgoing-edge list

References utility::graph::DirectedEdgeList::end(), and incident_edge_list_.

void utility::graph::DirectedNode::print ( ) const
virtual

send summaray data about this node to the screen

virtual function to print node to standard out

References utility::graph::DirectedEdgeList::const_begin(), utility::graph::DirectedEdgeList::const_end(), utility::io::oc::cout, get_node_index(), and incident_edge_list_.

Member Data Documentation

DirectedEdgeListIter utility::graph::DirectedNode::first_outgoing_edge_
private
DirectedEdgeList utility::graph::DirectedNode::incident_edge_list_
private
platform::Size utility::graph::DirectedNode::indegree_
private
platform::Size utility::graph::DirectedNode::node_index_
private
platform::Size utility::graph::DirectedNode::num_incident_edges_
private
platform::Size utility::graph::DirectedNode::outdegree_
private
Digraph* utility::graph::DirectedNode::owner_
private

Referenced by drop_all_edges(), and get_owner().


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