#include <iostream>
#include <queue>
#include <vector>
#include <math.h>

#include <lemon/invalid.h>
#include <lemon/list_graph.h>
#include <lemon/smart_graph.h>
#include <matching.h>

using namespace lemon;
using namespace std;


int main() {

  typedef UndirSmartGraph Graph;

  typedef Graph::Edge Edge;
  typedef Graph::UndirEdgeIt UndirEdgeIt;
  typedef Graph::IncEdgeIt IncEdgeIt;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::Node Node;

  typedef Graph::OutEdgeIt OutEdgeIt;
   
  Graph G;

  // G.clear();
  std::vector<Graph::Node> nodes;
  for (int i=0; i<5; ++i)
      nodes.push_back(G.addNode());
  G.addEdge(nodes[0], nodes[0]);
  G.addEdge(nodes[0], nodes[1]);
  G.addEdge(nodes[0], nodes[2]);  
  G.addEdge(nodes[0], nodes[4]);
  G.addEdge(nodes[2], nodes[3]);
  G.addEdge(nodes[1], nodes[2]);
  G.addEdge(nodes[2], nodes[4]);

  for(UndirEdgeIt e(G); e!=INVALID; ++e) {
    std::cout<<G.id(e)<<" : "<<G.id(G.source(e))
	     <<" " <<G.id(G.target(e))<<std::endl;
  }

  std::cout <<"Nodes:"<<std::endl;

  for(NodeIt v(G); v!=INVALID; ++v) {
    std::cout<<G.id(v)<<std::endl;
  }

  cout << "Dev Out edges from node " << G.id(nodes[1])<<std::endl;
  Edge f;
  for(G.firstOut(f, nodes[1]); f!=INVALID; G.nextOut(f)) {
    cout<<"edge " << G.id(f) << " goes"
	     <<" from "<< G.id(G.source(f)) 
	     << " to " << G.id(G.target(f))<<std::endl;
  }

  cout << "Out edges from node " << G.id(nodes[1])<<std::endl;
  for( OutEdgeIt f(G,nodes[1]); f!=INVALID; ++f ) {
    cout<<"edge " << G.id(f) << " goes"
	     <<" from "<< G.id(G.source(f)) 
	     << " to " << G.id(G.target(f))<<std::endl;
  }

  std::cout<<"Edges of node " << G.id(nodes[1])<<std::endl;
  for( IncEdgeIt f(G,nodes[1]); f!=INVALID; ++f ) {
    cout<<"edge " << G.id(f) << " goes"
	     <<" from "<< G.id(G.source(f)) 
	     << " to " << G.id(G.target(f))<<std::endl;
  }

  //return 0;

  //ez a ket for ciklus meg lefut - bar hibas eleken iteral -, de a
  //matching.h-s mar segfaultol

  for( IncEdgeIt f(G,nodes[1]); f!=INVALID; ++f ) {
    std::cout<<"edge " << G.id(f)<< " goes to " << G.id(G.target(f))<<std::endl;
  }

  MaxMatching<Graph> max_matching(G);
  max_matching.runEdmonds(0);
  
  return 0;
}