#include <iostream>

 #include <vector>

 #include <string>

 #include <marci_list_graph.hh>

 #include <marci_graph_traits.hh>

 #include <marci_property_vector.hh>

 #include <marci_bfs.hh>

 #include <marci_max_flow.hh>

 using namespace marci;

 int main (int, char*[])

 {

   typedef graph_traits<list_graph>::node_iterator node_iterator;

   typedef graph_traits<list_graph>::edge_iterator edge_iterator;

   typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;

   typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;

   typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;

   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;

   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;

   list_graph G;

   std::vector<node_iterator> vector_of_node_iterators;

   for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());

   for(int i=0; i!=8; ++i)

     for(int j=0; j!=8; ++j) {

       if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);

     }  

   std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;

   std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;

   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {

     std::cout << "node " << G.id(i) << std::endl;

     std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; 

     for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) { 

       std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";

     }

     std::cout << std::endl; 

     std::cout<< " ";

     for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) { 

       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 

     std::cout<<std::endl;

     std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";

     for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) { 

       std::cout << j << " "; } 

     std::cout << std::endl;

     std::cout<< " ";

     for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) { 

       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 

     std::cout<<std::endl;

     std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";

     for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) { 

       std::cout << j << " "; } 

     std::cout<<std::endl;

     std::cout<< " ";

     for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) { 

       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 

     std::cout<<std::endl;

   }

   std::cout << "all edges: ";

   for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {

     std::cout << i << " ";

   }

   std::cout << std::endl;

   std::cout << "node property array test" << std::endl;

   node_property_vector<list_graph, int> my_property_vector(G);

   each_node_iterator v;

   G.get_first(v);

   my_property_vector.put(v, 42);

   my_property_vector.put(++G.first_node(), 314);

   my_property_vector.put(++++G.first_node(), 1956);

   my_property_vector.put(vector_of_node_iterators[3], 1989);

   my_property_vector.put(vector_of_node_iterators[4], 2003);

   my_property_vector.put(vector_of_node_iterators[7], 1978);

   std::cout << "some node property values..." << std::endl;

   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {

     std::cout << my_property_vector.get(i) << std::endl;

   }

   int _i=1;

   int _ii=1;

   edge_property_vector<list_graph, int> my_edge_property(G);

   for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {

     my_edge_property.put(i, _i);

     _i*=_ii; ++_ii;

   }

   std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;

   for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) {

     std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";

   }

   std::cout << std::endl;

   //std::cout << "the same for inedges of the nodes..." << std::endl;

   //k=0;

   //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {

   //  for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {

   //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";

   //  }

   //  std::cout << std::endl;

   //}

   std::cout << "bfs from the first node" << std::endl;

   bfs<list_graph> bfs_test(G, G.first_node());

   bfs_test.run();

   std::cout << "reached: ";

   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {

     std::cout << bfs_test.reached.get(i) << " ";

   }

   std::cout<<std::endl;

   std::cout << "dist: ";

   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {

     std::cout << bfs_test.dist.get(i) << " ";

   }

   std::cout<<std::endl;

   std::cout << "augmenting path flow algorithm test..." << std::endl;

   list_graph flow_test;

   node_iterator s=flow_test.add_node();

   node_iterator v1=flow_test.add_node();

   node_iterator v2=flow_test.add_node();

   node_iterator v3=flow_test.add_node();

   node_iterator v4=flow_test.add_node();

   node_iterator t=flow_test.add_node();

   node_property_vector<list_graph, std::string> node_name(flow_test);

   node_name.put(s, "s");

   node_name.put(v1, "v1");

   node_name.put(v2, "v2");

   node_name.put(v3, "v3");

   node_name.put(v4, "v4");

   node_name.put(t, "t");

   edge_iterator s_v1=flow_test.add_edge(s, v1);

   edge_iterator s_v2=flow_test.add_edge(s, v2);

   edge_iterator v1_v2=flow_test.add_edge(v1, v2);

   edge_iterator v2_v1=flow_test.add_edge(v2, v1);

   edge_iterator v1_v3=flow_test.add_edge(v1, v3);

   edge_iterator v3_v2=flow_test.add_edge(v3, v2);

   edge_iterator v2_v4=flow_test.add_edge(v2, v4);

   edge_iterator v4_v3=flow_test.add_edge(v4, v3);

   edge_iterator v3_t=flow_test.add_edge(v3, t);

   edge_iterator v4_t=flow_test.add_edge(v4, t);

   edge_property_vector<list_graph, int> cap(flow_test);

   cap.put(s_v1, 16);

   cap.put(s_v2, 13);

   cap.put(v1_v2, 10);

   cap.put(v2_v1, 4);

   cap.put(v1_v3, 12);

   cap.put(v3_v2, 9);

   cap.put(v2_v4, 14);

   cap.put(v4_v3, 7);

   cap.put(v3_t, 20);

   cap.put(v4_t, 4);

   std::cout << "on directed graph graph" << std::endl; //<< flow_test;

   std::cout << "names and capacity values" << std::endl; 

   for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) { 

     std::cout << node_name.get(i) << ": ";

     std::cout << "out edges: ";

     for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j) 

       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";

     std::cout << "in edges: ";

     for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j) 

       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";

     std::cout << std::endl;

   }

   //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) { 

   //  std::cout << i << " ";

   //}

   max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);

   max_flow_test.run();

   return 0;

 }