/*
	Graph library Demo.
	David D.	2006
*/

#include "Graph.h"


using namespace std;
using namespace Mido::Utility;

const int N = 7;
const double dag[N][N] = { 	{-1, 0,-1,-1,-1,-1,-1},
							{-1,-1, 0,-1, 5,-1,-1},
							{-1,-1,-1, 0,-1, 1,-1},
							{-1,-1,-1,-1,-1,-1, 0},
							{-1,-1, 4,-1,-1, 3,-1},
							{-1,-1,-1, 0,-1,-1,-1},
							{-1,-1,-1,-1,-1,-1,-1}	};

int main(int argc, char** argv)
{	
	
	double** array = new double*[N];
	for(int i=0;i<N;i++)
		array[i] = new double[N];
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			array[i][j] = dag[i][j];
	
	Graph graph((const double**)array,N);

	// Find the shortest path
	Graph::path_t path;
	unsigned size = 0;
	double min = graph.Dijkstra(path);
	cout << "min dist = " << min << endl;
	while(path.size())
	{
		cout << path.top() +1 << " ";
		path.pop();
	}
	cout << endl;	

	// Find the k shortest paths
	Graph::path_list paths;
	int k = graph.MSAforKSP(10,paths);
	cout << "k = " << k << endl;	
	for(unsigned i=0;i<paths.size();i++)	// output the k shortest paths.
	{
		while(paths[i].size())
		{
			cout << paths[i].top() + 1 << " ";
			paths[i].pop();
		}
		cout << endl;
	}

	for(int i=0;i<N;i++)
		delete[] array[i];
	delete[] array;

	return 0;
}