/* Copyright (c) 1997-2004
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   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; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   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.
*/

#ident "$Project: polymake $$Id: orientation.tcc 6152 2005-06-07 08:19:46Z wotzlaw $"

#include <Poly.h>
#include <Set.h>
#include <Array.h>
#include <Graph.h>
#include <FacetList.h>

#include <list>
#include <ext/hash_map>

namespace polymake {
namespace topaz {

namespace {

bool consistent(const int f1, const int f2, const int o1, const int o2,
		const Array< Set<int> >& F,
		const Array< std_ext::hash_map<int,int> >& indices)
{
    const int n1 =indices[f1].find( (F[f1]-F[f2]).front() )->second;
    const int n2 =indices[f2].find( (F[f2]-F[f1]).front() )->second;
    
    return o1==o2 ? (n1-n2)%2!=0 : (n1-n2)%2==0;
}
    
}

Array<int> orientation(const Array< Set<int> >& F, const Graph<> DG)
{
    
    // compute indices of the vertices for each facet
    Array< std_ext::hash_map<int,int> > indices(F.size());
    int count1=0;
    for (Entire< Array<Set<int> > >::const_iterator f=entire(F);
	 !f.at_end(); ++f, ++count1) 
    {
	
	int count2=0;
	for (Entire< Set<int> >::const_iterator v=entire(*f);
	     !v.at_end(); ++v, ++count2)
	    indices[count1][*v] = count2;
    }
    
    Array<int> orientation(F.size());  // 0 for not visited
    orientation[0] = 1;
    std::list<int> node_queue;
    node_queue.push_back(0);
    bool orientable = true;
    
    while (!node_queue.empty() && orientable) {
	const int n=node_queue.front();
	node_queue.pop_front();
	
	for (Entire< Graph<>::out_edge_list >::const_iterator e=entire(DG.out_edges(n));
	     !e.at_end(); ++e) 
	{
	    const int nn=e.to_node();
	    
	    if (orientation[nn]==0) 
	    {  // nn not been visited yet, compute orientation
		orientation[nn]= consistent(n,nn,orientation[n],1,F,indices) ? 1 : -1;
		node_queue.push_back(nn);
		
	    } else  // check consistency of orientation
		if ( n<nn && !consistent(n,nn,orientation[n],orientation[nn],F,indices) ) 
		{
		    orientable = false;
		    break;
		}
	}	
    }

    return orientation;
}

}
}
    
// Local Variables:
// mode:C++
// c-basic-offset:3
// End: