//============================================================================
// Name        : graph.cpp
// Author      : Radosław Kędzior
// Description : Program prezentujący tworzenie prostych grafów oraz różnice
//					pomiędzy grafami skierowanymi, nieskierowanymi i dwukierunkowymi.
//============================================================================


#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <iostream>
using namespace boost;

/*
 * Tworzenie grafu znajduje się w funkcji main() - na końcu pliku.
 */


//Szablon klasy wypisującej graf na konsolę.
template <class Graph> struct exercise_vertex {
  exercise_vertex(Graph& g_) : g(g_) { }
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  void operator()(const Vertex& v) const
  {
    using namespace boost;
    typename property_map<Graph, vertex_index_t>::type 
      vertex_id = get(vertex_index, g);
    std::cout << "vertex: " << get(vertex_id, v);

    /*
     * Wypisanie krawędzi wychodzących z wierzchołka.
     */
    std::cout << "\tout-edges: ";
    typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
    typename graph_traits<Graph>::edge_descriptor e;
    for (tie(out_i, out_end) = out_edges(v, g);  
         out_i != out_end; ++out_i)
    {
      e = *out_i;
      Vertex src = source(e, g), targ = target(e, g);
      std::cout << "(" << get(vertex_id, src)
                << "," << get(vertex_id, targ) << ") ";
    }

    /*
     * Wypisanie krawędzi przychodzących do wierzchołka.
     */
    std::cout << "\tin-edges: ";
    typename graph_traits<Graph>::in_edge_iterator in_i, in_end;
    for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
    {
      e = *in_i;
      Vertex src = source(e, g), targ = target(e, g);
      std::cout << "(" << get(vertex_id, src)
                << "," << get(vertex_id, targ) << ") ";
    }

    /*
     * Wypisanie sąsiadów wierzchołka - innych wierzchołków do których mamy
     * bezpośredni dostęp z tego wierzchołka (do których wskazują krawędzie
     * wychodzące).
     */
    std::cout << "\tadjacent vertices: ";
    typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
    for (tie(ai,ai_end) = adjacent_vertices(v, g);  ai != ai_end; ++ai)
      std::cout << get(vertex_id, *ai) <<  " ";
    std::cout << std::endl;
  }
  
  Graph& g;
};

/*
 * Szablon podobny po poprzedniego tylko dla grafów skierowanych.
 * Grafy te nie mają wiedzy o krawędziach przychodzących
 * nie ma metody in_edges() dla takich grafów.
 */
template <class Graph> struct exercise_vertex_d {
  exercise_vertex_d(Graph& g_) : g(g_) { }
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  void operator()(const Vertex& v) const
  {
    using namespace boost;
    typename property_map<Graph, vertex_index_t>::type 
      vertex_id = get(vertex_index, g);
    std::cout << "vertex: " << get(vertex_id, v);

    // Write out the outgoing edges
    std::cout << "\tout-edges: ";
    typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
    typename graph_traits<Graph>::edge_descriptor e;
    for (tie(out_i, out_end) = out_edges(v, g);  
         out_i != out_end; ++out_i)
    {
      e = *out_i;
      Vertex src = source(e, g), targ = target(e, g);
      std::cout << "(" << get(vertex_id, src)
                << "," << get(vertex_id, targ) << ") ";
    }

    // Write out all adjacent vertices    
    std::cout << "\tadjacent vertices: ";
    typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
    for (tie(ai,ai_end) = adjacent_vertices(v, g);  ai != ai_end; ++ai)
      std::cout << get(vertex_id, *ai) <<  " ";
    std::cout << std::endl;
  }
  
  Graph& g;
};

int main() 
{
	/*
	 * Tworzenie typu grafu. Pierwsze dwa argumenty szablonu to listy (określamy typ)
	 * w jakich przechowywane będą odpowiednio krawędzie i wierzchołki. Mamy do wyboru:
	 * vecS		- std::vector.
	 * listS	- std::list.
	 * slistS	- std::slist.
	 * setS		- std::set.
	 * multisetS- std::multiset.
	 * hash_setS- std::hash_set.
	 * Trzeci parametr to typ grafu, tutaj kolejno: dwukierunkowe, skierowane i nieskierowane.
	 * Istnieje inna wersja szablonu adjacency_list która pozwala definiować odpowiednie właściwości
	 * dla grafu, wierzchołku i krawędzi.
	 */
	typedef adjacency_list<vecS, vecS, bidirectionalS> Graph_bi;
	typedef adjacency_list<vecS, vecS, directedS> Graph_d;
	typedef adjacency_list<vecS, vecS, undirectedS> Graph_und;
	
	typedef std::pair<int, int> Edge;
	
	enum { A, B, C, D, E, N };
	const int num_vertices = N;

	// Definiujemy krawędzie pomiędzy wierzchołkami w postaci tablicy.
	Edge edge_array[] = {
							Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
							Edge(C,E), Edge(B,D), Edge(D,E)
						};
	
	const int num_edges = sizeof( edge_array )/sizeof( edge_array[0] );
	
	// Definicje grafów:
	Graph_bi g_bi( num_vertices );
	Graph_d g_d( num_vertices );
	Graph_und g_und( num_vertices );

	/*
	 * Dodajemy kolejno krawędzie do grafu, przy okazji definiujemy wierzchołki.
	 * Krawędzie w tym przypadku są reprezentowane przez pary liczb całkowitych,
	 * wierzchołki zaś przez liczby.
	 */
	for ( int i = 0; i < num_edges; ++i )
	{
		add_edge( edge_array[i].first, edge_array[i].second, g_bi );
		
		add_edge( edge_array[i].first, edge_array[i].second, g_d );
		
		add_edge( edge_array[i].first, edge_array[i].second, g_und );
	}
	

	
	/*
	 * W tym momencie mamy zdefiniowane grafy. Różnice jakie występują pomiędzy grafami to:
	 * Bidirectional: osobno wyróżniamy krawędzie wychodzące i przychodzące
	 * 				 (dwa zbiory krawędzi dla każdego wierzchołka = więcej potrzebnych zasobów)
	 * Directed: przechowujemy tylko informacje o krawędziach wychodzących z wierzchołków
	 * 				(nie znamy wprost krawędzi przychodzących)
	 * Undireced: grafy nieskierowane, krawędzie są dwukierunkowe (w pamięci przy wierzchołku
	 * 				jest jeden zbiór krawędzi)
	 * 
	 * Poniższy kod wypisuje zawartość grafów na konsolę:
	 */
	std::cout << "BIDIRECTIONAL" << std::endl;
	std::for_each(vertices(g_bi).first, vertices(g_bi).second, exercise_vertex<Graph_bi>(g_bi));
	
	std::cout << "DIRECTED" << std::endl;
	std::for_each(vertices(g_d).first, vertices(g_d).second, exercise_vertex_d<Graph_d>(g_d) );
	
	std::cout << "UNDIRECTED" << std::endl;
	std::for_each(vertices(g_und).first, vertices(g_und).second, exercise_vertex<Graph_und>(g_und));
	return 0;
}