/* Krzysztof Krygiel, grupa 4I1
 * 
 * Przykład wykorzystania biblioteki boost::graph
 *
 * Poniższy program demonstruje możliwości użycia wyżej wymienionej biblioteki
 * w celu wyznaczenia najkrótszych ścieżek w ważonym grafie przy pomocy
 * algorytmu Dijkstry ( O(V log V) ). Należy pamiętać, że za pomocą tego 
 * algorytmu możliwe jest wyznaczenie szukanych odległości tylko dla grafu 
 * o nieujemnych wagach krawędzi. Dla grafu o ujemnych wagach (który nie zawiera 
 * cyklu o ujemnej długości) należy wykorzystać algorytm Bellmana-Forda. 
 * Dla grafu o jednakowych  wartościach wag można użyć przeszukiwania w szerz 
 * w celu optymalizacji programu ( O(V+E) ).
 * 
 * Pod koniec programu pokazano jak w łatwy sposób znaleźć minimalne drzewo 
 * rozpinające.w nieskierowanym grafie. Zaimplementowany w bibliotece algorytm
 * Prima ma złożoność O(E log V) gdzie E to liczba krawędzi, a V to liczba
 * wierzchołków.
 * Zaimplementowany został także algorytm Kruskala o złożoności O(E log E).
 * Ze względu na mniejszą wydajność jego użycie nie zostanie tutaj przedstawione.
 */

#include <iostream>

#include <boost/lexical_cast.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

using namespace boost;
using namespace std;

/*
 * Klasa wizytatora dla algorytmu Dijkstry. Po przetworzeniu danego wierzchołka 
 * wypisywany jest odpowiedni komunikat.
 * Istnieje jeszcze 6 innych metod, które można wykorzystać w tym wizytatorze.
 */
class Wizytator:public default_dijkstra_visitor {
	public:
		template<class Etykieta, class Graf> 
		void examine_vertex(Etykieta& w, Graf& g){		//parametrami jest etykieta wierzcholka i graf na którym wykonujemy algorytm
			cout<<"Wyznaczono odległość do wierzchołka "<<static_cast<char>(w+'A')<<endl;
		}
};


int main(int, char *[])
{
	//Definicja typu danych do przechowywania grafu (graf będzie reprezentowany przez listy sąsiedztwa)
	typedef adjacency_list<
		listS,			//krawędzie przechowywane w std::list
		vecS,				//wierzchołki przechowywane w std::vector
		undirectedS,		//graf nieskierowany (istnieje możlwość stworzenia grafu skierowanego : directedS)
		no_property,	//Właściwości wierzchołków (brak atrybutów)
		property<edge_weight_t, int> //Właściwości krawędzi (każdej krawędzi przyporządkowujemy wagę)
	> graf;
	
	typedef graph_traits < graf >::vertex_descriptor vertex_descriptor;
	typedef graph_traits < graf >::edge_descriptor edge_descriptor;
	
	//Krawedzie reprezentowane są przez pare liczb oznaczajacych wierzchołek początkowy i końcowy
	typedef pair<int,int> Krawedz;
	//nazwy symboliczne dla wierzchołków, liczba_wierz - liczba wierzchołków w grafie
	enum wierzcholki {A,B,C,D,E,F,G, liczba_wierz};
		
	//inicjalizacja krawędzi grafu
	Krawedz krawedzie[] = { Krawedz(A, B), Krawedz(A, C), Krawedz(B, C), Krawedz(B, D), Krawedz(D, A),
		Krawedz(D, E), Krawedz(D, G), Krawedz(E, B), Krawedz(E, F), Krawedz(F, G) };
		
	//wagi poszczególnych krawędzi (kolejność odpowiada kolejności w krawedzie[])
	int wagi[] = { 3, 2, 4, 2, 10, 1, 3, 1, 5, 15  };
	int liczba_kraw = sizeof(krawedzie) / sizeof(Krawedz);

	//tworzenie grafu
	graf g(
		krawedzie,			//iterator na pierwszy element konteneru zawierającego krawędzie
		krawedzie+liczba_kraw,		//iterator na element za ostatnim w kontenerze zawierającym krawędzie
		wagi,			//wagie krawędzi
		liczba_wierz		//liczba wierzchołków
	);

	//przygotowanie kontenerów (dla odległości do danego wierzchołka i poprzednika na najkrótszej scieżce)
	vector<vertex_descriptor> poprzednik(liczba_wierz);
	vector<int> odleglosc(liczba_wierz);

	//wywołanie algorytmu wyszukiwania najkrótszej ścieżki
	dijkstra_shortest_paths(
		g,			//przeszukiwany graf
		vertex(D, g),	//wierzchołek startowy
		//informacja o miejscu zapisu wyników
		predecessor_map(make_iterator_property_map(poprzednik.begin(), get(vertex_index, g))).
			distance_map(make_iterator_property_map(odleglosc.begin(), get(vertex_index, g)))
	);

	//wypisanie wyników
	for (int i=0;i<liczba_wierz;i++){
		//jeżeli poprzednikiem wierzchołka jest on sam (i nie jest to wierzchołek startowy) to
		//dany wierzchołek nie jest osiągalny z wierzchołka startowego
		if (i!=D && poprzednik[i]==i) cout<<"Brak scieżki do wierzchołka "<< static_cast<char>(i+'A')<<endl;
		else{
			//proste odtworzenie pełnej ścieżki poprzez przesuwanie się od końca po poprzednikach
			string sciezka=lexical_cast<string>(static_cast<char>(i+'A'));
			int wierz=i;
			while (poprzednik[wierz]!=wierz) {
				wierz=poprzednik[wierz];
				sciezka=lexical_cast<string>(static_cast<char>(wierz+'A'))+sciezka;
			}
			
			cout<<"Odległość do wierzchołka "<<(char)(i+'A')<<" wynosi "<<odleglosc[i]<<" (dla scieżki: "<<sciezka<<")"<<endl;
		}
	}
	
	/*
	 * Oprocz prostej funkcji implementującej algorytm Dijkstry, która pozwala na zdobycie informacji o 
	 * najkrótszej ścieżce istnieje także wzorzec umożliwiający dołączenie własnego wizytatora. Daje on
	 * możliwość reagowania na poszczególne elementy algorytmu Dijkstry (np. inicjacja czy pobranie
	 * wierzchołka z kolejki priorytetowej).
	 */
	
	//wywołanie algorytmu z przekazaniem własnego wizytatora
	property_map<graf, edge_weight_t>::type weightmap = get(edge_weight, g);
	property_map<graf, vertex_index_t>::type indexmap = get(vertex_index, g);
	
	dijkstra_shortest_paths(
		g,
		vertex(D, g),
		&poprzednik[0],
		&odleglosc[0],
		weightmap,		//wagi krawedzi pobrane z grafu
		indexmap, 		//indeksy (etykiety) krawedzi pobrane z grafu
		std::less<int>(),		//operator porównania (dla porównywania odległości)
		closed_plus<int>(),		//operator dodawania (sumowanie odległosci)
		(std::numeric_limits<int>::max)(),		//wartość, która zostaną zaincicjowane odległości (dla poprawności musi być większa od najdluższej ścieżki)
		0,		//odległośc do początkowego wierzchołka
		Wizytator()		//wlasny wizytotor (mozna przekazac domyslny -default_dijkstra_visitor()
	);
	
	
	
	//Znajdowanie minimalnego drzewa rozpinającego dla wcześniej skonstruowanego grafu
	prim_minimum_spanning_tree(g, &poprzednik[0]);
	
	cout<<"Do minimalnego drzewa rozpinającego należą krawędzie:"<<endl;
	for (int i=0;i<liczba_wierz;i++){
		//krawedź należy do drzewa rozpinającego jeżeli poprzednik[i]!=i
		if (poprzednik[i]!=i) cout<<"("<<static_cast<char>(i+'A')<<" "<<static_cast<char>(poprzednik[i]+'A')<<")"<<endl;
	}
}