/* Copyright (c) 1997-2005
   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: 1D_tools.tcc 6357 2005-09-22 17:12:12Z gawrilow $"

#include <ext/hash_map>
#include <Bitset.h>

namespace polymake { namespace topaz {

template <typename Complex>
bool C1_is_BOS (const Complex& C)
{
   DIMENSION_CHECK(C.empty(), "C1_is_BOS: Complex is empty.");
   
   // compute the vertex set and test whether C is a pure 1-complex
   Set<int> V;
   for (typename Entire<Complex>::const_iterator c_it=entire(C); !c_it.at_end(); ++c_it) {
      V += *c_it;
      DIMENSION_CHECK_WRAP(c_it->size()>2, "C1_is_BOS: Dimension of " << *c_it << " is greater 1.");
      
      if (c_it->size()!=2)  // complex is not pure
	 return false;
   }
   
   // compute the vertex_map
   const int n_vert=V.size();
   std_ext::hash_map<int, int> vertex_map(n_vert);
   int count=0;
   for (Entire< Set<int> >::iterator it=entire(V); !it.at_end(); ++it, ++count)
      vertex_map[*it]=count;
   
   // compute the adjacency lists
   Array< std::list<int> > adj_lists(n_vert);
   for (typename Entire<Complex>::const_iterator c_it=entire(C); !c_it.at_end(); ++c_it) {
      int x= vertex_map[ c_it->front() ],  y= vertex_map[ c_it->back() ];
      adj_lists[x].push_back(y);
      adj_lists[y].push_back(x);
   }
   
   // search the graph:
   // 1) connected; 2) degree(v)<3 all v in V; 3) #{v|degree(v)=1} =: n_leafs equals 0 or 2
   int n_leafs=0;
   Bitset visited(n_vert);
   std::list<int> node_queue;
   
   node_queue.push_back(0);
   visited+=0;
   
   while (!node_queue.empty()) {
      const int n=node_queue.front();      // remove first node from the queue
      node_queue.pop_front();
      
      if (adj_lists[n].size()>2)           // testing degree(v)<3 all v in V
	 return false;
      
      n_leafs= adj_lists[n].size()==1 ? n_leafs+1 : n_leafs;   // counting n_leafs
      if (n_leafs>3) {                                         // testing  n_leafs < 3
	 //       cout << "C1_is_BOS: Graph has more than two leafs." << endl;
	 return false;
      }
      
      // check the neighbours of
      for (typename Entire< std::list<int> >::iterator it=entire(adj_lists[n]); !it.at_end(); ++it) {
	 const int nn=*it;
	 if (!visited.contains(nn)) {                // nn not been visited yet -> add nn to the queue
	    visited+=nn;
	    node_queue.push_back(nn);
	 }
      }  
   }  // end while
   
   for (int i=0; i<n_vert; ++i)           // testing connected
      if (!visited.contains(i)) {
	 //	cout << "C1_is_BOS: Graph is not connected: " << i << " has not been visited." << endl;
	 return false;
      }
   
   if (n_leafs==1) {                       // testing n_leafs equals 0 or 2  <=>  n_leafs<3 && n_leafs!=1
      //     cout << "C1_is_BOS: Graph has one leaf only." << endl;
      return false;
   }
   
   return true;
}
   
template <typename Complex>
bool C1_is_manifold (const Complex& C)
{
   DIMENSION_CHECK(C.empty(), "C1_is_manifold: Complex is empty.");

  // compute the vertex set and test whether C is a pure 1-complex
  Set<int> V;
  for (typename Entire<Complex>::const_iterator c_it=entire(C); !c_it.at_end(); ++c_it) {
    V+=*c_it;
    DIMENSION_CHECK_WRAP(c_it->size()>2, "C1_is_manifold: Dimension of " << *c_it << " is greater 1.");
    
    if (c_it->size()!=2) { // complex is not pure
       //       cout << "C1_is_manifold: Complex is not PURE." << endl;
       return false;
    }
  }

  // compute the vertex_map
  const int n_vert=V.size();
  std_ext::hash_map<int, int> vertex_map(n_vert);
  int count=0;
  for (Entire< Set<int> >::iterator it=entire(V); !it.at_end(); ++it, ++count)
    vertex_map[*it]=count;

  // check whether each vertex is contained in 1 or 2 edges
  Array<int> vert_degree(n_vert);
  for (typename Entire<Complex>::const_iterator c_it=entire(C); !c_it.at_end(); ++c_it) {
     ++vert_degree[ vertex_map[c_it->front()] ];
     ++vert_degree[ vertex_map[c_it->back()] ];
     if ( vert_degree[ vertex_map[c_it->front()] ] > 2 || vert_degree[ vertex_map[c_it->back()] ] > 2 ) {
	//	cout << "C1_is_manifold: Vertex degree > 2 found" << endl;
	return false;
     }
  }
  
  return true;
}

} }

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