/*
 * File:   tspsolver.cc
 * Author: Filip Niksic, fniksic@gmail.com
 *
 * Created on 2008. veljaca 08, 01:08
 */

#include <cassert>
#include <iostream>

#include "graph.h"
#include "tspsolver.h"
#include "branch.h"

using namespace std;

void TSPSolver::branchAndBound(Branch *branch) {
    assert(branch != 0);
//    if (branch->getLowerBound() < bestTour) {
        if (branch->isTourFound()) {
            delete best;
            best = new Branch(*branch);
            bestTour = branch->getLowerBound();
//            cout << "Found new best tour. Cost: " << bestTour / 2.0 << endl;
        }
        else /*if (!branch->isContradiction())*/ {
            Graph::Edge_ID e = branch->nextAllowedEdge();
            if (e == Graph::nullEdge)
                return;
            Branch *left = new Branch(*branch);
            Branch *right = new Branch(*branch);
            left->requireEdge(e);
            right->disallowEdge(e);
            if (left->getLowerBound() > right->getLowerBound()) {
                Branch *tmp = left;
                left = right;
                right = tmp;
            }
            // Radije na ovom mjestu provjerim jesu li uvjeti zadovoljeni, nego da
            // otkomentiram gore zakomentirane linije i pustim da uvjeti budu provjereni
            // nakon sto se udje u sljedeci nivo rekurzije.
            if (!left->isContradiction() && left->getLowerBound() < bestTour)
                branchAndBound(left);
            delete left; left = 0;
            if (!right->isContradiction() && right->getLowerBound() < bestTour)
                branchAndBound(right);
            delete right; right = 0;
        }
//        else
//            ;
//    }
}