#include <stdio.h>
#include <iostream>

#include <boost/shared_ptr.hpp>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

// adjacency_list-based type
typedef adjacency_list < vecS, vecS, undirectedS > SimpleGraph;

void initializeGraph(int numOfSides, shared_ptr<SimpleGraph> graph)
{
    // "Ridges" connecting the vertices of the upper polygon
    // with the corresponding vertices of the lower polygon
    for(int ii = 0; ii < numOfSides; ++ii)
        add_edge(ii, ii + numOfSides, *graph);

    // Edges on the lower polygon
    for(int ii = 0; ii < numOfSides - 1; ++ii)
        add_edge(ii, ii + 1, *graph);
    add_edge(numOfSides - 1, 0, *graph);

    // Edges on the upper polygon
    for(int ii = numOfSides; ii < 2 * numOfSides - 1; ++ii)
        add_edge(ii, ii + 1, *graph);
    add_edge(2 * numOfSides - 1 , numOfSides, *graph);
}

void isomorphism_test(int numOfSides)
{
    // Create and initialize the graphs
    shared_ptr<SimpleGraph> g1(new SimpleGraph(2 * numOfSides));
    shared_ptr<SimpleGraph> g2(new SimpleGraph(2 * numOfSides));
    initializeGraph(numOfSides, g1);
    initializeGraph(numOfSides, g2);


    std::cout << "\n\n GRAPH PROPERTIES \n" << std::endl;
    std::cout << "num. of vert.: " << num_vertices(*g1) << std::endl;
    std::cout << "num. of edges: " << num_edges(*g1) << std::endl;


    // Do some logging
    int maxDegree = 0;
    int maxDegreeCount = 1;
    boost::graph_traits<SimpleGraph>::vertex_iterator vIt,vItEnd;
    for (tie(vIt, vItEnd) = vertices(*g1); vIt != vItEnd; ++vIt)
    {
        int degree = out_degree(*vIt, *g1);
        if (maxDegree < degree) {
            maxDegree = degree;
            maxDegreeCount = 1;
        }
        else if (maxDegree == degree)
            maxDegreeCount++;

    }
    std::cout << "max.degree: " << maxDegree << "; num. of vert. with max. degree: " << maxDegreeCount << std::endl;


    std::cout << "\n\n ISOMOROPHISM TEST \n" << std::endl;
    boost::property_map<SimpleGraph, boost::vertex_index_t>::type ref_index_map = get(vertex_index, *g1);
    std::vector<boost::graph_traits<SimpleGraph>::vertex_descriptor> iso(num_vertices(*g2));
    bool ret = isomorphism(*g1,*g2,
                       isomorphism_map(make_iterator_property_map(iso.begin(), ref_index_map, iso[0])));
    std::cout << "Is isomorphic: " << ret << std::endl;
}

int main(int argc, char** argv)
{
    std::cout << "BGLTest" << std::endl;
    if (2 != argc) {
        std::cout << "Please give the number of sides as argument." << std::endl;
        exit(0);
    }

    if (getenv("COV_DEBUG_STOP"))
    {
        int ii = 0;
        while (ii != 1);
    }

    int numOfSides = atoi(argv[1]);
    std::cout << "Working with polyhedron, with " << numOfSides << " number of sides." << std::endl;

    // Test isomorphism
    isomorphism_test(numOfSides);

    return 0;
}