/*
This file implements functions to compute a DCM3 decomposition.
Copyright (C) 2004 The University of Texas at Austin

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 of the License, or (at your option)
any later version.

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.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Email: usman@cs.njit.edu
Mail: Usman Roshan, Department of Computer Sciences, NJIT-CCS, Computer
Science Department, GITC 4400, University Heights, Newark, NJ 07102
*/

/*! \file dcm3.h
\brief Contains functions to find the centroid edge of a tree and to compute
the DCM3 subsets.
*/

#include<constants.h>
#include<phylo_tree.h>
#include<ugraph.h>

/*!\brief Returns the centroid edge of the given phylogenetic_tree in linear time
and linear space

The centroid edge is defined to be the edge such that its removal partitions 
the leaves of T into sets of equal size (or as close to equal as possible).
T is read in as a rooted tree and each node contains the number 
of leaves below it. This function iterates over the nodes of T to find the node
which has half the number of leaves below it (or closest to half) and then returns
the corresponding adjacent edge as the centroid edge.
*/
edge get_centroid_edge(phylogenetic_tree T);

/*!\brief Returns the DCM3 subproblems associated with the edge c_edge on the guide tree T
in linear time and linear space

\param T The phylogenetic guide-tree 
\param c_edge The centroid edge of T
\param subsets An integer array of size num_leaves with the space already allocated
\param subsets_ An integer array of size num_leaves with the space already allocated
\param separator An integer array of size num_leaves with the space already allocated
\param subset_num A pointer to an integer with space already allocated

The taxa are represented as integers by giving them unique taxon ids. The
array variable called subsets contains the subproblems (minus the separator) 
and the array variable called subsets_ tells us how when a 
subproblem has ended and the next one begins. The subproblems are arranged as follows:

<ul>
<li>first subset : start from subsets[0] and ends at subsets[subsets_[1]-1]
<li>second subset: starts from subsets[subsets_[1]] and ends at subsets[subsets_[2]-1]
<li>kth subset   : starts from subsets[subsets_[subset_num-2] and ends at subsets[subsets_[subset_num-1]-1]
</ul>

The variable subset_num points an integer which represents the number of computed subsets 
+ 1. The array variable called separator contains the DCM3 separator. The entries begin
from separator[0] and end at the first index i for which separator[i] = -1
*/
void get_dcm3_subsets(phylogenetic_tree T, edge c_edge, int* subsets, int* subsets_,
		      int* separator, int* subset_num);

/*!\brief NOT TO BE CALLED BY USER: auxillary function used by get_dcm3_subsets*/
void get_dcm3_subsets_rec(phylogenetic_tree T, node root, edge p_e, int* subsets,
			    int* separator, int* subsets_i, int* separator_i,
			    int start_sep, double cur_dist, double* shortest_dist);