1 /***************************************************************************
2  *   Copyright (C) 2006 by BUI Quang Minh, Steffen Klaere, Arndt von Haeseler   *
3  *   minh.bui@univie.ac.at   *
4  *                                                                         *
5  *   This program is free software; you can redistribute it and/or modify  *
6  *   it under the terms of the GNU General Public License as published by  *
7  *   the Free Software Foundation; either version 2 of the License, or     *
8  *   (at your option) any later version.                                   *
9  *                                                                         *
10  *   This program is distributed in the hope that it will be useful,       *
11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
13  *   GNU General Public License for more details.                          *
14  *                                                                         *
15  *   You should have received a copy of the GNU General Public License     *
16  *   along with this program; if not, write to the                         *
17  *   Free Software Foundation, Inc.,                                       *
18  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
19  ***************************************************************************/
20 #ifndef GREEDY_H
21 #define GREEDY_H
22 
23 #include "pdtree.h"
24 
25 /**
26 Implementation of greedy algorithm with complexity O(n*logk)
27 @author BUI Quang Minh, Steffen Klaere, Arndt von Haeseler
28 */
29 class Greedy : public PDTree
30 {
31 public:
32 	/**
33 		construct from program parameters
34 		@param params program parameters
35 	*/
Greedy(Params & params)36     Greedy(Params &params) :
37 		PDTree(params) {}
38 
39 	/**
40 		construct from a tree
41 		@param tree a tree class
42 	*/
Greedy(PDTree & tree)43     Greedy(PDTree &tree) :
44 		PDTree(tree) {}
45 
46 	/**
47 		constructor
48 	*/
Greedy()49 	Greedy() : PDTree() {};
50 
51 	/**
52 		run the algorithm
53 		@param params program parameters
54 		@param taxa_set (OUT) vector of PD sets
55 	*/
56 	void run(Params &params, vector<PDTaxaSet> &taxa_set);
57 
58 	/**
59 		update the ordered list based on the recent longest path
60 		@param node the starting node
61 		@param subtree (OUT) resulted subtree
62 		@param cur_set the current set
63 	*/
64 	void updateOnLongestPath(Node *node, NodeVector &subtree, PDTaxaSet &cur_set);
65 
66 	/**
67 		build the initial subtree based on the initial set of taxa
68 		@param node the starting node, NULL to start from the root
69 		@param dad dad of the node, used to direct the search
70 		@param subtree (OUT) resulted subtree
71 		@param nodestack (TEMP) stack of node, used only by function
72 	*/
73 	void buildOnInitialSet(NodeVector &subtree, NodeVector &nodestack, Node *node = NULL, Node *dad = NULL);
74 
75 	/**
76 		initialize the ordered list based on the initial subtree structure
77 		@param subtree vector containing nodes in the subtree
78 		@return the subtree length
79 	*/
80 	double updateOnInitialSet(NodeVector &subtree);
81 
82 	/**
83 		@return innodes.begin().
84 	*/
85 	NeighborSet::iterator highestNeighbor();
86 
87 	/**
88 		add an edge into the NeighborSet
89 	*/
90 	void addNeighbor(Neighbor* neigh);
91 
92 	//NodeSet innodes;
93 
94 	/**
95 		neighbor set
96 	*/
97 	NeighborSet neighset;
98 
99 	/**
100 		list of nodes in the subtree
101 	*/
102 	NodeVector subtree;
103 
104 private:
105 
106 	/**
107 		size of list of nodes, used internally during greedy search
108 	*/
109 	int list_size;
110 };
111 
112 #endif
113