Finding Sophie

#include "stdlib.h"
#include "stdio.h"
#include "time.h"

#include <iostream>
#include <fstream>

#include <map>
#include <string>
#include <vector>

using namespace std;

class Node
{

public:

    Node() : m_id(0), m_Probability(0), m_InUse(0) {}

    Node(int id, double probability) : m_id(id), m_Probability(probability), m_InUse(0) {}

    bool    isInUse()        const { return m_InUse; }
    int     getID()          const { return m_id; }
    double  getProbability() const { return m_Probability; }

    void setInUse(const bool& inUse) { m_InUse = inUse; }

    bool operator<(const Node& node) const
    {
        return m_id < node.getID();
    }

protected:

    int    m_id;
    bool   m_InUse;
    double m_Probability;
};

class Graph
{
public:
    // public for simplicity and speed
    // should be careful with malloc
    int      NodeCount;
    double** Weight;

public:
    Graph() : NodeCount(0), Weight(0), m_CurrentMin(-1) {}
    ~Graph() { cleanUp(); }

    void cleanUp();
    void read_graph(char* file);
    void split_string(string text, vector<string>& words);
    void run_floyd();
    bool isConnected();

    double permutate(double probability, double expectation, double time, Node* currNode)
    {
        if (m_Nodes.size() < 2)
        {
            if (m_Nodes.size() == 0)
            {
                return - 1;
            }
            else
            {
                return 0;
            }
        }

        if (!currNode)
        {
            currNode = m_Nodes[0];
            probability = 1 - currNode->getProbability();
            expectation = 0;
        }
        else
        {
            probability -= currNode->getProbability();
            expectation += time * currNode->getProbability();
        }

        if (m_CurrentMin >= 0)
        {
            if (expectation + probability * time >= m_CurrentMin)
            {
                return m_CurrentMin;
            }
        }

        bool allInUse = true;
        for(unsigned int i=1; i < m_Nodes.size(); ++i)
        {
            Node* nextNode = m_Nodes[i];
            if (nextNode->isInUse())
            {
                continue;
            }

            allInUse = false;
            nextNode->setInUse(true);
            permutate(probability, expectation, time + Weight[currNode->getID()][nextNode->getID()], nextNode);
            nextNode->setInUse(false);
        }

        if (allInUse) // end recursion condition)
        {
            m_CurrentMin = expectation;
        }

        return m_CurrentMin;
    }

    /*
    double permutate()
    {
        double result = -1;

        int nodeCount = m_Nodes.size() - 2;
        if (nodeCount > 0)
        {
            #ifdef _DEBUG
            int count = 1;
            #endif

            while (true)
            {
                double exp  = 0;
                double time = 0;
                for (vector<Node>::iterator n = m_Nodes.begin(); n != m_Nodes.end(); ++n)
                {
                    vector<Node>::iterator n1= n + 1;
                    if (n1 != m_Nodes.end())
                    {
                        time += Weight[n->getID()][n1->getID()];
                        exp  += (time * Probability[n1->getID()]);
                    }
                }

                if (result < 0)
                {
                    result = exp;
                }
                else if (exp < result)
                {
                    result = exp;
                }

                #ifdef _DEBUG
                cout << "Processing permutation # " << count << " -> " << exp << endl;
                ++count;
                #endif

                if (!next_permutation((m_Nodes.begin() + 1), m_Nodes.end())) { break;}
            }
        }

        return result;
    }
    */

protected:

    double       m_CurrentMin;
    vector<Node*> m_Nodes;
};

int main(int argc, char *argv[])
{
    Graph graph;

    #ifndef _DEBUG
    if (argc != 2)
    {
        return 0;
    }
    graph.read_graph(argv[1]);
    #else
    clock_t startWait = clock();;
    graph.read_graph("test-cases\\input01.txt");
    #endif

    graph.run_floyd();

    if (!graph.isConnected())
    {
        printf("-1.00\n");
    }
    else
    {
        printf("%.2f\n", graph.permutate(1.0, 0.0, 0.0, NULL));
        //printf("%.2f\n", graph.permutate());
    }

    #ifdef _DEBUG
    clock_t endtWait = clock();
    cout << "Time: " << ((endtWait - startWait) / 1000.0) << endl;
    int ri;
    cin >> ri;
    #endif

    return 0;
}

void Graph::cleanUp()
{
    if (Weight)
    {
        for (int i=0; i<NodeCount; ++i) { delete Weight[i];}
        delete[] Weight;
        Weight = NULL;
    }

    for (vector<Node*>::iterator itr = m_Nodes.begin(); itr!=m_Nodes.end(); ++itr)
    {
        delete (*itr);
    }
    m_Nodes.clear();

    NodeCount    = 0;
    m_CurrentMin = -1;
}
// split a string using isspace
void Graph::split_string(string text, vector<string>& words)
    {
        int i=0;
        char ch;
        string word;

        for(unsigned int i=0; i < text.size(); ++i)
        {
            ch = text[i];
            if (isspace(ch))
            {
                if (!word.empty())
                {
                    words.push_back(word);
                }
                word = "";
            }
            else
            {
                word += ch;
            }
        }

        if (!word.empty())
        {
            words.push_back(word);
        }
    }

// read sophie graph from a file
void Graph::read_graph(char* file)
{
    cleanUp();

    ifstream graphFile(file);
    if (graphFile.is_open())
    {
        string line;
        int state     = 0;
        int nodesRead = 0;

        map<string, int> nodeName;

        while ( graphFile.good() )
        {
            getline (graphFile, line);

            if (state == 0)
            {
                // read # of nodes
                // and create an empty node matrix
                NodeCount = atoi(line.c_str());
                if (NodeCount > 0)
                {
                    Weight        = new double*[NodeCount];
                    for (int i = 0; i < NodeCount; ++i)
                    {
                        Weight[i] = new double[NodeCount];
                        for (int j = 0; j < NodeCount; ++j)
                        {
                            Weight[i][j] = -1;
                        }
                    }
                }
                ++state;
            }
            else if (state == 1)
            {
                if (nodesRead < NodeCount) // read the nodes
                {
                    vector<string> words;
                    split_string(line, words);
                    if (words.size() == 2)
                    {
                        double probability = atof(words[1].c_str());
                        nodeName[words[0]] = nodesRead;

                        if (probability > 0 || nodesRead == 0)
                        {
                            Node* node = new Node(nodesRead, probability);
                            m_Nodes.push_back(node);
                        }

                        ++nodesRead;
                    }
                }
                else // read # of edges
                {
                    ++state;
                }
            }
            else if (state == 2) // read the edges
            {
                vector<string> words;
                split_string(line, words);
                if (words.size() == 3)
                {
                    map<string, int>::const_iterator itr = nodeName.find(words[0].c_str());
                    if (itr != nodeName.end())
                    {
                        int x = itr->second;
                        itr = nodeName.find(words[1].c_str());
                        if (itr != nodeName.end())
                        {
                            int y = itr->second;
                            Weight[x][y] = Weight[y][x] = atof(words[2].c_str());
                        }
                    }
                }
            }

        }
        graphFile.close();
    }
    else
    {
    }
}

void Graph::run_floyd()
{
    for (int k = 0; k < NodeCount; ++k)
    {
        for (int i = 0; i < NodeCount; ++i)
        {
            for (int j = 0; j < NodeCount; ++j)
            {
                double sum = Weight[i][k] + Weight[k][j];

                bool   inf = ((Weight[i][k] == -1) || (Weight[k][j] == -1));
                if (!inf)
                {
                    if (Weight[i][j] == -1)
                    {
                        Weight[i][j] = sum;
                    }
                    else if (sum < Weight[i][j])
                    {
                        Weight[i][j] = sum;
                    }
                }
            }
        }
    }

    #ifdef _DEBUG
    for (int i = 0; i < NodeCount; ++i)
    {
        for (int j = 0; j < NodeCount; ++j)
        {
            printf("%.2f ", Weight[i][j]);
        }
        cout << endl;
    }
    cout << endl << endl;
    #endif
}

bool Graph::isConnected()
{
    for (unsigned int j=1; j<m_Nodes.size(); ++j)
    {
        Node* node = m_Nodes[j];
        if (Weight[0][node->getID()] == -1)
        {
            return false;
        }
    }

    return true;
}