// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software

// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor

//           Andrew Lumsdaine

/*

 * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

*/

#include <boost/graph/biconnected_components.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/test/minimal.hpp>

#include <boost/lexical_cast.hpp>

#include <vector>

#include <iterator>

#include <iostream>

#include <algorithm>

#include <boost/graph/connected_components.hpp>

#include <boost/graph/random.hpp>

#include <boost/random/linear_congruential.hpp>

#include <fstream>

#ifdef __SYMBIAN32__

#include "std_log_result.h"

#define LOG_FILENAME_LINE __FILE__, __LINE__

#endif

using namespace boost;

struct EdgeProperty

{

  std::size_t component;

};

static bool any_errors = false;

template<typename Graph, typename Vertex>

void 

check_articulation_points(const Graph& g, std::vector<Vertex> art_points)

{

  std::vector<int> components(num_vertices(g));

  int basic_comps = 

    connected_components(g, 

                         make_iterator_property_map(components.begin(), 

                                                    get(vertex_index, g),

                                                    int()));

  std::vector<Vertex> art_points_check;

  typename graph_traits<Graph>::vertex_iterator vi, vi_end;

  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {

    Graph g_copy(g);

    Vertex victim = vertex(get(vertex_index, g, *vi), g_copy);

    clear_vertex(victim, g_copy);

    remove_vertex(victim, g_copy);

    int copy_comps = 

      connected_components

        (g_copy, 

         make_iterator_property_map(components.begin(), 

                                    get(vertex_index, g_copy),

                                    int()));

    if (copy_comps > basic_comps)

      art_points_check.push_back(*vi);

  }

  std::sort(art_points.begin(), art_points.end());

  std::sort(art_points_check.begin(), art_points_check.end());

  BOOST_CHECK(art_points == art_points_check);

  if (art_points != art_points_check) {

    std::cerr << "ERROR!" << std::endl;

    std::cerr << "\tComputed: ";

    std::size_t i;

    for (i = 0; i < art_points.size(); ++i) 

      std::cout << art_points[i] << ' ';

    std::cout << std::endl << "\tExpected: ";

    for (i = 0; i < art_points_check.size(); ++i)

      std::cout << art_points_check[i] << ' ';

    std::cout << std::endl;

    any_errors = true;

  } else std::cout << "OK." << std::endl;

}

int test_main(int argc, char* argv[])

{

  std::size_t n = 100;

  std::size_t m = 500;

  std::size_t seed = 1;

  if (argc > 1) n = lexical_cast<std::size_t>(argv[1]);

  if (argc > 2) m = lexical_cast<std::size_t>(argv[2]);

  if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);

  typedef adjacency_list<listS, vecS, undirectedS,

                         no_property, EdgeProperty> Graph;

  typedef graph_traits<Graph>::vertex_descriptor Vertex;

  Graph g(n);

  minstd_rand gen(seed);

  generate_random_graph(g, n, m, gen);

  std::vector<Vertex> art_points;

  std::cout << "Computing biconnected components & articulation points... ";

  std::cout.flush();

  std::size_t num_comps = 

    biconnected_components(g, 

                           get(&EdgeProperty::component, g),

                           std::back_inserter(art_points)).first;

  std::cout << "done.\n\t" << num_comps << " biconnected components.\n"

            << "\t" << art_points.size() << " articulation points.\n"

            << "\tTesting articulation points...";

  std::cout.flush();

  check_articulation_points(g, art_points);

  if (any_errors) {

    std::ofstream out("biconnected_components_test_failed.dot");

    out << "graph A {\n" << "  node[shape=\"circle\"]\n";

    for (std::size_t i = 0; i < art_points.size(); ++i) {

      out << art_points[i] << " [ style=\"filled\" ];" << std::endl;

    }

    graph_traits<Graph>::edge_iterator ei, ei_end;

    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)

      out << source(*ei, g) << " -- " << target(*ei, g)

          << "[label=\"" << g[*ei].component << "\"]\n";

    out << "}\n";

  }

 #ifdef __SYMBIAN32__

	std_log(LOG_FILENAME_LINE,"[End Test Case ]");

	testResultXml("biconnected_components_test");

	close_log_file();

#endif

  return 0;

}