//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under 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)
//=======================================================================
#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

#include <boost/graph/adjacency_list.hpp>

using namespace boost;
using namespace std;

typedef property< vertex_color_t, default_color_type,
    property< vertex_distance_t, int,
        property< vertex_degree_t, int,
            property< vertex_in_degree_t, int,
                property< vertex_out_degree_t, int > > > > >
    VertexProperty;
typedef property< edge_weight_t, int > EdgeProperty;
typedef adjacency_list< vecS, vecS, bidirectionalS, VertexProperty,
    EdgeProperty >
    Graph;

template < class Graph > void print(Graph& g)
{
    typename Graph::vertex_iterator i, end;
    typename Graph::out_edge_iterator ei, edge_end;
    for (boost::tie(i, end) = vertices(g); i != end; ++i)
    {
        cout << *i << " --> ";
        for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
            cout << target(*ei, g) << "  ";
        cout << endl;
    }
}

std::size_t myrand(std::size_t N)
{
    std::size_t ret = rand() % N;
    //  cout << "N = " << N << "  rand = " << ret << endl;
    return ret;
}

template < class Graph > bool check_edge(Graph& g, std::size_t a, std::size_t b)
{
    typename Graph::adjacency_iterator vi, viend, found;
    boost::tie(vi, viend) = adjacent_vertices(vertex(a, g), g);

    found = find(vi, viend, vertex(b, g));
    if (found == viend)
        return false;

    return true;
}

int main(int, char*[])
{
    std::size_t N = 5;

    Graph g(N);
    int i;

    bool is_failed = false;

    for (i = 0; i < 6; ++i)
    {
        std::size_t a = myrand(N), b = myrand(N);
        while (a == b)
            b = myrand(N);
        cout << "edge edge (" << a << "," << b << ")" << endl;
        // add edges
        add_edge(a, b, g);
        is_failed = is_failed || (!check_edge(g, a, b));
    }

    if (is_failed)
        cerr << "    Failed." << endl;
    else
        cerr << "           Passed." << endl;

    print(g);

    // remove_edge
    for (i = 0; i < 2; ++i)
    {
        std::size_t a = myrand(N), b = myrand(N);
        while (a == b)
            b = myrand(N);
        cout << "remove edge (" << a << "," << b << ")" << endl;
        remove_edge(a, b, g);
        is_failed = is_failed || check_edge(g, a, b);
    }
    if (is_failed)
        cerr << "    Failed." << endl;
    else
        cerr << "           Passed." << endl;

    print(g);

    // add_vertex
    is_failed = false;
    std::size_t old_N = N;
    std::size_t vid = add_vertex(g);
    std::size_t vidp1 = add_vertex(g);

    N = num_vertices(g);
    if ((N - 2) != old_N)
        cerr << "    Failed." << endl;
    else
        cerr << "           Passed." << endl;

    is_failed = false;
    for (i = 0; i < 2; ++i)
    {
        std::size_t a = myrand(N), b = myrand(N);
        while (a == vid)
            a = myrand(N);
        while (b == vidp1)
            b = myrand(N);
        cout << "add edge (" << vid << "," << a << ")" << endl;
        cout << "add edge (" << vid << "," << vidp1 << ")" << endl;
        add_edge(vid, a, g);
        add_edge(b, vidp1, g);
        is_failed = is_failed || !check_edge(g, vid, a);
        is_failed = is_failed || !check_edge(g, b, vidp1);
    }
    if (is_failed)
        cerr << "    Failed." << endl;
    else
        cerr << "           Passed." << endl;
    print(g);

    // clear_vertex
    std::size_t c = myrand(N);
    is_failed = false;
    clear_vertex(c, g);

    if (out_degree(c, g) != 0)
        is_failed = true;

    cout << "Removing vertex " << c << endl;
    remove_vertex(c, g);

    old_N = N;
    N = num_vertices(g);

    if ((N + 1) != old_N)
        is_failed = true;

    if (is_failed)
        cerr << "    Failed." << endl;
    else
        cerr << "           Passed." << endl;

    print(g);

    return 0;
}