/** Djk Package: Procedures implementing Dijkstra's shortest path search algorithm. **/

#include <opnet.h>

/* Header file defining Djk package types and prototypes. */
#include "djk.h"

/* Node ID generator */
int			DjkI_Node_Id = 0;

void
djk_path_list_combine (List *list_a_ptr, List *list_b_ptr, List *dest_list_ptr)
	{
	int			list_a_size, list_b_size, list_index;
	DjkT_Node *	last_a_path_node_ptr;
	DjkT_Node *	path_node_ptr;

	/** Combine list a and list b into dest_list_ptr.  Note that this        **/
	/** procedure copies the elements of a and b.  If a's destination        **/
	/** is the same as b's source, then that element is not copied           **/
	/** twice. Assumes that the destination list has already been allocated. **/
	FIN (djk_path_list_combine (list_a_ptr, list_b_ptr, dest_list_ptr));

	/* Loop through a's list first. */
	list_a_size = op_prg_list_size (list_a_ptr);
	
	for (list_index = 0; list_index < list_a_size; list_index++)
		{
		/* Get path node. */
		path_node_ptr = (DjkT_Node *) op_prg_list_access (list_a_ptr, list_index);

		/* Append the node to the list. */
		op_prg_list_insert (dest_list_ptr, path_node_ptr, OPC_LISTPOS_TAIL);
		}
	
	/* Store the last path ID from list a. */
	last_a_path_node_ptr = path_node_ptr;

	/* Loop through b's list next. */
	list_b_size = op_prg_list_size (list_b_ptr);
	
	for (list_index = 0; list_index < list_b_size; list_index++)
		{
		/* Get path node. */
		path_node_ptr = (DjkT_Node *) op_prg_list_access (list_b_ptr, list_index);

		/* Check to see if a's destination matches b's source. */
		if ((list_index == 0) && (last_a_path_node_ptr == path_node_ptr))
			continue;

		/* Append the node to the list. */
		op_prg_list_insert (dest_list_ptr, path_node_ptr, OPC_LISTPOS_TAIL);
		}
	
	FOUT;
	}

int
djk_node_stub_check (DjkT_Node *node_ptr)
	{
	int				is_stub;

	/** Return OPC_TRUE if node is a stub, OPC_FALSE if not. **/
	FIN (djk_node_stub_check (node_ptr));

	/* Currently, we look at the number of connections to determine */
	/* whether or not the node is a stub.                           */
	if (op_prg_list_size (node_ptr->connection_list_ptr) > 1)
		is_stub = OPC_FALSE;
	else
		is_stub = OPC_TRUE;

	FRET (is_stub);
	}

DjkT_Node *
djk_node_search (List *node_list_ptr, int options)
	{
	DjkT_Node *		node_ptr = OPC_NIL;
	DjkT_Node *		cur_node_ptr;
	int				node_index, node_count, found_index;

	/** Search for a node based on the criteria set in the options argument. **/
	FIN (djk_node_search (node_list_ptr, options));

	/* Loop through vertices and try to find the best match. */
	node_count = op_prg_list_size (node_list_ptr);

	/* If list is empty, then return a NIL node. */
	if (node_count == 0)
		{
		FRET (OPC_NIL);
		}

	for (node_index = 0; node_index < node_count; node_index++)
		{
		/* Get current node. */
		cur_node_ptr = (DjkT_Node *) op_prg_list_access (node_list_ptr, node_index);

		if (options & DJKC_NODE_SEARCH_LEAST_COST)
			{
			if (node_index == 0)
				{
				found_index = node_index;
				node_ptr = cur_node_ptr;
				}
			else
				{
				if (cur_node_ptr->root_distance < node_ptr->root_distance)
					{
					found_index = node_index;
					node_ptr = cur_node_ptr;
					}
				}
			}
		}

	/* If we found something then we might want to delete it from the input list. */
	if ((options & DJKC_NODE_SEARCH_REMOVE) && (node_ptr != OPC_NIL))
		op_prg_list_remove (node_list_ptr, found_index);

	FRET (node_ptr);
	}

DjkT_Node *
djk_node_lookup (List *node_list_ptr, DjkT_Node *node_ptr)
	{
	DjkT_Node *				cur_node_ptr;
	int						node_index, node_count;

	/** Lookup and return a node that matches the given node. **/
	/** Returns OPC_NIL if no match is found.                 **/
	FIN (djk_node_lookup (node_list_ptr, node_ptr));

	/* Loop through the node list and try to find a match. */
	node_count = op_prg_list_size (node_list_ptr);
	for (node_index = 0; node_index < node_count; node_index++)
		{
		/* Get current node. */
		cur_node_ptr = (DjkT_Node *) op_prg_list_access (node_list_ptr, node_index);

		if (cur_node_ptr == node_ptr)
			FRET (node_ptr);
		}

	FRET (OPC_NIL);
	}

void
djk_node_next_hop_calc (DjkT_Node *current_node_ptr, DjkT_Node *parent_node_ptr)
	{
	DjkT_Node *		parent_hop_ptr;
	DjkT_Node *		current_hop_ptr;
	int				hop_count, hop_index;
	DjkT_Node *		last_hop_ptr;
	int				last_hop;
	int				current_hop_count;

	/** Recalculate the path from the root to the current node.   **/
	/** Assumes that the correct path has already been calculated **/
	/** for the parent node.                                      **/
	FIN (djk_node_next_hop_calc (current_node_ptr, parent_node_ptr));
	
	/* Before adding the parent hops, re-initialize the current hop list */
	/* to include only the current node.                               */
	current_hop_count = op_prg_list_size (current_node_ptr->path_list_ptr);
	if (current_hop_count > 1)
		{
		/* Get last hop. */
		last_hop_ptr = (DjkT_Node *) op_prg_list_access (current_node_ptr->path_list_ptr, OPC_LISTPOS_TAIL);
		
		/* Clear the list. */
		while (op_prg_list_size (current_node_ptr->path_list_ptr) > 0)
			op_prg_list_remove (current_node_ptr->path_list_ptr, OPC_LISTPOS_HEAD);
		
		/* And re-add the last element. */
		op_prg_list_insert (current_node_ptr->path_list_ptr, last_hop_ptr, OPC_LISTPOS_TAIL);
		}
	else
		{
		/* The path list is currently empty, add a hop that represents the node itself. */
		op_prg_list_insert (current_node_ptr->path_list_ptr, current_node_ptr, OPC_LISTPOS_TAIL);
		}

	/* Loop through all the hops in the parent; copy and add them to current node. */
	hop_count = op_prg_list_size (parent_node_ptr->path_list_ptr);
	for (hop_index = 0; hop_index < hop_count; hop_index++)
		{
		/* Get the current hop. */
		parent_hop_ptr = (DjkT_Node *) op_prg_list_access (parent_node_ptr->path_list_ptr, hop_index);

		/* Add the new hop to the current node list. */
		op_prg_list_insert (current_node_ptr->path_list_ptr, parent_hop_ptr, hop_index);
		} 

	FOUT;
	}

void
djk_shortest_paths_calc (List *node_list_ptr, DjkT_Node *root_node_ptr, int options)
	{
	List *			candidate_list_ptr;
	List *			shortest_path_list_ptr;

	/** Takes as input a list of DjkT_Node.  The client of this procedure creates **/
	/** this list, which represents a graph whose edges are bidirectional.  By    **/
	/** default, this function requires bidirectional edges between two nodes in  **/
	/** order to consider a path for inclusion.  For example, for a path to exist **/
	/** from A to B, a path must exist from B to A.  The representation of the    **/
	/** graph does not enforce this, and this behavior may be changed in the      **/
	/** future.  The input list is modified to contain a hop list of nodes for    **/
	/** each node, as well as the total cost of the path.  All paths are          **/
	/** calculated for the list of nodes given, with root_node_ptr as the         **/
	/** start of all paths.                                                       **/

	/** Note that the options argument exists for further expansion.  Currently   **/
	/** no options are defined.                                                   **/

	FIN (djk_shortest_paths_calc (node_list_ptr, root_node_ptr, options));

	/* Initialize the root node to contain itself in the initial path list. */
	op_prg_list_insert (root_node_ptr->path_list_ptr, root_node_ptr, OPC_LISTPOS_TAIL);

	/* Create a candidate list and a shortest path list, and pass it to  */	
	/* an auxillary function.  The candidate list is initially empty and */
	/* the shortest path list contains only the root node.               */
	candidate_list_ptr = op_prg_list_create ();
	shortest_path_list_ptr = op_prg_list_create ();
	op_prg_list_insert (shortest_path_list_ptr, root_node_ptr, OPC_LISTPOS_TAIL);
	djk_path_list_calc (node_list_ptr, candidate_list_ptr, shortest_path_list_ptr, root_node_ptr);

	/* Now go on to the next phase of the algorithm, which is adding stub nodes. */
	djk_stub_nodes_add (node_list_ptr, root_node_ptr);

	FOUT;
	}

void
djk_stub_nodes_add (List *node_list_ptr, DjkT_Node *root_node_ptr)
	{
	int					num_nodes, node_index;
	DjkT_Node *			node_ptr;
	DjkT_Node *			connect_node_ptr;
	int					num_connects, connect_index;
	DjkT_Connection *	connect_ptr;
	int					num_hops, hop_index;
	DjkT_Node *			node_hop_ptr;
	DjkT_Connection *	back_connect_ptr;

	/** Procedure that implements the stub node phase of Dijkstra's algorithm. **/
	/** Stub nodes (nodes with one connection) were skipped in a previous      **/
	/** phase, but now their paths are calculated.  The basic idea is to       **/
	/** loop through all transit (non-stub) nodes, find connections to stub    **/
	/** nodes, and simply create a path list on the stub node that includes    **/
	/** the transit node path plus the transit node itself, and add the cost   **/
	/** to visit the stub node.                                                **/

	/** Note that an optimization to this algorithm would be to loop through   **/
	/** only the nodes that can be connected to stubs.  This is applicable     **/
	/** when the client of this algorithm is OSPF, since only nodes that       **/
	/** represent routers should be connected to stub networks.                **/
	FIN (djk_stub_nodes_add (node_list_ptr, root_node_ptr));

	num_nodes = op_prg_list_size (node_list_ptr);
	for (node_index = 0; node_index < num_nodes; node_index++)
		{
		/* Get current node. */
		node_ptr = (DjkT_Node *) op_prg_list_access (node_list_ptr, node_index);

		/* If this is a stub node, then continue on. */
		if (djk_node_stub_check (node_ptr))
			continue;

		/* We have a transit node, is it connected to any stub nodes? */
		num_connects = op_prg_list_size (node_ptr->connection_list_ptr);
		
		for (connect_index = 0; connect_index < num_connects; connect_index++)
			{
			/* Get current connection. */
			connect_ptr = (DjkT_Connection *) op_prg_list_access (node_ptr->connection_list_ptr,
				connect_index);
			
			/* Get the node on the other end of this connection. */
			connect_node_ptr = connect_ptr->node_ptr;

			/* Is this a stub node? */
			if (!djk_node_stub_check (connect_node_ptr))
				continue;

			/* Is it the root node? */
			if (connect_node_ptr == root_node_ptr)
				{
				/* We've already calculated this path, no need to recompute it. */
				continue;
				}

			/* This is a stub node, so we may add to the path list. */
			num_hops = op_prg_list_size (node_ptr->path_list_ptr);

			/* If there is no path to the transit node in the first place */
			/* there is no need to consider the stub node.                */
			if (num_hops == 0)
				continue;

			/* Finally, make sure the stub has a connection back to the transit network. */
			back_connect_ptr = djk_connect_lookup (connect_node_ptr->connection_list_ptr,
				node_ptr);
			if (back_connect_ptr == OPC_NIL)
				continue;

			for (hop_index = 0; hop_index < num_hops; hop_index++)
				{
				node_hop_ptr = (DjkT_Node *) op_prg_list_access (node_ptr->path_list_ptr, hop_index);
				op_prg_list_insert (connect_node_ptr->path_list_ptr, node_hop_ptr, OPC_LISTPOS_TAIL);
				}
			
			/* And add the new stub node to the end of the path list. */
			op_prg_list_insert (connect_node_ptr->path_list_ptr, connect_node_ptr, OPC_LISTPOS_TAIL);

			/* And update the cost to get to the node. */
			connect_node_ptr->root_distance = node_ptr->root_distance + connect_ptr->cost;
			}
		}

	FOUT;
	}

void
djk_path_list_calc (List *node_list_ptr, List *candidate_list_ptr, 
	List *shortest_path_list_ptr, DjkT_Node *current_node_ptr)
	{	
	int					num_connects, connect_index;
	DjkT_Connection *	connect_ptr;
	List *				connect_list_ptr;
	DjkT_Node *			connect_node_ptr;
	DjkT_Node *			cand_node_ptr;
	DjkT_Node *			best_cand_node_ptr;
	DjkT_Connection *	back_connect_ptr;
	int					root_distance;

	/** Auxillary procedure to calculate the path list.  The algorithm implemented **/
	/** is described in section 16.1 of RFC 1583.  This procedure is called        **/
	/** recursively, and calculates the path and distance for current_node_ptr.    **/
	FIN (djk_path_list_calc (node_list_ptr, candidate_list_ptr, shortest_path_list_ptr,	
		current_node_ptr));

	/* Take the current node and loop through all the links to transit nodes (nodes with */
	/* more than one connection).  Stub nodes will be handled in a later phase.          */	
	connect_list_ptr = current_node_ptr->connection_list_ptr;
	num_connects = op_prg_list_size (connect_list_ptr);
	for (connect_index = 0; connect_index < num_connects; connect_index++)
		{	
		/* Get current connection. */
		connect_ptr = (DjkT_Connection *) op_prg_list_access (connect_list_ptr, connect_index);

		/* Look for the node at the other end of this connection. */
		connect_node_ptr = connect_ptr->node_ptr;

		/* If we found a stub node, or none at all, continue on. */
		if ((connect_node_ptr == OPC_NIL) || (djk_node_stub_check (connect_node_ptr)))
			continue;

		/* We found a transit node.  First check to see if it's already on the path list. */
		if (djk_node_lookup (shortest_path_list_ptr, connect_node_ptr)
			!= OPC_NIL)
			continue;

		/* Make sure this node has a path back to the original node. */
		back_connect_ptr = djk_connect_lookup (connect_node_ptr->connection_list_ptr, 
			current_node_ptr);
		if (back_connect_ptr == OPC_NIL)
			continue;

		/* It's not yet in the shortest path list, and there's a bidirectional */
		/* connection.  Calculate the cost back to the root.                   */
		root_distance = current_node_ptr->root_distance + connect_ptr->cost;

		/* Now compare this root distance to the root distance computed */
		/* for this node.  If the node is in the candidate list, and    */
		/* the root distance already computed is greater than the root  */
		/* distance we've just computed, then replace the path list     */
		/* of the node in the candidate list.  If the node is not in    */
		/* the candidate list, then add it to the candidate list.       */
		
		/* First see if the node is in the candidate list. */
		cand_node_ptr = djk_node_lookup (candidate_list_ptr, connect_node_ptr);

		if (cand_node_ptr == OPC_NIL)
			{
			/* Node does not exist, so modify the total cost. */
			connect_node_ptr->root_distance = root_distance;

			/* Recalculate the path. */
			djk_node_next_hop_calc (connect_node_ptr, current_node_ptr);

			/* Add to candidate list. */
			op_prg_list_insert (candidate_list_ptr, connect_node_ptr, OPC_LISTPOS_TAIL);
			}
		else if (root_distance < cand_node_ptr->root_distance)
			{
			/* Node does exist, and we found a shorter path than originally */
			/* calculated, so simply modify its components.                 */
			cand_node_ptr->root_distance = root_distance;
			
			/* Recalculate the path. */
			djk_node_next_hop_calc (cand_node_ptr, current_node_ptr);
			}
		}

	/* After we've finished processing the connections from the current node, */
	/* check the candidate list for the next node to be added to the shortest */
	/* path list.  The node to be added will be the closest node to the root  */
	/* in the candidate list.  This node will also be removed from the        */
	/* candidate list, and the procedure will recurse with the best candidate */
	/* as current_node_ptr.                                                   */
	
	/* First search for the best candidate. */
	best_cand_node_ptr = djk_node_search (candidate_list_ptr, DJKC_NODE_SEARCH_LEAST_COST |
		DJKC_NODE_SEARCH_REMOVE);

	/* If none was found, then the algorithm is done.  Otherwise, perform the next */
	/* iteration of the algorithm, using the next best candidate.                  */
	if (best_cand_node_ptr != OPC_NIL)
		{
		/* This is the closest node to the root on the candidate list, so it */
		/* belongs on the path list.                                         */
		op_prg_list_insert (shortest_path_list_ptr, best_cand_node_ptr, OPC_LISTPOS_TAIL);
		djk_path_list_calc (node_list_ptr, candidate_list_ptr, shortest_path_list_ptr,
			best_cand_node_ptr);
		}
	
	FOUT;
	}

DjkT_Connection *
djk_connect_lookup (List *connect_list_ptr, DjkT_Node *node_ptr)
	{	
	DjkT_Connection *		connect_ptr;
	int						connect_index, connect_count;

	/** Look for a connection to the given node.  Return OPC_NIL if none exists. **/
	FIN (djk_connect_lookup (connect_list_ptr, node_ptr));

	/* Loop through all connections and see if one matches. */
	connect_count = op_prg_list_size (connect_list_ptr);
	for (connect_index = 0; connect_index < connect_count; connect_index++)
		{
		/* Get current connection. */
		connect_ptr = (DjkT_Connection *) op_prg_list_access (connect_list_ptr, connect_index);
		
		/* Check for a match. */
		if (connect_ptr->node_ptr == node_ptr)
			FRET (connect_ptr);
		}

	FRET (OPC_NIL);
	}

/***** Constructors *****/
DjkT_Node *
djk_node_create (void)
	{
	DjkT_Node *		node_ptr;

	/** Procedure for creating a node object. **/
	FIN (djk_node_create (void));

	/* Allocate node object. */
	node_ptr = (DjkT_Node *) op_prg_mem_alloc (sizeof (DjkT_Node));

	/* Initialize node object to sensible values. */
	node_ptr->node_id = DjkI_Node_Id++;
	node_ptr->connection_list_ptr = op_prg_list_create ();
	node_ptr->root_distance = 0;
	node_ptr->path_list_ptr = op_prg_list_create ();
	node_ptr->node_state_ptr = OPC_NIL;

	FRET (node_ptr);
	}

DjkT_Node *
djk_node_copy (DjkT_Node *node_ptr)
	{
	DjkT_Node *			copy_node_ptr;
	int					num_connects, connect_index;
	DjkT_Connection *	connect_ptr;
	DjkT_Connection *	copy_connect_ptr;
	int					num_hops, hop_index;
	DjkT_Node *			hop_ptr;

	/** Procedure to create and copy a node object. **/
	FIN (djk_node_copy (node_ptr));

	/* Create the copy first. */
	copy_node_ptr = djk_node_create ();
	
	/* Copy the fields. */
	copy_node_ptr->node_id = node_ptr->node_id;
	copy_node_ptr->root_distance = node_ptr->root_distance;
	
	/* The state is not actually copied, but the reference is copied. */
	copy_node_ptr->node_state_ptr = node_ptr->node_state_ptr;

	/* Copy the connection list. */
	num_connects = op_prg_list_size (node_ptr->connection_list_ptr);

	for (connect_index = 0; connect_index < num_connects; connect_index++)
		{
		/* Get current connection. */
		connect_ptr = (DjkT_Connection *) op_prg_list_access (node_ptr->connection_list_ptr,
			connect_index);

		/* Copy the connection. */
		copy_connect_ptr = djk_connection_copy (connect_ptr);

		/* Add to node copy. */
		op_prg_list_insert (copy_node_ptr->connection_list_ptr, copy_connect_ptr, OPC_LISTPOS_TAIL);
		}

	/* Copy the hop list. */
	num_hops = op_prg_list_size (node_ptr->path_list_ptr);

	for (hop_index = 0; hop_index < num_hops; hop_index++)
		{
		/* Get current hop. */
		hop_ptr = (DjkT_Node *) op_prg_list_access (node_ptr->path_list_ptr, hop_index);

		/* Add to copied hop list. */
		op_prg_list_insert (copy_node_ptr->path_list_ptr, hop_ptr, OPC_LISTPOS_TAIL);
		}

	FRET (copy_node_ptr);
	}

DjkT_Connection *
djk_connection_create (void)
	{
	DjkT_Connection *	connect_ptr;

	/** Procedure for creating a connection object. **/
	FIN (djk_connection_create (void));

	/* Allocate connection object. */
	connect_ptr = (DjkT_Connection *) op_prg_mem_alloc (sizeof (DjkT_Connection));
	
	/* Initialize connection object to sensible values. */
	connect_ptr->node_ptr = OPC_NIL;
	connect_ptr->cost = 0;
	connect_ptr->connect_state_ptr = OPC_NIL;

	FRET (connect_ptr);
	}

DjkT_Connection *
djk_connection_copy (DjkT_Connection *connect_ptr)
	{
	DjkT_Connection *	copy_connect_ptr;

	/** Procedure for creating and copying a connection object. **/
	FIN (djk_connection_copy (connect_ptr));

	/* Create new connection. */
	copy_connect_ptr = djk_connection_create ();

	/* Set the fields. */
	copy_connect_ptr->node_ptr = connect_ptr->node_ptr;
	copy_connect_ptr->cost = connect_ptr->cost;
	copy_connect_ptr->connect_state_ptr = OPC_NIL;

	FRET (copy_connect_ptr);
	}

/***** Destructors *****/
void
djk_node_destroy (DjkT_Node *node_ptr)
	{
	DjkT_Connection *	connect_ptr;

	/** Procedure to destroy a node object. **/
	FIN (djk_node_destroy (node_ptr));

	/* Destroy the lists associated with the node. */
	while (op_prg_list_size (node_ptr->connection_list_ptr) > 0)
		{	
		connect_ptr = op_prg_list_remove (node_ptr->connection_list_ptr, OPC_LISTPOS_HEAD);
		djk_connection_destroy (connect_ptr);
		}

	op_prg_mem_free (node_ptr->connection_list_ptr);
	op_prg_mem_free (node_ptr->path_list_ptr);

	/* Do nothing to the node state. */

	/* Deallocate node itself. */
	op_prg_mem_free (node_ptr);

	FOUT;
	}

void
djk_connection_destroy (DjkT_Connection *connect_ptr)
	{
	/** Procedure to destroy a connection object. **/
	FIN (djk_connection_destroy (connect_ptr));

	/* Just deallocate the structure itself. */
	op_prg_mem_free (connect_ptr);

	FOUT;
	}

/***** Print Procedures *****/
void
djk_node_list_print (List *node_list_ptr)
	{
	DjkT_Node *			node_ptr;
	int					node_count, node_index;

	/** Print out a list of nodes. **/
	FIN (djk_node_list_print (node_list_ptr));

	/* Loop through the nodes and call the print procedure for each one of them. */
	node_count = op_prg_list_size (node_list_ptr);
	for (node_index = 0; node_index < node_count; node_index++)
		{
		/* Get current node. */
		node_ptr = (DjkT_Node *) op_prg_list_access (node_list_ptr, node_index);

		djk_node_print (node_ptr);
		}
	
	FOUT;
	}

void
djk_node_print (DjkT_Node *node_ptr)
	{
	/** Print out information about a single node. **/
	FIN (djk_node_print (node_ptr));

	printf ("Node Ptr: %x\t Node ID: %d\t Distance to root: %d\t Num Connects: %d\t Path list: ", 
		node_ptr, node_ptr->node_id, node_ptr->root_distance, 
		op_prg_list_size (node_ptr->connection_list_ptr));

	/* Print out path list. */
	djk_node_hop_list_print (node_ptr->path_list_ptr);

	FOUT;
	}

void
djk_node_hop_list_print (List *hop_list_ptr)
	{
	DjkT_Node *	hop_ptr;
	int			hop_index, hop_count;

	/** Prints a list of hops. **/
	FIN (djk_node_hop_list_print (hop_list_ptr));

	printf ("(");
	hop_count = op_prg_list_size (hop_list_ptr);
	for (hop_index = 0; hop_index < hop_count; hop_index++)
		{
		/* Get current hop. */
		hop_ptr = (DjkT_Node *) op_prg_list_access (hop_list_ptr, hop_index);

		/* Print current hop. */
		if (hop_index == (hop_count - 1))
			printf ("%x", hop_ptr);
		else
			printf ("%x ", hop_ptr);
		}
	printf (")\n");

	FOUT;
	}

void
djk_node_path_list_print (List *node_list_ptr)
	{
	DjkT_Node *			node_ptr;
	int					node_count, node_index;
	DjkT_Node *			first_hop_ptr;
	DjkT_Node *			last_hop_ptr;

	/** Prints out just the available paths from a router, derived from **/
	/** the router's shortest path list.                                **/
	FIN (djk_node_path_list_print (node_list_ptr));

	printf ("\n\nNode Path Listing:\n");
	printf ("-------------------\n");

	/* Loop through all the nodes, and print the paths. */
	node_count = op_prg_list_size (node_list_ptr);
	for (node_index = 0; node_index < node_count; node_index++)
		{
		/* Get current node. */
		node_ptr = (DjkT_Node *) op_prg_list_access (node_list_ptr, node_index);

		/* Get the first hop. */
		first_hop_ptr = (DjkT_Node *) op_prg_list_access (node_ptr->path_list_ptr, OPC_LISTPOS_HEAD);

		/* Get the last hop. */
		last_hop_ptr = (DjkT_Node *) op_prg_list_access (node_ptr->path_list_ptr, OPC_LISTPOS_TAIL);

		/* Print out path information. */
		printf ("Path: %x --> %x\tCost: %d\t", first_hop_ptr, last_hop_ptr, node_ptr->root_distance);
		djk_node_hop_list_print (node_ptr->path_list_ptr);
		}

	FOUT;
	}