/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Autor: Jan Olszak
Temat: biblioteki boost - boost::graph (BGL) - przeszukiwanie grafów algorytmem Dijkstry
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Algorytm Dijkstry przeszukiwania grafu (na podstawie Wikipedii):
0.	s - wierzchołek, od którego startujemy, v - dowolny inny wierzchołek

1.	Stwórz tablicę d odległosci od zródła dla wszystkich wierzchołków grafu. 
Na początku d[s] = 0, zas d[v] = nieskończonosc dla wszystkich pozostałych wierzchołków.

2.	Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. 
Priorytetem kolejki jest aktualnie wyliczona odległosc od wierzchołka zródłowego s.

3.	Dopóki kolejka nie jest pusta:
3.1	Usuń z kolejki wierzchołek u o najniższym priorytecie 
(wierzchołek najbliższy zródła, który nie został jeszcze rozważony)
3.2	Dla każdego sąsiada v wierzchołka u dokonaj relaksacji poprzez u: jeśli d[u] + w(u,v) < d[v] 
(poprzez u da się dojsc do v szybciej niż dotychczasową ścieżką), to d[v]: = d[u] + w(u,v).


4.	Na końcu tablica d zawiera najkrótsze odległości do wszystkich wierzchołków.

Biblioteka BGL umożliwia stworzenie wizytatora, 
którego  metody są wywoływane kiedy odpowiednie kroki w algorytmie są wykonywane. 

DijkstraVisitor definiuje nasępujący interfejs (na podstawie dokumentacjii boost http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/DijkstraVisitor.html):
u - wierzchołek, e - krawędz, g - graf

1. Initialize Vertex	vis.initialize_vertex(u, g)	void	Wywoływane raz dla każdego wierzchołka grafu, podczas jego inicjalizacji. (krok 1 algorytmu)

2. Examine Vertex		vis.examine_vertex(u, g) void	  	Wywoływane dla wierzchołka usuwanego z kolejki (krok 3.1 algorytmu). 
Zaraz potem metoda examine_edge(e,g) jest wywoływana dla wszystkich krawędzi wychodzących z wierzchołka u

3. Examine Edge			vis.examine_edge(e, g)	void		Wywoływane dla krawędzi, kiedy jest odkrywana (krok 3.2 algorytmu)

4. Discover Vertex		vis.discover_vertex(u, g) void		Wywoływane dla wierzchołka, gdy jest odkrywany. Czyli gdy odległosc od wierzchołka-zródła staje się skończona. (krok 3.2 algorytmu)

5. Edge Relaxed			vis.edge_relaxed(e, g) void		Wywoływane dla krawędzi, kiedy dokonuje się przez nią relaksacji (krok 3.2 algorytmu)

6. Edge Not Relaxed		vis.edge_not_relaxed(e, g)	void	Wywoływane dla krawędzi, kiedy nie dokonuje się przez nią relaksacji (krok 3.2 algorytmu)

7. Finish Vertex		vis.finish_vertex(u, g)	void		Wywoływane dla wierzchołka po tym jak wszystkie wychodzące z niego krawędzie będą dodane do drzewa przeszukiwań, 
oraz wszystkie przyległe do niego wierzchołki będą odkryte (ale zanim wychodzące z nich krawędzie będą odkryte)



Przy deklarowaniu własnego wizytatora nie trzeba po niczym dziedziczyć. Wystarczy zrobić klasę, która ma wszystkie wyżej wymienione metody.
Jest ich jednak dużo i najczesciej nie będzie potrzeby używać wszystkich. Żeby ułatwić tworzenie wizytatora w którym wywoływane są tylko niektóre metody twórcy BGL stworzyli modele 
- w tym wypadku dijkstra_visitor zdefiniowany w boost/graph/dijkstra_shortest_paths.hpp oraz pomocniczą metodę make_dijkstra_visitor
implementującego DijkstraVisitor w pliku


Można tworzyć wizytatora na 2 sposoby
implementowac
make dijkstra visitator




----------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

#include <boost/config.hpp>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
// Use boost::queue instead of std::queue because std::queue doesn't
// model Buffer; it has to top() function. -Jeremy
#include <boost/pending/queue.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>


using namespace boost;


typedef adjacency_list < vecS, vecS, directedS,no_property, property < edge_weight_t, int > >  DirectedGraph;
typedef graph_traits<DirectedGraph>::edge_descriptor EdgeDescriptor;
typedef graph_traits<DirectedGraph>::vertex_descriptor VertexDescriptor;
typedef std::pair<int, int> Edge;


// Wierzchołki będą typu int, N - liczba wierzchołków
enum { A, B, C, N };

// Pomocna tablica do wypisywania na ekran
char name[] = "ABCDE";

class MyVisitor {
public:
	MyVisitor() { }
	void initialize_vertex(VertexDescriptor u,DirectedGraph g)
	{
		std::cout << "initialize_vertex " << u << std::endl;
	}
	void discover_vertex(VertexDescriptor u,DirectedGraph g){
		std::cout << "discover_vertex "<< u << std::endl;

	}
	void examine_vertex(VertexDescriptor u,DirectedGraph g){
		std::cout << "examine_vertex "<< u << std::endl;

	}
	void examine_edge(EdgeDescriptor e,DirectedGraph g){
		std::cout << "examine_edge "<< e << std::endl;

	}
	void edge_relaxed(EdgeDescriptor e,DirectedGraph g){
		std::cout << "edge_relaxed "<< e <<std::endl;

	}
	void edge_not_relaxed(EdgeDescriptor e,DirectedGraph g){
		std::cout << "edge_not_relaxed "<< e <<std::endl;

	}
	void finish_vertex(VertexDescriptor u,DirectedGraph g){
		std::cout << "finish_vertex "<< u << std::endl;

	}



};

void print(std::string title,DirectedGraph g, std::vector<VertexDescriptor>  &p, std::vector<int> &d ){
	// Pomocnicza funkcja wypisująca.


	std::cout << title << std::endl;
	graph_traits < DirectedGraph >::vertex_iterator vi, vend;
	for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
		std::cout << "najmniejsza odleglosc(" << name[*vi] << ") = " << d[*vi] << ", ";
		std::cout << "rodzic(" << name[*vi] << ") = " << name[p[*vi]] << std::
			endl;
	}
	std::cout << std::endl;
}




void firstExample(){
	/*
	Przykład, w którym używamy własnej klasy-wizytatora, 
	w której trzeba definiować wszystkie metody interfejsu DijkstraVisitor
	*/

	// Tablica krawędzi
	Edge edge_array[] = {Edge(A,B), Edge(A,C), Edge(B,C)};

	// Tablica wag dla krawędzi
	int weights[] = { 1, 9, 3};

	// Liczba krawędzi
	int num_arcs = sizeof(edge_array) / sizeof(Edge);

	// Tworzymy graf g
	DirectedGraph g(edge_array, edge_array + num_arcs, weights, N);

	// Kontenery, do których dijkstra_shortest_paths() wypisze wynik
	std::vector<VertexDescriptor> p(num_vertices(g));
	std::vector<int> d(num_vertices(g));
	VertexDescriptor s = vertex(A, g);

	// Nasz wizytator, wszystkie metody muszą być zadeklarowane
	MyVisitor myVisitor;

	// Wywołanie algorymu Dijkstry. Argumenty podane przy pomocy bgl_named_params. http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/bgl_named_params.html
	dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]).visitor(myVisitor)    );

	print("Pierwszy przyklad: ",g,p,d);

}




template <class NewGraph, class Tag>
struct MyPartVisitor  
	: public base_visitor<MyPartVisitor<NewGraph, Tag> >
{
	typedef Tag event_filter;

	MyPartVisitor(NewGraph& graph) : new_g(graph) { }

	template <class Edge, class Graph>
	void operator()(Edge e, Graph& g) {
		add_edge(source(e, g), target(e, g), new_g);
		std::cout << "kopiuje krawedz"<< e << std::endl;
	}
private:
	NewGraph& new_g;

};


template <class NewGraph, class Tag>
inline MyPartVisitor<NewGraph, Tag>
makeMyPartVisitor(NewGraph& g, Tag) {
	return MyPartVisitor<NewGraph, Tag>(g); // funkcje moga dedukowac typy argumentow, ktore sie do nich przekazuje
}

void secondExample(){
	/*
	Przykład, w którym używamy własnego wizytatora, ktory implementuje tylko jedna metode interfejsu.
	W tym wypadku, chcemy przekopiowac graf g do grafu g_copy
	*/

	// Tablica krawędzi
	Edge edge_array[] = {Edge(A,B), Edge(A,C), Edge(B,C)};

	// Tablica wag dla krawędzi
	int weights[] = { 1, 9, 3};

	// Liczba krawędzi
	int num_arcs = sizeof(edge_array) / sizeof(Edge);

	// Tworzymy graf g
	DirectedGraph g(edge_array, edge_array + num_arcs, weights, N);

	// Tworzymy graf, do którego przekopiujemy graf g
	DirectedGraph g_copy(edge_array, edge_array + num_arcs, weights, N);

	// Kontenery, do których dijkstra_shortest_paths() wypisze wynik
	std::vector<VertexDescriptor> p(num_vertices(g));
	std::vector<int> d(num_vertices(g));

	// Wierzchołek początkowy algorytmu - source
	VertexDescriptor s = vertex(A, g);


	// Wywołanie algorymu Dijkstry. Argumenty podane przy pomocy bgl_named_params. http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/bgl_named_params.html

	dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]).visitor(make_dijkstra_visitor(makeMyPartVisitor(g_copy, on_examine_edge())))    );

	print("Drugi przyklad, skopiowany graf:",g_copy,p,d);

}


int main(int, char *[])
{
	firstExample();
	secondExample();

	std::system("pause");

	return EXIT_SUCCESS;

}