/*
 * File:   branch.h
 * Author: Filip Niksic, fniksic@gmail.com
 *
 * Created on 2008. sijecanj 31, 15:03
 */

#ifndef BRANCH_H
#define	BRANCH_H

#include <vector>
#include <cstddef>
#include <cassert>

#include "globals.h"
#include "graph.h"
#include "partition.h"

class Branch {
public:
    enum EdgeConstraint_T { ALLOWED, REQUIRED, DISALLOWED };
    typedef Graph::Vertex_ID Vertex_ID;
    typedef Graph::Edge_ID Edge_ID;
private:
    std::size_t size;
    Graph g;
    std::vector<std::vector<EdgeConstraint_T> > constraints;
    Real_T lowerBound;
    
    std::vector<std::size_t> numRequired;
    std::vector<std::size_t> numAllowed;
    
    bool tourFound;
    bool contradiction;
    
    // Partition p nam modelira particiju skupa vrhova. Inicijalno je svaki vrh u
    // svom skupu. Kako povezujemo vrhove bridovima, spajat cemo skupove u kojima
    // se oni nalaze. Povezivanje dva vrha iz istog skupa ekvivalentno je zatvaranju
    // ciklusa. To cemo dozvoliti samo ako se radi o Hamiltonovom ciklusu.
    Partition p;
public:
    explicit Branch(const Graph &_g);
    Edge_ID nextAllowedEdge(Edge_ID e) const;
    Edge_ID nextAllowedEdge() const {
        return nextAllowedEdge(Edge_ID(0, 0));
    }
    void disallowEdge(Edge_ID e);
    void requireEdge(Edge_ID e);
    bool isTourFound() const {
        return tourFound && !contradiction;
    }
    bool isContradiction() const {
        return contradiction;
    }
    Real_T getLowerBound() const {
        return lowerBound;
    }
    // getTour() vraca vektor vrhova u kojem je na mjestu i zapisan sljedbenik od i u turi.
    std::vector<Vertex_ID> getTour() const;
private:
    // setConstraint je privatna jer zelim dozvoliti korisniku jedino da brid koji je
    // ALLOWED ucini REQUIRED ili DISALLOWED. Za to su predvidjene public metode.
    void setConstraint(Edge_ID e, EdgeConstraint_T c) {
        assert(constraints[e.first][e.second] == ALLOWED && c != ALLOWED);
        constraints[e.first][e.second] = constraints[e.second][e.first] = c;
        --numAllowed[e.first];
        if (e.first != e.second) --numAllowed[e.second];
        if (c == REQUIRED) {
            ++numRequired[e.first];
            if (e.first != e.second) ++numRequired[e.second];
        }
    }
    // Promjena constrainta nekog brida za posljedicu moze imati da neki bridovi moraju
    // postati REQUIRED ili DISALLOWED. Npr. svi osim dva brida incidentnih s nekim vrhom su
    // DISALLOWED -- u tom slucaju ta dva brida postaju REQUIRED. Ili, npr. dva brida incidentna
    // s nekim vrhom vec jesu REQUIRED -- ostali bridovi moraju postati DISALLOWED.
    // Moguce su i kontradiktorne situacije, u tom slucaju:
    // TODO: u Branch dodati flag koji oznacava kontradiktornu situaciju
    void setImpliedConstraints();
    void setInitialConstraints();
    bool closesCycle(Edge_ID e) const;
    void computeLowerBound();
    void printConstraints() const;
    void printNums() const;
};

inline bool Branch::closesCycle(Edge_ID e) const {
    // Ukoliko se krajevi nalaze u istom skupu, bridom e bismo zatvorili ciklus.
    if (p.find(e.first) == p.find(e.second))
        return true;
    else
        return false;
}

#endif	/* BRANCH_H */