#include <boost/config.hpp>
#include <iostream>                      // for std::cout
#include <fstream>						 //for std::ifstream
#include <utility>                       // for std::pair
#include <boost/utility.hpp>             // for boost::tie
#include <boost/graph/graph_traits.hpp>  // for boost::graph_traits
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>

using namespace boost;
using namespace std;

enum edge_cost_t { edge_cost };

namespace boost {
  BOOST_INSTALL_PROPERTY(edge, cost);
}

//create a typedef for the Graph type
typedef property<edge_cost_t, int> Costs;

typedef adjacency_list<multisetS, vecS, bidirectionalS, no_property, Costs> Graph;


//create typedefs for the property maps
typedef property_map<Graph, edge_cost_t>::type CostVal;

//create a typedef for the edge descriptor, edge iterator and vertex iterator
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef graph_traits<Graph>::vertex_iterator vertex_iter;

struct my_edge_writer {
  my_edge_writer(Graph& G_) : G(G_) {};
   void operator()(std::ostream& out, const   graph_traits < Graph >::edge_descriptor& e) const {
     out << "[label=\"";
     out << get(edge_cost,G)[e];
     out << "\"]";
   }
private:
  Graph& G;
};

struct my_node_writer {
  my_node_writer(Graph& G_, int d[]) : G(G_) {
	dist = vector<int>(num_vertices(G_));
	
	for (int i=0; i<num_vertices(G_); i++)
	    dist[i] = d[i];
  };
   void operator()(std::ostream& out, const   graph_traits < Graph >::vertex_descriptor& v) const {
     out << "[label=\"";
     out << dist[v];
     out << "\"]";
   }
private:
  Graph& G;
  vector<int> dist;
};

int main() {
	
	int num_vertex;
	int num_edges;
	
	int from, to, cost;
	ifstream file("GraphEX.txt");
	
	if (!file.is_open()) {
		cout << "File Error!" << endl;
		return 0;
	}
	else{
		file >> num_vertex >> num_edges;
		Graph g(num_vertex); // construct a graph object
		for (int j = 0; j < num_edges; j++) {
			file >> from >> to >> cost;
			Edge e; bool inserted;
			tie(e, inserted) = add_edge(from, to, Costs(cost), g);  //intialize the edges
		}
		file.close();
		
		CostVal cost_map = get(edge_cost, g);
		
		pair<vertex_iter, vertex_iter> vp2 =vertices(g);
		property_map<Graph, vertex_index_t>::type vert_index = get(vertex_index, g);
	
		int distance[num_vertex];
	
		fill(distance, distance + num_vertex, (numeric_limits < int >::max)());
		// Specify the first vertex as the source vertex
		distance[vert_index[*vp2.first]] = 0;
	
		int parent[num_vertex];
		for (int i = 0; i < num_vertex; ++i)
			parent[i] = i;
		
		bool r = bellman_ford_shortest_paths(g, int (num_vertex), weight_map(cost_map).distance_map(&distance[0]).predecessor_map(&parent[0]));
		if(!r)
			cout << "Graph contains negative cycles!!" << endl;
		else
			cout << "Graph does NOT contain negative cycles!!" << endl;
			
		remove_edge(0, 2, g);
		remove_edge(0, 3, g);
		remove_edge(4, 6, g);
		remove_edge(1, 2, g);
		remove_edge(5, 6, g);
		remove_edge(3, 2, g);
		remove_edge(5, 7, g);
		
		fill(distance, distance + num_vertex, (numeric_limits < int >::max)());
		// Specify the first vertex as the source vertex
		distance[vert_index[*vp2.first]] = 0;

		for (int i = 0; i < num_vertex; ++i)
			parent[i] = i;
		
		r = bellman_ford_shortest_paths(g, int (num_vertex), weight_map(cost_map).distance_map(&distance[0]).predecessor_map(&parent[0]));
		if(!r)
			cout << "Graph contains negative cycles!!" << endl;
		else
			cout << "Graph does NOT contain negative cycles!!" << endl;
			
		add_edge(4, 6, Costs(3), g);
		
		fill(distance, distance + num_vertex, (numeric_limits < int >::max)());
		// Specify the first vertex as the source vertex
		distance[vert_index[*vp2.first]] = 0;

		for (int i = 0; i < num_vertex; ++i)
			parent[i] = i;
			
		cout << "---Writing graph which goes to Bellmann-Ford" << endl;
		ofstream out ("graph.dot");
        write_graphviz(out, g, my_node_writer(g,distance), my_edge_writer(g));		
		out.close();
		cout << "---Graph written" << endl;
		
		r = bellman_ford_shortest_paths(g, int (num_vertex), weight_map(cost_map).distance_map(&distance[0]).predecessor_map(&parent[0]));
		if(!r)
			cout << "Graph contains negative cycles!!" << endl;
		else
			cout << "Graph does NOT contain negative cycles!!" << endl;
			
		cout << "*** Writing graph which came from Bellmann-Ford" << endl;
		ofstream out2 ("graph-bf.dot");
        write_graphviz(out2, g, my_node_writer(g,distance), my_edge_writer(g));		
		out2.close();
		cout << "*** Graph written" << endl;
	
	return 1;
	}
}