EXTERNAL LOOP: ~~~~~~~~~~~~~ IF --besttree, --bestsimple or --bestgreedy specified THEN let N be the best network obtained by the relevant subroutine ELSE let N be the result of running the MAIN ALGORITHM. ENDIF - Compute stats for N, display some pre post-processing results - Mild post-processing on N, unless all post-processing switched off. (This involves repeatedly contracting edges with neither endpoint a reticulation, where this does not damage triplet consistency) - Radical post-processing of N, but ONLY if radical post-processing switched on (and post-processing has not been totally disabled). This involves executing the following loop: SD-min loop: Keep deleting edges until that doesn't reduce SD anymore Keep contracting edges until that doesn't reduce SD anymore Go back to Loop for as long as something is deleted or contracted - List surplus/missing triplets if the user has requested this information - Display final network (DOT/eNewick) - Print final stats FINISHED ----------------------------------------------------------------------------------------------- The MAIN ALGORITHM consists of running the following MAIN LOOP until we are finished. The high-level description of the MAIN LOOP is: { try Aho, if that fails try the polytime J&S algorithm, if that fails then use the J&S "5/12" scoring function. Compute a good simple level-1 network for the triplets induced by the partition, and (if possible) a good tree, if the tree is better use the tree, otherwise use the simple level-1 network }. MAIN LOOP: 1) CHOOSE THE PARTITION ----------------------- - IF --forcemaxsn is TRUE, use the max SN-sets as a partition, DONE; ELSE IF Aho graph is not connected THEN return a 2-block partition where one of the blocks is equal to one of the connected components in the Aho graph, and the other is equal to the remaining leaves, DONE ELSE IF we are allowed to look for local perfection (i.e. --noperfection is false) THEN look at the max SN-sets of the set: if they form a genuine partition of the leaves -and- the induced set of triplets is dense -and- they are 100% consistent with some level-1 network -then- we found local perfection: use the max SN-sets as the partition! DONE ELSE Use the J&S "5/12" scoring function to choose a partition (up to the maximum number of blocks allowed), DONE 2) DECIDE WHAT TO DO WITH THE PARTITION --------------------------------------- - IF the partition contains only two blocks, then we're done because we introduce a tree vertex (i.e. indegree 1, outdegree 2) and we recurse inside the blocks ELSE - Induce a set of triplets on the partition - IF we were allowed to look for local perfection and we found it THEN introduce a simple level-1 network (constructed using the J&S algorithm) consistent with 100% of the induced triplets, and recurse inside the blocks, done ELSE - IF the number of leaves in the induced triplet set is not above the --simmax thresshold THEN use the exponential-time best simple level-1 algorithm ELSE use the greedy simple level-1 algorithm - IF the number of leaves in the induced triplet set is not above the --wumax threshhold, THEN use Wu's exponential-time algorithm to get the best Introduce the computed simple level-1 network UNLESS we also ran Wu's algorithm and it was better than the computed simple level-1 algorithm. Recurse inside the blocks, DONE.