/**
 * Shortest paths with unique labels
 * April 02, 2008 Tom Kamphans
 *
 * Compile:
 * g++ -m64 -O2 -g0 -o sp sp.cpp
 *
 *
 * Compiler options:
 * BFS      : perform simple BFS
 * RBFS     : perform simple BFS, edges in reverse order
 * BUSEARCH : perform buttom-up search
 * RNDSEARCH: perform random search
 * UNIEDGES : Store unique edges, too 
 * BFSCOMPL : perform complete BFS search; uses a lot of memory!!
 *
 * EBUG     : print some progress informations    
 *
 *
 * Exit codes:
 * 0: normal
 * 1: fatal
 * 2: Input file not found or corrupt
 *
 */

//define EBUG
#define UNIEDGES
#define BFS
#define RBFS
#define BFSCOMPL

/*
***********************************************************************
***                                                                 ***
*** Dislcaimer:                                                     ***
***                                                                 ***
*** This code is NOT a bright example for good programming style.   ***
*** It is merely a quite ugly quick-and-dirty hack that serves its  ***
*** purpose.                                                        ***
*** For example, keeping all classes in one file is not recommended ***
*** and ususally considered as very bad style, but it had an        ***
*** advantages for this program: compiling is quite simple.         ***
***                                                                 ***
***********************************************************************
*/

#include <list>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <string>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <sstream>
#include <ctime>

int thepass = 0;
int debuglevel = 1;
int searchlevel = 1;
int inputlevel = 0;
int justbfs = 0;
int skippreproc = 0;
int profile = 0;
int SPTNcounter = -1;

std::list<std::string> _S;

void clearMarkers();
class Vertex;

//********************************************************************
//
// Edge Header
//
//********************************************************************
class Edge {
public:
  Edge();
  Edge( Vertex* f, Vertex* t, std::string l);
  std::string getLabel();
  Vertex* from();
  Vertex* to();
  void printOn( std::ostream &strm );
#ifdef UNIEDGES
  void insert( Edge *e );
  Edge *getNext();
#endif

private:
  Vertex *_from;
  Vertex *_to;
  std::string _label;
#ifdef UNIEDGES
  Edge *_next;
#endif
}; // Edge

inline std::ostream& operator << (std::ostream &strm, Edge &e)
{ e.printOn(strm); return strm; }

typedef std::list<Edge>::iterator EdgeIterator;
typedef std::list<Edge>::reverse_iterator RevEdgeIterator;


//********************************************************************
//
// Vertex Header
//
//********************************************************************

class Vertex {
public:
    bool isReported;
    int pruned;
    
    Vertex();
    Vertex( std::string l );
    bool isAdjacent( Vertex *v );
    bool isLabelValidPath( std::string label );
    int prune( Vertex *target );
    bool isReachable( Vertex *target );
    void addEdge( Edge& e ) ;
    void getFirstEdge();
    Edge* getNextEdge();
    bool hasNextEdge();
    EdgeIterator getEdges();
    EdgeIterator getEdgesEnd();
#ifdef BUSEARCH
    void addInEdge( Edge& e );
    EdgeIterator getInEdges();
    EdgeIterator getInEdgesEnd();
#endif

#ifdef UNIEDGES
    Edge* getFirstUniEdge( Vertex *target );
    EdgeIterator getUniEdges();
    EdgeIterator getUniEdgesEnd();
#endif
    RevEdgeIterator getRevEdges();
    RevEdgeIterator getRevEdgesEnd();
    void setInEdge( Edge* e );
    Vertex* getFather();
    std::string getEdgeLabel();
    std::string getLabel();
    void setVisited();
    void clearVisited();
    bool isVisited();
    void printLabel( std::ostream &strm );
    void printOn( std::ostream &strm );


private:
    std::string _label;
    std::list<Edge> _edges;
    Edge* _inEdge;
    bool _isVisited;
    EdgeIterator _ite;
#ifdef BUSEARCH
    std::list<Edge> _inedges;
#endif
#ifdef UNIEDGES
    std::list<Edge> _uniedges;
#endif

    bool _isReachableRec( Vertex* from, Vertex *target );
}; // Vertex



//********************************************************************
//
// Vertex Implementierung
//
//********************************************************************


//-----------------------------------------------------------------
Vertex::Vertex() 
//-----------------------------------------------------------------
{
    _isVisited = false;
    _inEdge = NULL;
    isReported = false;
    pruned = 0;
} // Vertex()


//-----------------------------------------------------------------
Vertex::Vertex( std::string l )
//-----------------------------------------------------------------
{
    _isVisited = false;
    _label = l;
    _inEdge = NULL;
    isReported = false;
    pruned = 0;
} // Vertex()


//-----------------------------------------------------------------
bool Vertex::isAdjacent( Vertex *v )
//-----------------------------------------------------------------
{
    EdgeIterator it;
    for( it = _edges.begin(); it != _edges.end(); it++) {
	if ( it->to() == v) return true;
    } // for
    return false;
} // isAdjacent


/**
 * returns true iff the input label is never used on the path
 * from this to the root of the SPT:
 */

//-----------------------------------------------------------------
bool Vertex::isLabelValidPath( std::string label )
//-----------------------------------------------------------------
{
    Vertex *vp = this;
    while ( vp != NULL ) {
	if ( vp->getEdgeLabel() == label ) {
	    return false;
	}
	vp = vp->getFather();
    } // while
    
    return true;
    
} // isLabelValidPath


//-----------------------------------------------------------------
int Vertex::prune( Vertex *target )
//-----------------------------------------------------------------
{
    if ( pruned > 0 ) return pruned;
    pruned = 2;
    EdgeIterator it;
    int pchilds = 0;
    
    for( it = _edges.begin(); it != _edges.end(); it++) {
	if ( it->to() == NULL ) {
	    std::cerr << "?!?!?!?!?!?!"; exit( 3 ) ;
	}
	pchilds += it->to()->prune( target );
    } // for
    if ( (this!=target) && (pchilds == _edges.size() )) {
	pruned = 1;
    }
    return pruned;
    
} // prune 

//-----------------------------------------------------------------
bool Vertex::isReachable( Vertex *target )
//-----------------------------------------------------------------
{
    clearMarkers();
    return _isReachableRec( this, target );
} // isReachable
    

//-----------------------------------------------------------------
void Vertex::addEdge( Edge& e ) 
//-----------------------------------------------------------------
{
    _edges.push_back( e );
    
#ifdef UNIEDGES
    Edge *ep = &_edges.back(); // W H Y ???
    EdgeIterator it;
    for(it = _uniedges.begin(); it != _uniedges.end(); it++) 
	if ( it->to() == e.to() ) {
	    it->insert( ep );
	    break;
	} 
    if ( it == _uniedges.end() ) 
	_uniedges.push_back( e );
#endif
    
} // addEdge


//-----------------------------------------------------------------
void Vertex::getFirstEdge()
//-----------------------------------------------------------------
{
    _ite = _edges.begin();
} // getFirstEdge
    

//-----------------------------------------------------------------
Edge* Vertex::getNextEdge()
//-----------------------------------------------------------------
{
    return &*_ite++;
} // getNextEdge
  

//-----------------------------------------------------------------
bool Vertex::hasNextEdge()
//-----------------------------------------------------------------
{
    return ( _ite != _edges.end() );
} // hasNextEdge

  
//-----------------------------------------------------------------
EdgeIterator Vertex::getEdges()
//-----------------------------------------------------------------
{
#ifdef RNDSEARCH
    std::random_shuffle ( _rndedges.begin(), _rndedges.end() );
#endif
    return _edges.begin();
} // getEdges

  
//----------------------------------------------------------------- 
EdgeIterator Vertex::getEdgesEnd()
//-----------------------------------------------------------------
{
    return _edges.end();
} // getEdgesEnd


#ifdef BUSEARCH
//-----------------------------------------------------------------
void Vertex::addInEdge( Edge& e ) 
//-----------------------------------------------------------------
{
    _inedges.push_back( e );
} // addInEdge


//-----------------------------------------------------------------
EdgeIterator Vertex::getInEdges()
//-----------------------------------------------------------------
{
    return _inedges.begin();
} // getInEdges


//----------------------------------------------------------------- 
EdgeIterator Vertex::getInEdgesEnd()
//-----------------------------------------------------------------
{
    return _inedges.end();
} // getInEdgesEnd
#endif


#ifdef UNIEDGES
//-----------------------------------------------------------------
Edge* Vertex::getFirstUniEdge( Vertex *target )
//-----------------------------------------------------------------
{
    for(EdgeIterator it = _uniedges.begin(); it != _uniedges.end(); it++) 
	if ( it->to() == target ) return &*it;
    return NULL;
} // getFirstUniEdge
  

//-----------------------------------------------------------------
EdgeIterator Vertex::getUniEdges()
//-----------------------------------------------------------------
{
    return _uniedges.begin();
} // getUniEdges


//----------------------------------------------------------------- 
EdgeIterator Vertex::getUniEdgesEnd()
//-----------------------------------------------------------------
{
    return _uniedges.end();
} // getUniEdgesEnd
#endif


//-----------------------------------------------------------------
RevEdgeIterator Vertex::getRevEdges()
//-----------------------------------------------------------------
{
    return _edges.rbegin();
} // getRevEdges

//----------------------------------------------------------------- 
RevEdgeIterator Vertex::getRevEdgesEnd()
//-----------------------------------------------------------------
{
    return _edges.rend();
} // getRevEdgesEnd



//-----------------------------------------------------------------
void Vertex::setInEdge( Edge* e )
//-----------------------------------------------------------------
{
    _inEdge = e;
} // setInEdge


//-----------------------------------------------------------------
Vertex* Vertex::getFather()
//-----------------------------------------------------------------
{
    if ( _inEdge != NULL )
	return _inEdge->from();
    else
	return NULL;
} // getFather


//-----------------------------------------------------------------
std::string Vertex::getEdgeLabel()
//-----------------------------------------------------------------
{
    if ( _inEdge != NULL )
	return _inEdge->getLabel();
    else
	return std::string("");
} // getLabel


//-----------------------------------------------------------------
std::string Vertex::getLabel()
//-----------------------------------------------------------------
{
    return _label;
} // getLabel


//-----------------------------------------------------------------
void Vertex::setVisited()
//-----------------------------------------------------------------
{
    _isVisited = true;
} // setVisited


//-----------------------------------------------------------------
void Vertex::clearVisited()
//-----------------------------------------------------------------
{
    _isVisited = false;
} // clearVisited


//-----------------------------------------------------------------
bool Vertex::isVisited()
//-----------------------------------------------------------------
{
    return _isVisited;
} // isVisited


//-----------------------------------------------------------------
void Vertex::printLabel( std::ostream &strm )
//-----------------------------------------------------------------
{
    strm << _label;
} // printLabel


//-----------------------------------------------------------------
void Vertex::printOn( std::ostream &strm )
//-----------------------------------------------------------------
{
    strm << _label; // << " Visited: " << _isVisited;
    if ( _inEdge != NULL ) {
	if ( _inEdge->from() != NULL ) {
	    strm << " Father: " << _inEdge->from()->getLabel() << std::endl;
	}
    }
    strm << "\n";
    for(EdgeIterator it = _edges.begin(); it != _edges.end(); it++) {
	strm << "--> " << *it << std::endl;
    } // for
#ifdef BUSEARCH
    for(EdgeIterator it = _inedges.begin(); it != _inedges.end(); it++) {
	strm << "<-- " << *it << std::endl;
    } // for
#endif
#ifdef UNIEDGES
    int i=0;
    for(std::list<Edge>::iterator it = _uniedges.begin(); 
	it != _uniedges.end(); it++) {
	Edge *e;
	for (e = &*it; e != NULL; e = e->getNext(), i++)
	    if ( e == &*it) strm << i << "----> " << *e << std::endl;
	    else strm << i << "  +-> " << *e << std::endl;
    } // for
#endif
} // printOn


//-----------------------------------------------------------------
bool Vertex::_isReachableRec( Vertex* from, Vertex *target )
//-----------------------------------------------------------------
{
    if ( target->getLabel() == this->getLabel() ) 
	return true;

    EdgeIterator last = getEdgesEnd();
    EdgeIterator eit = getEdges();;
    Vertex *vp;
    bool found = false;
    
    this->setVisited();
    
    while ( eit != last) {
	vp = eit->to();
	if ( ! vp->isVisited() ) { 
	    if ( this->isLabelValidPath( eit->getLabel() )) {
		vp->setInEdge( &*eit );
		found = vp->_isReachableRec( from, target );
		if ( found ) return true;
	    } 
	} // if ! isVisited
	eit++;
    } // while
    
    this->clearVisited();
    return false;
    
} // _isReachableRec

inline std::ostream& operator << (std::ostream &strm, Vertex &v)
{ v.printOn(strm); return strm; }


//********************************************************************
//
// SPTNode Header
//
//********************************************************************

class SPTNode {

public:
    SPTNode* father;
    Edge* content;
    
    SPTNode();
    SPTNode( SPTNode *f ) ;
    SPTNode( SPTNode *f, Edge *c );
    ~SPTNode();
    bool isValidSPTPath( Edge *e );
#ifdef UNIEDGES
    bool isValidUniqueSPTPath( Edge *e );
    bool isValidUniqueSPTPath( Vertex *target );
#endif
    void incRefCounter();
    void decRefCounter();
    void printOn( std::ostream &strm );

    static int getNumCount();

private:
    int _refcount;
    static int _idcount;
    //  static std::list<std::string> _S;

    int _printOnRec( std::ostream &strm );

}; // SPTNode


//********************************************************************
//
// SPTNode Implementierung
//
//********************************************************************

//-----------------------------------------------------------------
SPTNode::SPTNode() 
//-----------------------------------------------------------------
{
    father = NULL;
    content = NULL;
    _refcount = 0;
    if ( ++_idcount % 1000000 == 0) 
	if ( debuglevel > 1 )
	    std::cerr << "+" << _idcount << "\n";
} 

//-----------------------------------------------------------------
SPTNode::SPTNode( SPTNode *f ) 
//-----------------------------------------------------------------
{
    if ( f->father == NULL ) father = NULL;
    else {
	father = new SPTNode( f->father );
	father->incRefCounter();
    }
    content = f->content;
    _refcount = 0;
    if ( ++_idcount % 1000000 == 0) 
	if ( debuglevel > 1 )
	    std::cerr << "+" << _idcount << "\n";
} 

//-----------------------------------------------------------------
SPTNode::SPTNode( SPTNode *f, Edge *c ) 
//-----------------------------------------------------------------
{
    father = f;
    content = c;
    _refcount = 1;
    if( father != NULL ) {
	father->incRefCounter();
    }
    if ( ++_idcount % 1000000 == 0) 
	if ( debuglevel > 1 )
	    std::cerr << "+" << _idcount << "\n";
} // SPTNode


//-----------------------------------------------------------------
SPTNode::~SPTNode() 
//-----------------------------------------------------------------
{
    if( father != NULL ) {
	father->decRefCounter();
    }
    father=NULL;
    content=NULL;
} // ~SPTNode


/**
 * returns true iff neigher the input label nor the input to-vertex are
 * used on the path from this to the root of the SPT:
 */

//-----------------------------------------------------------------
bool SPTNode::isValidSPTPath( Edge *e )
//-----------------------------------------------------------------
{
    std::string label = e->getLabel();
    Vertex *target = e->to();
    
    SPTNode *sn = this;
    while ( sn != NULL ) {
	if ( sn->content == NULL ) {
	    std::cerr << "Error, SPTnode without content" << std::endl; exit(1);
	}
	if ( (sn->content->getLabel() == label ) 
	     || (sn->content->to() == target) ) {
	return false;
	}
	
	sn = sn->father;
    } // while
    
    return true;
    
} // isValidSPTPath


#ifdef UNIEDGES
/**
 * returns true iff neigher the input label nor the input to-vertex are
 * used on the path from this to the root of the SPT:
 */

//-----------------------------------------------------------------
bool SPTNode::isValidUniqueSPTPath( Edge *e )
//-----------------------------------------------------------------
{
    //std::cerr << "<" << *e;
    _S.clear();
    _S.push_front( e->getLabel() );
    bool r= this->isValidUniqueSPTPath( e->to());
    //std::cerr << r << ">";
    return r;
} // isValidUniqueSPTPath


//-----------------------------------------------------------------
bool SPTNode::isValidUniqueSPTPath( Vertex *target )
//-----------------------------------------------------------------
{
    //    for ( std::list<std::string>::iterator site = _S.begin();
    //	  site != _S.end(); site++ ) std::cerr << *site << ", ";
    // std::cerr << std::endl;
    
    if ( content == NULL ) {
	std::cerr << "Error, SPTnode without content" << std::endl; exit(1);
    }
    if ( content->from() == NULL ) 
	return true;

    Edge *e;
    for ( e = content->from()->getFirstUniEdge( content->to() ); 
	  e != NULL; e = e->getNext() ) {
	this->content = e;
	bool invalid = false; 
	if ( e->from() == target )
	    invalid = true;
	if ( ! invalid ) 
	    for ( std::list<std::string>::iterator site = _S.begin();
		  site != _S.end(); site++ ) {
		if ( *site == e->getLabel() ) {
		    invalid = true;
		    break;
		} // If
	    } // string iterator
	if ( ! invalid ) {
	    _S.push_front( e->getLabel() );
	    if ( father != NULL ) 
		invalid = !father->isValidUniqueSPTPath( target );
	    if ( _S.front() != e->getLabel() ) {
		std::cerr << "Weired things inside the string stack...\n";
		exit(1);
	    }
	    _S.pop_front();
	} // if ! valid
	if ( ! invalid )
	    return true;
    } // for
    return false;
} // isValidUniqueSPTPath
#endif


//-----------------------------------------------------------------
void SPTNode::incRefCounter()
//-----------------------------------------------------------------
{
    _refcount++;
} // incRefCounter


//-----------------------------------------------------------------
void SPTNode::decRefCounter()
//-----------------------------------------------------------------
{
    _refcount--;
    if( _refcount < 1 )
	delete this;
} // decRefCounter


//-----------------------------------------------------------------
void SPTNode::printOn( std::ostream &strm )
//-----------------------------------------------------------------
{
    int l = this->_printOnRec( strm );
    strm << " Length: " << l;
} // printOn


//-----------------------------------------------------------------
int SPTNode::getNumCount()
//-----------------------------------------------------------------
{
    return _idcount;
}


//-----------------------------------------------------------------
int SPTNode::_printOnRec( std::ostream &strm )
//-----------------------------------------------------------------
{
    int l = 0;
    if ( father != NULL ) {
	l = 1 + father->_printOnRec( strm );
	strm << " -";
	if ( content != NULL ) {
	    strm << content->getLabel() << "-> ";
	}
    }
    if ( content != NULL ) {
	strm << content->to()->getLabel();
    } 
    return l;
} // printOn


int SPTNode::_idcount = 0;

inline std::ostream& operator << (std::ostream &strm, SPTNode &v)
{ v.printOn(strm); return strm; }



//********************************************************************
//
// Edge Implementierung
//
//********************************************************************

//-----------------------------------------------------------------
Edge::Edge() 
//-----------------------------------------------------------------
{
#ifdef UNIEDGES
  _next = NULL;
#endif
} // Edge()

//-----------------------------------------------------------------
Edge::Edge( Vertex* f, Vertex* t, std::string l)
//-----------------------------------------------------------------
{ 
#ifdef UNIEDGES
  _next = NULL;
#endif
  _from = f;
  _to = t;
  _label = l;
} // Edge()


//-----------------------------------------------------------------
std::string Edge::getLabel()
//-----------------------------------------------------------------
{
  return _label;
} // getLabel


//-----------------------------------------------------------------
Vertex* Edge::from()
//-----------------------------------------------------------------
{
  return _from;
}

//-----------------------------------------------------------------
Vertex* Edge::to()
//-----------------------------------------------------------------
{
  return _to;
}

//-----------------------------------------------------------------
void Edge::printOn( std::ostream &strm )
//-----------------------------------------------------------------
{
  if ( _from != NULL ) strm << _from->getLabel();
  strm << " --" << _label << "--> ";
  if ( _to != NULL ) strm << _to->getLabel();
#ifdef UNIEDGES
  if ( _next != NULL ) strm << " + ";
#ifdef EBUG
  if ( _next != NULL ) strm << *_next;
#endif
#endif
} // printOn

#ifdef UNIEDGES
//-----------------------------------------------------------------
Edge* Edge::getNext()
//-----------------------------------------------------------------
{
  return _next;
} // getNext

//-----------------------------------------------------------------
void Edge::insert( Edge *e )
//-----------------------------------------------------------------
{ 
  if ( e->to() != _to ) {
    std::cerr << "Error: wrong target in insert\n"; exit(1);
  }
  if ( _next == NULL )  {
    e->_next = NULL;
    _next = e;
  } else {
    _next->insert( e );
  }
} // insert
#endif



//********************************************************************
//
// Main
//
//********************************************************************


// some global data structures; ugly, but convenient...
std::map <std::string, Vertex> nodes;

typedef std::map <std::string, Vertex>::iterator GraphIterator;


//-----------------------------------------------------------------
void printGraph( std::ostream &strm )
//-----------------------------------------------------------------
{
  GraphIterator it;
  for( it = nodes.begin(); it != nodes.end(); it++) {
    strm << it->second;
  } // for
} // printgraph

inline std::ostream& operator << (std::ostream &strm,  std::map <std::string, Vertex> &g)
{ printGraph( strm ); return strm; }


//-----------------------------------------------------------------
int printSPrec( Vertex *vp )
//-----------------------------------------------------------------
{
  int l = -1;
  if ( vp != NULL ) {
    l = 1 + printSPrec( vp-> getFather() );
    if ( vp-> getFather() != NULL ) {
      std::cout << " -" << vp->getEdgeLabel() << "-> ";
    }
    std::cout << vp->getLabel();
  }
  return l;
}  // printSPrec
    
//-----------------------------------------------------------------
int printSP( Vertex *vp )
//-----------------------------------------------------------------
{
  int l = printSPrec( vp );
  std::cout << " Length: " << l << std::endl;
  return l;
}  // printSP


//-----------------------------------------------------------------
void printSPshort( Vertex *vp )
//-----------------------------------------------------------------
{
  int l = 0;
  if ( vp != NULL ) {
    std::cout << "  To: " << vp->getLabel();
    while( vp != NULL ) {
      vp = vp->getFather();
      l++;
    } // while
    std::cout << "  Length: " << --l << std::endl;
  }
}  // printSPshort


//-----------------------------------------------------------------
void clearMarkers()
//-----------------------------------------------------------------
{
  GraphIterator it;
  for( it = nodes.begin(); it != nodes.end(); it++) {
    it->second.clearVisited();
    // it->second.isReported = false;
    it->second.setInEdge( NULL );
    it->second.pruned = 0;
  } // for
} // clearMarkers


//-----------------------------------------------------------------
void printGraphTest( Vertex *vp, std::string space )
//-----------------------------------------------------------------
{
  Vertex *v;
  std::cerr << space << vp->getLabel() << std::endl;
  if ( ! vp->isVisited() ) {
    vp->setVisited();
    vp->getFirstEdge();      
    while( vp->hasNextEdge() ) {
      v = vp->getNextEdge()->to();
      if ( v != NULL ) {
	printGraphTest( v, space + "   " );
      }
    }
  }
} // printGraphTest

//-----------------------------------------------------------------
void gpl()
//-----------------------------------------------------------------
{
std::cerr 
<< "Shortest paths with unique labels"  << std::endl
<< "Copyright (C) 2008 Tom Kamphans, Algorithms group, TU Braunschweig."
<< std::endl << std::endl 
<< "This program is free software: you can redistribute it and/or modify"
<< "it under the terms of the GNU General Public License as published by"
<< "the Free Software Foundation, version 3 of the License."
<< std::endl 
<< "This program is distributed in the hope that it will be useful,"
<< "but WITHOUT ANY WARRANTY; without even the implied warranty of"
<< "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the"
<< "GNU General Public License for more details."
<< std::endl 
<< "For a copy of the GNU General Public License"
<< "see <http://www.gnu.org/licenses/>." << std::endl;
}    

//-----------------------------------------------------------------
void usage()
//-----------------------------------------------------------------
{
  std::cerr << std::endl << "Usage:" << std::endl
	    << "sp [-c<n>] [-v] [-4] <filename> <startnode>  [<targetnode>]" 
	    << std::endl
	    << "-cn method for complete search (ignored if targetnode is given)" 
	    << std::endl
	    << "    -c0 no complete search" << std::endl
#ifdef UNIEDGES
	    << "    -c1 save memory (default)" << std::endl
#endif
#ifdef BFSCOMPL
	    << "    -c2 save time (small instances only!)" << std::endl
	    << "    -c3 both methods (not recommended...)" << std::endl
	    << "    -c4 search using backtracking (just for testing!)" << std::endl
#endif
    //	    << "-q quiet, less debug output" << std::endl
	    << "-b for testing: perform just a reachability test using BFS" << std::endl
	    << "-s for testing: skip preprocessing" << std::endl
	    << "-v verbose, more debug output" << std::endl
	    << "-4 four-column input (defaut: 3)" << std::endl
	    << std::endl << std::endl;
  exit(1);
} // usage




//-----------------------------------------------------------------
int main(int argc, char** argv) 
//-----------------------------------------------------------------
{
  //----------------------------------------------------------------------
  // Parse command line

  char *filename;

  while (--argc>0 && **++argv=='-') {
    switch(tolower(*++*argv)) {
    case 'q': debuglevel = -1; break;
    case 'v': debuglevel = 2; break;
    case 'm': debuglevel = 42; break;
    case '4': inputlevel = 4; break;
    case 'b': justbfs = 1; break;
    case 's': skippreproc = 1; break;
    case 'c': if ( !*(*argv +1 ) ) searchlevel = atoi(*++argv); 
	      else searchlevel = atoi(++*argv);
	      if ( searchlevel > 4 ) usage();
	      break;
    case 'l': gpl(); break;
    default: usage();
    } 
  } // while

  if ( debuglevel > -1 ) {
    std::cerr << "Shortest paths with unique labels"  << std::endl
    << "Copyright (C) 2008 Tom Kamphans, Algorithms group, TU Braunschweig."
	      << std::endl
	      << "This program comes with ABSOLUTELY NO WARRANTY."
	      << std::endl
	      << "This is free software, and you are welcome to redistribute it"
	      << std::endl
	      << "under certain conditions; type "
	      << argv[0] << " -l for details." << std::endl;
  }


  if ( debuglevel == 42 ) {
    std::cerr << "Int     " << sizeof( int     ) << "\n";
    std::cerr << "Pointer " << sizeof( int*    ) << "\n";
    std::cerr << "Vertex  " << sizeof( Vertex  ) << "\n";
    std::cerr << "Edge    " << sizeof( Edge    ) << "\n";
    std::cerr << "SPTNode " << sizeof( SPTNode ) << "\n";
    exit(1);
  }

  if ( (argc < 2) or (argc > 3) ) { 
    usage(); 
  }

  bool found;
  int currlen, maxlen=0;

  filename = *argv;
  std::string startnodeLabel( *++argv );

  std::ifstream inpfile( filename );

  std::time_t start, end;

  if ( ! inpfile.is_open() ) {
    std::cerr << "Error opening file " << filename << std::endl;
    exit(2);
  }

  //----------------------------------------------------------------------
  // Read file, build graph
  //
  // File format: one line for every edge
  // <start node>  <target node>  <label>  
  // or (with option -4)
  // <start node>  <target node>  <dummy>  <label>  

  if ( debuglevel > -1 ) {
    std::cerr << "------------------------------------------------------"
	      << std::endl;
    std::cerr << "Pass " << ++thepass << ": read graph" << std::endl;
    std::time( &start ); 
  }

  GraphIterator thenode, fromnode, tonode;
  std::string fs, ts, ls, ds;
  int numedges = 0;

  while ( ! inpfile.eof() ) {
      fs = "";
      std::string instr;
      std::getline(inpfile, instr);
      std::string::iterator endline(instr.end() - 1);
      if(*endline == '\r') instr.erase(endline);
      // std::cerr << instr << "\n";
      std::istringstream inp(instr);
      inp >> fs;
      if ( fs != "" ) { 
	if ( inp.eof() ) { std::cerr << "Broken file\n"; exit(2); }
	inp >> ts;
	if ( inp.eof() ) { std::cerr << "Broken file\n"; exit(2); }
	if ( inputlevel == 4 ) inp >> ds;
	if ( inp.eof() ) { std::cerr << "Broken file\n"; exit(2); }
	inp >> ls;
	if ( !inp.eof() ) { std::cerr << "Broken file, Line too long\n"; exit(2); }
	// std::cerr << "(" << f << ", " << t << ", " << l << ")\n";

	// lookup vertices:
	tonode = nodes.find( ts );
	if ( tonode == nodes.end() ) {
	  Vertex v( ts );
	  tonode = 
	    nodes.insert( tonode, std::pair<std::string, Vertex>(ts, v) );
	} // if tonode
	if ( tonode == nodes.end() ) {
	  std::cerr << "Error allocating vertex; " << ts; exit(1);
	}

	fromnode = nodes.find( fs );
	if ( fromnode == nodes.end() ) {
	  Vertex v( fs );
	  fromnode = 
	    nodes.insert( fromnode, std::pair<std::string, Vertex>(fs, v) );
	} // if fromnode
	if ( tonode == nodes.end() ) {
	  std::cerr << "Error allocating vertex; " << fs; exit(1);
	}

	// insert edge:
	Edge e( &(fromnode->second), &(tonode->second), ls);
	numedges++;
	fromnode->second.addEdge( e );
#ifdef BUSEARCH
	Edge ei( &(tonode->second), &(fromnode->second), ls);
	tonode->second.addInEdge( ei );
#endif
      } // if fs
  } // while eof

  inpfile.close();

  if ( debuglevel > -1 ) {
    std::cerr << "...Edges:    " << numedges  << std::endl;
    std::cerr << "...Vertices: " << nodes.size()  << std::endl;
    if ( debuglevel > 1 ) std::cerr << nodes;
  }

  Vertex *startnode;

  thenode = nodes.find( startnodeLabel );
  if ( thenode == nodes.end() ) { 
	  std::cerr << "Error start node not found\n"; exit(1); 
  }
  startnode = &(thenode->second);
  startnode->isReported = true;

  std::time( &end ); 

  if ( debuglevel > -1 ) {
    std::cerr << "Finished pass " << thepass 
	      << " in time " << std::difftime( end, start ) << std::endl;
  }

  //----------------------------------------------------------------------
  // Fill Todo-List with BFS
  if ( debuglevel > -1 ) {
    std::cerr << "------------------------------------------------------"
	      << std::endl;
    std::cerr << "Pass " << ++thepass 
	      << ": searching reachable vertices" << std::endl;
  }

  std::time( &start ); 

  std::queue < Vertex* > SQ;
  std::set < Vertex* > todo;
  std::set < Vertex* >::iterator thetodo;
  Vertex *v;
  Vertex *vp;

  SQ.push( startnode );

  while ( ! SQ.empty() ) {
    v =  SQ.front();
    EdgeIterator last = v->getEdgesEnd();
    EdgeIterator eit;
    // std::cerr << *v;
    for ( eit = v->getEdges(); eit != last; eit++ ){
      vp = eit->to();
      if ( !vp->isVisited() ) {
	vp->setVisited();
	SQ.push( vp );
	todo.insert( vp );
      } // if !visited
    } // for
    SQ.pop();
  } // while

  thetodo = todo.find( startnode );
  if ( thetodo != todo.end() ) {
    todo.erase( thetodo );
  }

  std::time( &end );

  if ( debuglevel > -1 ) {
    std::cerr << "Finished pass " << thepass 
	      << " in time " << std::difftime( end, start ) << std::endl
	      << "Reachable: " << todo.size() << std::endl;
  }

  if ( justbfs ) {
    exit( 0 );
  }

  // for ( thetodo = todo.begin(); thetodo != todo.end(); ++thetodo) 
  // std::cerr << (*thetodo)->getLabel() << ", ";
  // std::cerr << std::endl;

  clearMarkers();


  //----------------------------------------------------------------------
  // Test reachability (if parameter given)

  if ( argc == 3 ) {
    std::string targetnodeLabel( *++argv );
    thenode = nodes.find( targetnodeLabel );
    if ( thenode == nodes.end() ) { 
      std::cerr << "Error target node not found\n"; exit(1); 
    }
    Vertex* targetnode = &(thenode->second);

    thetodo = todo.find( targetnode );
    std::cout << "Valid path from " << startnode->getLabel()
	      << " to " << targetnode->getLabel();
    if ( thetodo != todo.end() )
      if ( startnode->isReachable( *thetodo ) ) {
	std::cout << " exists." << std::endl;
	exit( 0 );
      } 
    std::cout << " does not exist." << std::endl;
    exit(0);
  } // if argc


  //----------------------------------------------------------------------
  // Just for performance measuring: test reachability for all nodes

  if ( searchlevel == 4 ) {
    if ( debuglevel > -1 ) {
      std::cerr << "------------------------------------------------------"
		<< std::endl
		<< "Pass " << ++thepass 
		<< ": searching complete graph" << std::endl;
    }

    std::time( &start );
    for ( thetodo = todo.begin(); thetodo != todo.end(); ++thetodo)  {
      std::cerr << "Searching " << (*thetodo)->getLabel() << "... ";
      if ( startnode->isReachable( *thetodo ) ) {
	std::cout << " found" << std::endl;
	printSP( *thetodo );
      } else {
	std::cout << " not found" << std::endl;
      } 
      clearMarkers();
    } // for
    
    std::time( &end ); 

    if ( debuglevel > -1 ) {
      std::cerr << "Finished pass " << thepass
		<< " in time " << std::difftime( end, start ) << std::endl
		<< std::endl;
    }

    exit( 0 );

  } // searchlevel


#ifdef BFS

  //----------------------------------------------------------------------
  // BFS
  if ( skippreproc == 0 ) {

    if ( debuglevel > -1 ) {
      std::cerr << "------------------------------------------------------"
		<< std::endl
		<< "Pass " << ++thepass 
		<< ": traversing graph" << std::endl;
    }
    
    std::time( &start );

    SQ.push( startnode );

    while ( ! SQ.empty() ) {
      v =  SQ.front();
      EdgeIterator last = v->getEdgesEnd();
      EdgeIterator eit;
      // std::cerr << *v;
      for ( eit = v->getEdges(); eit != last; eit++ ){
	vp = eit->to();
	if ( (vp->getFather() == NULL) && ( vp != startnode )) {
	  if ( v->isLabelValidPath( eit->getLabel() )) {
	    vp->setInEdge( &*eit );
	    SQ.push( vp );
	    if ( ! vp->isReported ) {
	      thetodo = todo.find( vp );
	      if ( thetodo == todo.end() ) {
		std::cerr << "Weired things inside the todo-list...\n";
	      } else {
		todo.erase( thetodo );
	      }
	      vp->isReported = true;
	      currlen = printSP( vp );
	      if ( maxlen < currlen ) maxlen = currlen;
	      // printSPshort( vp );
	    } // if !isReported
	  } // isValid ... else 
	} // if getFather
      } // for
      
      SQ.pop();
      
    } // while

    std::time( &end ); 

    if ( debuglevel > -1 ) {
      std::cerr << "Finished pass " << thepass
		<< " in time " << std::difftime( end, start ) << std::endl
		<< "Todo: " << todo.size()
		<< ", max length: " << maxlen
		<< std::endl;
    }

  } // if skip
  
  clearMarkers();

#endif


#ifdef RBFS

  //----------------------------------------------------------------------
  // BFS reverse order

  if ( skippreproc == 0 ) {
    if ( debuglevel > -1 ) {
      std::cerr << "------------------------------------------------------"
		<< std::endl
		<< "Pass " << ++thepass 
		<< ": traversing graph in reverse order" << std::endl;
    }

    std::time( &start ); 

    SQ.push( startnode );

    while ( ! SQ.empty() ) {
      v =  SQ.front();
      RevEdgeIterator rlast = v->getRevEdgesEnd();
      RevEdgeIterator reit;
      // std::cerr << *v;
      for ( reit = v->getRevEdges(); reit != rlast; reit++ ){
	vp = reit->to();
	if ( (vp->getFather() == NULL) && ( vp != startnode )) {
	  if ( v->isLabelValidPath( reit->getLabel() )) {
	    vp->setInEdge( &*reit );
	    SQ.push( vp );
	    if ( ! vp->isReported ) {
	      thetodo = todo.find( vp );
	      if ( thetodo == todo.end() ) {
		std::cerr << "Weired things inside the todo-list...\n";
	      } else {
		todo.erase( thetodo );
	      }
	      vp->isReported = true;
	      printSP( vp );
	      // printSPshort( vp );
	    } // if !isReported
	  } // isValid ... else 
	} // if getFather
      } // for
      
      SQ.pop();

    } // while

    std::time( &end );

    if ( debuglevel > -1 ) {
      std::cerr << "Finished pass " << thepass
		<< " in time " << std::difftime( end, start ) << std::endl
		<< "Todo: " << todo.size() << std::endl;
    }
    
    clearMarkers();
  } // if skip

#endif



  //----------------------------------------------------------------------
  // BFS starting from unvisited nodes

#ifdef BUSEARCH
  if ( skippreproc == 0 ) {
      
    if ( debuglevel > -1 ) {
      std::cerr << "------------------------------------------------------"
		<< std::endl
		<< "Pass " << ++thepass
		<< ": bottom up" << std::endl;
    }

    std::time( &start ); 

    for ( thetodo = todo.begin(); thetodo != todo.end(); ++thetodo)  {
      SQ.push( *thetodo );
      // std::cerr << "Searching for " << (*thetodo)->getLabel() << std::endl;
      found = false;
      while ( ! ( SQ.empty() || found )) {
	v =  SQ.front();
	EdgeIterator last = v->getInEdgesEnd();
	EdgeIterator eit;
	//std::cerr << *v;
	for ( eit = v->getInEdges(); eit != last; eit++ ){
	  vp = eit->to();
	  if ( (vp->getFather() == NULL) && ( vp !=  *thetodo )) {
	    if ( v->isLabelValidPath( eit->getLabel() )) {
	      vp->setInEdge( &*eit );
	      SQ.push( vp );
	      if ( vp == startnode ) {
		(*thetodo)->isReported = true;
		printSP( *thetodo );
		todo.erase( thetodo );
		found = true;
		// printSPshort( vp );
	      } // if startnode
	    } // isValid
	  } // if getFather
	} // for
	SQ.pop();
      } // while
    } // for thetodo
    
    std::time( &end );

    if ( debuglevel > -1 ) {
      std::cerr << "Finished pass " << thepass
		<< " in time " << std::difftime( end, start ) << std::endl
		<< "Todo: " << todo.size() << std::endl;
    }

  } // if skip

  clearMarkers();

#endif

  Edge startedge( NULL, startnode, std::string("") );
  SPTNode startspt( NULL, &startedge );

  startspt.incRefCounter();
  startspt.incRefCounter();

  //----------------------------------------------------------------------
  // Complete BFS using unique labels

#ifdef UNIEDGES
if ( (searchlevel % 2) == 1 ) {

  if ( debuglevel > -1 ) {
    std::cerr << "------------------------------------------------------"
	      << std::endl
	      << "Pass " << ++thepass 
	      << ": complete search (memory conserving method)" << std::endl;
  }

  std::time( &start );

  std::queue < SPTNode* > UQ;
  SPTNode *usptn;
  
  UQ.push( &startspt );

  while ( ! ( UQ.empty() || todo.empty()) ) {
    usptn = UQ.front(); 
    usptn->decRefCounter();
    UQ.pop();

    if ( usptn == NULL ) { std::cerr << "Error on SPT"; exit(0); }
    if ( usptn->content == NULL ) { std::cerr << "Error on SPT edge"; exit(0); }

    v =  usptn->content->to();
    found = false;

    for ( EdgeIterator eit = v->getUniEdges(); 
	  eit != v->getUniEdgesEnd(); eit++ ) {
      if ( usptn->isValidUniqueSPTPath( &*eit )) {	
	vp = eit->to();
	SPTNode *sn = new SPTNode( usptn, &*eit );
	UQ.push( sn ); 
	sn->incRefCounter();
	found = true;
	
	if ( ! vp->isReported ) {
	  thetodo = todo.find( vp );
	  if ( thetodo == todo.end() ) {
	    std::cerr << "Weired things inside the todo-list...\n";
	  } else {
	    todo.erase( thetodo );
	    if ( debuglevel > -1 ) {
	      std::cerr << "Found " << vp->getLabel()
			<< " Todo: " << todo.size() << std::endl;
	    }
	  }
	  vp->isReported = true;
	  std::cout << *sn << std::endl;	    
	  // printSPshort( vp );
	} // if reported
      } // if isValid
    } // for
    if( !found ) 
      usptn->decRefCounter();
    
  } // while

  std::time( &end );

  if ( debuglevel > -1 ) {
    std::cerr << "Finished pass " << thepass
	      << " in time " << std::difftime( end, start ) << std::endl;
  }
}
#endif


  //----------------------------------------------------------------------
  // Complete search

#ifdef BFSCOMPL
if ( searchlevel > 1 ) {
  if ( debuglevel > -1 ) {
    std::cerr << "------------------------------------------------------"
	      << std::endl
	      << "Pass " << ++thepass 
	      << ": complete search" << std::endl;
  }

  std::time( &start ); 

  std::queue < SPTNode* > Q;
  SPTNode *sptn;
  
  Q.push( &startspt );

  while ( ! ( Q.empty() || todo.empty()) ) {
    sptn = Q.front(); 
    sptn->decRefCounter();
    Q.pop();

      if ( sptn == NULL ) { std::cerr << "Error on SPT"; exit(0); }
      if ( sptn->content == NULL ) { std::cerr << "Error on SPT edge"; exit(0); }
      v =  sptn->content->to();

      EdgeIterator last = v->getEdgesEnd();
      EdgeIterator eit;

      found = false;
      for ( eit = v->getEdges(); eit != last; eit++ ){
	if ( sptn->isValidSPTPath( &*eit )) {	  
	  vp = eit->to();
	  SPTNode *sn = new SPTNode( sptn, &*eit );

	  Q.push( sn ); 
	  sn->incRefCounter();
	  found = true;

	  // Target found???
	  if ( ! vp->isReported ) {
	    thetodo = todo.find( vp );
	    if ( thetodo == todo.end() ) {
	      std::cerr << "Weired things inside the todo-list...\n";
	    } else {
	      todo.erase( thetodo );
	      if ( debuglevel > -1 ) {
		std::cerr << "Found " << vp->getLabel()
			  << " Todo: " << todo.size() << std::endl;
	      }
	    }
	    vp->isReported = true;
	    std::cout << *sn << std::endl;	    
	    // printSPshort( vp );
	  } // if reported
	} // if isValid
      } // for
      if( !found ) 
	sptn->decRefCounter();

    } // while

  std::time( &end );

  if ( debuglevel > -1 ) {
    std::cerr << "Finished pass " << thepass
	      << " in time " << std::difftime( end, start )
	      << std::endl;
  }

 }
#endif

  if ( debuglevel > -1 ) {
    std::cerr << "------------------------------------------------------"
	      << std::endl;

    std::cerr << "Todo-List: " << std::endl;
    for ( thetodo = todo.begin(); thetodo != todo.end(); ++thetodo) 
      std::cerr << (*thetodo )->getLabel() << ", ";
    std::cerr << std::endl;

    std::cerr << "------------------------------------------------------"
	    << std::endl;

    std::cerr << "Unvisited vertices: " << std::endl;
    GraphIterator git;
    for( git = nodes.begin(); git != nodes.end(); git++) 
      if ( ! git->second.isReported ) 
	std::cerr << git->second.getLabel() << ", ";
    std::cerr << std::endl;
  } else {
    std::cerr << SPTNode::getNumCount() * sizeof( SPTNode ) << std::endl;
  }

  return 0;

}


//time for k in `cat Knoten_uurMa.txt`; do ./sp Uur_oldDBMa.txt $k> /dev/null 2>&1; done