prg_djk Code Sample

#include <stdlib.h>

#include <opnet.h>
#include <prg.h>
#include <prg_vector.h>
#include <prg_graph.h>
#include <prg_djk.h>

#define EXAMPLE_NAMESPACE "example_namespace"
#define EXAMPLE_STATE "example_state"


void
prg_djk_example_code ()
	{
	int i, vsize;
	PrgT_Graph_State_ID state_id;
	PrgT_Graph *graph_ptr;
	PrgT_Graph_Vertex *vtx_a_ptr, *vtx_b_ptr;
	PrgT_Graph_Vertex *vtx_c_ptr, *vtx_d_ptr;
	PrgT_Graph_Edge *edge_ab_ptr, *edge_bd_ptr;
	PrgT_Graph_Edge *edge_ac_ptr, *edge_cd_ptr;
	PrgT_Graph_Edge *edge_ptr;
	PrgT_Vector *path_set_vptr, *path_vptr;
	PrgT_Compcode status;

	FIN (prg_djk_example_code (void));

	/* Register handlers for our namespace. */
	state_id = prg_graph_state_handler_register (EXAMPLE_NAMESPACE,
	EXAMPLE_STATE, PRGC_NIL, PRGC_NIL);

	if (state_id == PRGC_GRAPH_INVALID_ID)
		FOUT;

	graph_ptr = prg_graph_create (EXAMPLE_NAMESPACE);

	/* Build up the following graph. */
	/*       */
	/*   B   */
	/*  / \  */
	/* A   D */
	/*  \ /  */
	/*   C   */
	/*       */

	/* Insert Vertices. */
	vtx_a_ptr = prg_graph_vertex_insert (graph_ptr);
	vtx_b_ptr = prg_graph_vertex_insert (graph_ptr);
	vtx_c_ptr = prg_graph_vertex_insert (graph_ptr);
	vtx_d_ptr = prg_graph_vertex_insert (graph_ptr);

	/* Insert edges. */
	edge_ab_ptr = prg_graph_edge_insert (graph_ptr, vtx_a_ptr,
		vtx_b_ptr, PrgC_Graph_Edge_Duplex);

	edge_ac_ptr = prg_graph_edge_insert (graph_ptr, vtx_a_ptr,
		vtx_c_ptr, PrgC_Graph_Edge_Duplex);

	edge_bd_ptr = prg_graph_edge_insert (graph_ptr, vtx_b_ptr,
		vtx_d_ptr, PrgC_Graph_Edge_Duplex);

	edge_cd_ptr = prg_graph_edge_insert (graph_ptr, vtx_c_ptr,
		vtx_d_ptr, PrgC_Graph_Edge_Duplex);

	/* Initialize the DJK state on our graph */
	status = prg_djk_graph_init (graph_ptr);
	if (status == PrgC_Compcode_Failure)
		{ prg_graph_destroy (graph_ptr, PRGC_TRUE); FOUT; }

	/* The DJK graph structure is now initialized. Configure parameters.    */

	/* Set the edge weights:                                                */
	/* A-B => 1; A-C => 2; B-D => 2; C-D => 1                               */
	/* This graph has two shortest-paths from vertex A to vertex D          */
	prg_djk_edge_weight_set (edge_ab_ptr, 1);
	prg_djk_edge_weight_set (edge_ac_ptr, 2);
	prg_djk_edge_weight_set (edge_bd_ptr, 2);
	prg_djk_edge_weight_set (edge_cd_ptr, 1);

	/* Now the graph is ready for path calculations.                        */

/***** Example 1: Compute a single path.                           *****/
	printf ("\nExample 1:\n");

	/* First, compute a path between vertex A and vertex B                  */
	/* Since we have not run prg_djk_all_source_compute(), the path         */
	/* will be computed without consulting routing tables.                  */
	path_set_vptr = prg_djk_path_get (vtx_a_ptr, vtx_b_ptr);
	printf ("Path set contains %d path(s).\n", prg_vector_size (path_set_vptr));

	/* path_set_vptr is a vector (set) of vectors (paths) of edges.         */
	/* There is one path from A to B, so path_set_vptr contains one vector. */
	path_vptr = (PrgT_Vector *) prg_vector_access (path_set_vptr, 0);

	/* path_vptr contains a single edge: edge_ab_ptr */
	printf ("Path vector contains %d edge(s).\n", prg_vector_size (path_vptr));
	edge_ptr = (PrgT_Graph_Edge *) prg_vector_access (path_vptr, 0);
	printf ("Path's edge is%s edge_ab_ptr\n",
		(edge_ptr == edge_ab_ptr) ? "" : " not");

	/* We are done with the path and the path set, deallocate them: */
	/* The contained edge is owned by the graph, so do not destroy elements. */
	prg_vector_destroy (path_vptr, PRGC_FALSE);

	/* The paths have just been freed; do not re-free the path_set elements. */
	prg_vector_destroy (path_set_vptr, PRGC_FALSE);

/***** Example 2: Compute all-pairs shortest paths.                  *****/
	printf ("\nExample 2:\n");

	/* Note that we do not re-initialized the DJK state or the edge weights  */
	/* to run another path calculations.                                     */
	status = prg_djk_all_sources_compute (graph_ptr);
	if (status == PrgC_Compcode_Failure)
		{ prg_graph_destroy (graph_ptr, PRGC_TRUE); FOUT;}


	/* With routing tables established, every call to prg_djk_path_get will  */
	/* use the routing tables to get the paths and will not recompute paths  */

	/* Get the total cost of the path between A and D                        */
	/* Note that no path vector is needed.                                   */
	printf("The total cost of the shortest path between A and D is: %f\n",
		prg_djk_path_cost_get (vtx_a_ptr, vtx_d_ptr));

	/* Retrieve the path set from A to D, there are 2. */
	path_set_vptr = prg_djk_path_get (vtx_a_ptr, vtx_d_ptr);

	/* Confirm that there are 2 paths */
	printf ("Path set contains %d path(s).\n", prg_vector_size (path_set_vptr));
	if (prg_vector_size (path_set_vptr) != 2)
		{
		prg_vector_destroy (path_set_vptr, PRGC_TRUE);
		prg_graph_destroy (graph_ptr, PRGC_TRUE);
		FOUT;
		}

	/* Retrieve the second path */
	printf ("Displaying  path:\n", prg_vector_size (path_set_vptr));
	path_vptr = prg_vector_access (path_set_vptr, 1);
	vsize = prg_vector_size (path_vptr);
	for (i=0; i< vsize; i++)
		{
		PrgT_Graph_Edge *edge_ptr =
			(PrgT_Graph_Edge *) prg_vector_access (path_vptr, i);

		/* For each edge in the path, perform some operation */
		printf ("\tEdge address: (%lx)\n", (long) edge_ptr);
		}

	/* Deallocate paths and path set */

	vsize = prg_vector_size (path_set_vptr);
	for (i=0; i< vsize; i++)
		{
		PrgT_Vector *vptr = (PrgT_Vector *) prg_vector_access (path_set_vptr, i);
			prg_vector_destroy (vptr, PRGC_FALSE);
		}
	prg_vector_destroy (path_set_vptr, PRGC_FALSE);

	/* Clean up.*/
	prg_graph_destroy (graph_ptr, PRGC_TRUE);
	FOUT;
	}