//=======================================================================
// 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)
//=======================================================================

// Some small modifications are done by Alexander Holler

/*

  Paul Moore's request:

  As an example of a practical problem which is not restricted to graph
  "experts", consider file dependencies. It's basically graph construction,
  plus topological sort, but it might make a nice "tutorial" example. Build a
  dependency graph of files, then use the algorithms to do things like

  1. Produce a full recompilation order (topological sort, by modified date)
  2. Produce a "parallel" recompilation order (same as above, but group files
  which can be built in parallel)
  3. Change analysis (if I change file x, which others need recompiling)
  4. Dependency changes (if I add a dependency between file x and file y, what
  are the effects)

*/

#include <boost/config.hpp> // put this first to suppress some VC++ warnings

#include <iostream>
#include <iterator>
#include <algorithm>
#include <time.h>

#include <boost/utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/visitors.hpp>

using namespace std;
using namespace boost;

enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp, 
               foo_o, bar_cpp, bar_o, libfoobar_a,
               zig_cpp, zig_o, zag_cpp, zag_o, 
                 libzigzag_a, killerapp, N };
const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
                       "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
                       "zig.cpp", "zig.o", "zag.cpp", "zag.o",
                       "libzigzag.a", "killerapp" };


struct print_visitor : public bfs_visitor<> {
  template <class Vertex, class Graph>
  void discover_vertex(Vertex v, Graph&) {
    cout << name[v] << " ";
  }
};


struct cycle_detector : public dfs_visitor<>
{
  cycle_detector(bool& has_cycle) 
    : m_has_cycle(has_cycle) { }

  template <class Vertex, class Graph>
  void initialize_vertex(Vertex u, Graph&)
  {
	  std::cout<<"initialize_vertex: "<<name[u]<<endl;
  }  
  template <class Vertex, class Graph>
  void start_vertex(Vertex u, Graph&)
  {
	  std::cout<<"start_vertex: "<<name[u]<<endl;
  }
  template <class Vertex, class Graph>
  void discover_vertex(Vertex u, Graph&)
  {
	std::cout<<"discover_vertex: "<<name[u]<<endl;
  }  
  template <class Edge, class Graph>
  void examine_edge(Edge edge, Graph& g) 
  {
	  std::cout<<"examine_edge: "<<name[source(edge, g)]<<" --> "<<name[target(edge, g)] <<endl;
  }
  template <class Edge, class Graph>
  void tree_edge(Edge edge, Graph& g) 
  {
	   std::cout<<"tree_edge: "<<name[source(edge, g)]<<" --> "<<name[target(edge, g)] <<endl;
  }
  template <class Edge, class Graph>
  void back_edge(Edge edge, Graph& g) 
  { 
	  std::cout<<"back_edge: "<<name[source(edge, g)]<<" --> "<<name[target(edge, g)] <<endl;
	  m_has_cycle = true; 
  }
  template <class Edge, class Graph>
  void forward_or_cross_edge(Edge edge, Graph& g) 
  { 
	 std::cout<<"forward_or_cross_edge: "<<name[source(edge, g)]<<" --> "<<name[target(edge, g)] <<endl;
  }
  template <class Vertex, class Graph>
  void finish_vertex(Vertex u, Graph&)
  {
	  std::cout<<"finish_vertex: "<<name[u]<<endl;
  }

protected:
  bool& m_has_cycle;
};


int main(int,char*[])
{
  typedef pair<int,int> Edge;
  Edge used_by[] = {
    Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
    Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
    Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
    Edge(zow_h, foo_cpp), 
    Edge(foo_cpp, foo_o),
    Edge(foo_o, libfoobar_a),
    Edge(bar_cpp, bar_o),
    Edge(bar_o, libfoobar_a),
    Edge(libfoobar_a, libzigzag_a),
    Edge(zig_cpp, zig_o),
    Edge(zig_o, libzigzag_a),
    Edge(zag_cpp, zag_o),
    Edge(zag_o, libzigzag_a),
    Edge(libzigzag_a, killerapp)
  };
  const std::size_t nedges = sizeof(used_by)/sizeof(Edge);

  //typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
  typedef adjacency_list<vecS, vecS, undirectedS,no_property,
    property<edge_color_t, default_color_type>> Graph;
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  // VC++ can't handle the iterator constructor
  Graph g(N);
  for (std::size_t j = 0; j < nedges; ++j) {
    graph_traits<Graph>::edge_descriptor e; bool inserted;
    boost::tie(e, inserted) = add_edge(used_by[j].first, used_by[j].second, g);
  }
#else
  Graph g(used_by, used_by + nedges, N);
#endif
  typedef graph_traits<Graph>::vertex_descriptor Vertex;

  // are there any cycles in the graph?
  {
    bool has_cycle = false;
    cycle_detector vis(has_cycle);
    //depth_first_search(g, visitor(vis));
	
	undirected_dfs(g, root_vertex(Vertex(0)).visitor(vis)
                 .edge_color_map(get(edge_color, g)));

    cout << "The graph has a cycle? " << has_cycle << endl;
  }
  cout << endl;
  
  getchar();
  return 0;
}