#include "helpers.cpp"

#include<cstdio>
#include<vector>

#include <boost/config.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/adj_list_serialize.hpp> 
#include <boost/archive/text_oarchive.hpp>

using namespace boost;
using namespace std;

typedef adjacency_list<listS, vecS, directedS, Vertex, Edge> Graph;
typedef adjacency_list<setS, vecS, directedS, SccVertex> SccGraph;
typedef graph_traits<Graph>::vertex_descriptor vertex_t;
typedef graph_traits<Graph>::edge_descriptor edge_t;
typedef graph_traits<SccGraph>::vertex_descriptor vertex_scc_t;
typedef graph_traits<SccGraph>::edge_descriptor edge_scc_t;

Graph state_graph;

SccGraph scc_graph;
vector<int> component;

long long do_scc() {
    unsigned N = num_vertices(state_graph);
    component.resize(N);
    vector<int> discover_time(N);
    vector<int> color(N);
    vector<vertex_t> root(N);
    long long scc_count = strong_components(
            state_graph, make_iterator_property_map(component.begin(), get(vertex_index, state_graph)), 
            root_map(make_iterator_property_map(root.begin(), get(vertex_index, state_graph))).
            color_map(make_iterator_property_map(color.begin(), get(vertex_index, state_graph))).
            discover_time_map(make_iterator_property_map(discover_time.begin(), get(vertex_index, state_graph)))
    );
    return scc_count;
}

void create_scc_graph(long long scc_count, string filename) {
    typedef graph_traits<Graph>::edge_iterator edge_iter;
    
    vector< vertex_scc_t > vertices;
    for (int i = 0; i<scc_count; ++i) {
        vertex_scc_t u = add_vertex(scc_graph);
        SccVertex v;
        v.id = i;
        v.size = 0;
        v.starting = false;
        v.winning = false;
        scc_graph[u] = v;
        vertices.push_back(u);
    }

    std::vector<int>::size_type i;
    for (i = 0; i != component.size(); ++i) {
        vertex_scc_t v = vertices[component[i]];
        scc_graph[v].size++;
        if (state_graph[i].starting) {
            scc_graph[v].starting = true;
        }
        if (state_graph[i].winning) {
            scc_graph[v].winning = true;
        }
    }

    edge_iter ei, ei_end;
    for (tie(ei, ei_end) = edges(state_graph); ei != ei_end; ++ei) {
      vertex_t u = source(*ei,state_graph);
      vertex_t v = target(*ei,state_graph);
      int component_u = component[u];
      int component_v = component[v];
      if (component_u != component_v) {
          add_edge(vertices[component_u], vertices[component_v], scc_graph);
      }
    }

    {
        std::ofstream dot_file(filename);
        boost::archive::text_oarchive oa(dot_file);
        oa << scc_graph;
    }
}

int main(int argc, char* argv[]) {
    if (argc < 3) {
        return 0;
    }
    {
        string filename = argv[1];
        read(state_graph, filename);
    }

    long long scc_count = do_scc();

    {
        string filename = argv[2];
        create_scc_graph(scc_count, filename);
    }

    return 0;
}
