bellman.cpp

/**
    program author: K Sreram
    Author E-mail: sreramk@outlook.com
    License: GNU public license
*/
#include <limits>
#include <stdlib.h>
#include "bellman.h"
#include <iostream>
BellmanAlgorithm::BellmanAlgorithm()
{
    NodesArray = NULL;
}
BellmanAlgorithm::~BellmanAlgorithm()
{
    if(NodesArray != NULL)
        delete [] NodesArray;
}
void BellmanAlgorithm::TransverseAndDisplay()
{
    for(int i=0; i<NoOfNodes; ++i)
        std::cout << "\n" << NodesArray[i].Distance;
}

void BellmanAlgorithm::ResetSolveStep()
{
    for(int i=0; i< NoOfNodes; ++i)
        NodesArray[i].Flag = false;
    Q.push(&NodesArray[0]);
}

void BellmanAlgorithm::SolveStep()
{
    NodePtr N;
    std::list < LinkNode >::iterator i;
    while (!Q.empty())
    {
        N = Q.front();
        Q.pop();
        for(i = N->LinkNext.begin(); i!= N->LinkNext.end(); ++i)
          {

            if(i->NextNode->Distance  >  N->Distance + i->Weight)
                {
                    i->NextNode->Distance = N->Distance + i->Weight;
                    i->NextNode->Parent   = N;
                }

            if( (i->NextNode->Flag == false) && (i->NextNode != Source) )
                    {
                        i->NextNode->Flag = true;
                        Q.push(i->NextNode);
                    }
          }
    }
}

void BellmanAlgorithm::FindShortestPath(int nodeId)
{
    NodePtr temp;
    for(int i=0; i<NoOfNodes; ++i)
    {
        if(NodesArray[i].Data == nodeId)
        {
            temp = &NodesArray[i];
            while (temp != NULL)
            {
                std::cout << "\n" <<temp->Data;
                temp = temp->Parent;
            }
        }
    }
}

void BellmanAlgorithm::Solve()
{
    for(int i=1; i < NoOfNodes; ++i)
        {
            SolveStep();
            ResetSolveStep();
        }
}
// for connecting two nodes
void BellmanAlgorithm::MakeConnection(NodePtr From, NodePtr To, int weight)
{
    LinkNode N;
    N.NextNode = To;
    N.Weight = weight;
    From->LinkNext.push_back(N);
}

int **BellmanAlgorithm::SetMemoryInt(int x, int y)
{
    int** RetVal;
    RetVal = new int* [y];
    for(int i=0; i<x; ++i)
        RetVal[i] = new int;
    return RetVal;
}

void BellmanAlgorithm::FreeMemoryInt(int y, int ** mem)
{
    for(int i=0; i<y; ++i)
        delete [] mem[i];
    delete []mem;
}

NodePtr BellmanAlgorithm::NewNode(int size)
{
    return new Node[size];
}

void BellmanAlgorithm::FreeNode(NodePtr N)
{
    delete [] N;
}

void BellmanAlgorithm::InitializeGraph()
{
    int **ArrayLinks;
    int *DataFields;
    int n;
    std::cout << "Enter the number of nodes: ";
    std::cin  >> n;
    NoOfNodes = n;
    ArrayLinks = SetMemoryInt(n, n); // this is temporary
    DataFields = new int[n]; // this is temporary
    NodesArray = new Node[n]; // this lives until the object lives or is forced to reinitialize
    std::cout << "\n Enter the matrix:";

    // Value zero is considered as "Not connected".
    for(int i=0; i < n; ++i)
    {
        std::cout << "\nEnter the Data field : ";
        std::cin  >> DataFields[i];
        for(int j=0; j<n; ++j)
            {
                std::cout << "\nEnter the weight : ";
                std::cin >> ArrayLinks[i][j];
            }
    }

    for(int i=0; i<n; ++i)
    {
        NodesArray[i].Data = DataFields[i];
        NodesArray[i].Distance = (i==0)? 0: INT_MAX; // store maximum integer value
        NodesArray[i].Flag = false;
        NodesArray[i].Parent = NULL;
        for(int j=0; j<n; ++j)
        {
            if(ArrayLinks[i][j]!=0)
            {
                MakeConnection(&NodesArray[i], &NodesArray[j], ArrayLinks[i][j]);
            }
        }
    }
    Source = &NodesArray[0];
    Q.push(&NodesArray[0]);
    // freed memory
    delete [] DataFields;
    FreeMemoryInt(n, ArrayLinks);
}