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

DirectedEdge *	find_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...

DirectedEdge *	find_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
Digraph *	get_owner () const
	derived class access to the owner More...

Private Member Functions
	DirectedNode ()

	DirectedNode (DirectedNode const &)

DirectedNode &	operator= (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_

Digraph *	owner_

Member Typedef Documentation

typedef DirectedEdgeListConstIterator utility::graph::DirectedNode::DirectedEdgeListConstIter

typedef DirectedEdgeListIterator utility::graph::DirectedNode::DirectedEdgeListIter

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.