/* dep_remove.h */

#ifndef DEP_REMOVE__H
#define DEP_REMOVE__H

#include "tag.h"
#include <LEDA/list.h>

/* DEPENDANCY REMOVAL ALG
   dependencies are passed in a dep_list, a list of tag pairs.
   
   POSSIBLE ALGS
   remove_dependencies
   -------------------
   dump edges and nodes into graph with bool at each node set to false
   for each node i {
     for each edge i->j from node {
       if node[j] is true {
         remove edge i->j
	 set all nodes[0...n-1] to false;
	 start over
       } else {
         node[j] = true;
       }
     }
   }
   
   counts number n of unique tags and assigns each an index.
   creates 2 nxn boolean matrices. matrix 1, 2
   reads dependencies into matrix.
     matrix[i][j] true iff there is a dependency from tag index i to tag index j
   while( progress is made ) {
     for each row j {
       for each column i {
         if( matrix1[i][j] ) {
	   matrix2[i][j] = true
	 }
	 for each column k {
	   matrix2[k][j] |= matrix1[k][i]
	   if( k == j ) {
	      remove dependency from j to i
	      start over from scratch
   } } } } }

   or

   put all dep_pair's in a graph.
   compute maximum spanning tree.
   remove difference.
 */

/* list of pairs of tags ( from, to ) */
typedef list<tag> dep_list;

/* returns number of dependencies to remove */
int remove_dependencies( const dep_list &dependencies, dep_list &to_remove );

/* description string for a tag used to print out dep file */
string tag_descrip( tag ); /* defined in display.cc */

#endif
