#include<iostream>
#include<lemon/list_graph.h>
#include<lemon/lgf_reader.h>
#include<lemon/dfs.h>

using namespace lemon;
using namespace std;

int main(){
	
  ListDigraph g;
  ListDigraph::NodeMap<string> label(g);

  // ==================================================
  // Open and read file.
  ifstream file("22.4.lgf");
  stringstream input;
  if(file){
    input << file.rdbuf();
    file.close();
  } else {
    cout << "File not found " << endl;
    exit(1);
  }	
	
  // Parser.
  DigraphReader<ListDigraph>(g, input).
    nodeMap("label", label).
    run();
	
  // See if got digraph right
  cout << "Node: out neighbors" << endl;

  for(ListDigraph::NodeIt v(g); v != INVALID; ++v){
    cout << label[v] << " " << " : ";
		
    for(ListDigraph::OutArcIt e(g, v); e != INVALID; ++e){
      cout <<  " " << label[g.oppositeNode(v, e)];
    }

    cout << endl;
  }

  // ==================================================
  // Now DFS
  Dfs<ListDigraph> dfs(g);

  dfs.run();

  // Print predecessors
  cout << "Predecessors:" << endl;
  
  for (ListDigraph::NodeIt v(g); v != INVALID; ++v) {
    if (dfs.reached(v)) {
      ListDigraph::Node pred = dfs.predNode(v);
      if (pred != INVALID) {
	cout << label[v] << " from " << label[dfs.predNode(v)] << endl;
      } else {
	cout << label[v] << " from " << "NIL" << endl;
      }
    }
  }
  
  cout << endl;
}