bellman.h

/**
    program author: K Sreram
    Author E-mail: sreramk@outlook.com
    License: GNU public license
*/
#ifndef BELLMAN_H
#define BELLMAN_H

#include <queue>
#include <list>


struct Node; // Each  node in the graph is represented by this structure
struct Link; // This is a link, rather than having a link to another node from a node,
             // there is another structure which contains all the succeeding links.
struct LinkNode;
typedef Node* NodePtr;
typedef Link* LinkPtr;
typedef std::queue < NodePtr > NodePtrQueue; // used to keep track of the nodes that the
                                             // algorithm needs to transverse to set the distance
struct LinkNode
{
    NodePtr NextNode;
    int Weight;
};

struct Node
{
    bool Flag;
    int Data;
    std::list<LinkNode> LinkNext;
    int Distance;
    NodePtr Parent;
};


/*
    This is the bellman-ford implementation class, which contains the generated
    graph and has modules that transverses through each node setting the distance
    from the source. This algorithm runs in O(|V||E|).

*/
class BellmanAlgorithm
{
    int NoOfNodes; // holds the number of nodes in the graph
    NodePtr NodesArray; // these pointers are created and lives until the object exists
    NodePtrQueue Q; // this queue stores the list of all nodes that aren't visited but have its distances updated
    NodePtr Source; // the source node's pointer
    int ** SetMemoryInt(int x, int y); // declares a 2D array of size x*y
    void FreeMemoryInt(int y, int** mem); //Frees the memory allocated by the function 'int ** SetMemoryInt(int x, int y);'
    NodePtr NewNode(int size); // creates a new node and returns its pointer
    void FreeNode (NodePtr N); // frees the memory space occupied by the node
public:
    void InitializeGraph(); // get the graph from the user
    BellmanAlgorithm();
    ~BellmanAlgorithm(); // frees: NodesArray,
    void MakeConnection (NodePtr from, NodePtr To, int weight); // create a weighted connection between two nodes
    void ResetSolveStep(); // Resets the solve procedure
    void SolveStep(); // A single unit solve step; involves traversing through each node, updating the distance.
    void Solve(); //This is the final solve procedure
    void TransverseAndDisplay(); // Displays the node's distance from  the source, linearly.
    void FindShortestPath(int nodeId); // NodeId is given, which is matched with the 'data' field and the
                                       // shortest path is returned in reverse order
};

#endif // BELLMAN_H