Listing 4: SAMPLE.CPP Sample usage of the network template and shortest path algorithms

#include <iostream>
#include "network.h"
#include "spath.h"

#if defined(__BORLANDC__) || (_MSC_VER >= 1100 )
    using namespace std;
#endif

// interesting node and arc classes
class NODE
{
    int source;
public:
    NODE() : source(0) {}
    NODE(const NODE& node) : source(node.source) {}
    NODE& operator=(const NODE& node) 
        { source=node.source; return *this; }
    int  getSource() const { return source; }
    void setSource(int s) { source=s; }
};

class ARC
{
    // this arc stores a flow, capacity, and cost information;
    // suitable for a simple min-cost flow problem.
    int flow;
    int capacity;
    int cost;
public:
    ARC() : flow(0),capacity(0), cost(0) {}
    ARC(const ARC& arc) : flow(arc.flow),capacity(arc.capacity), 
        cost(arc.cost){}
    ARC& operator=(const ARC& arc) 
        { flow=arc.flow; capacity=arc.capacity; 
          cost=arc.cost; return *this; }
    int  getFlow() const { return flow; }
    void setFlow(int f) { flow=f; }
    int  getCapacity() const { return capacity; }
    void setCapacity(int c) { capacity=c; }
    int  getCost() const { return cost; }
    void setCost(int c) { cost=c; }
};

//
// predicate for above ARC class for the shortest-path algorithms
//
struct ARCCOST
{
    typedef int value_type;
    static const int infinity;
    static const int zero;
    // "distance" on these arcs is the cost of the arc
    int operator()(const ARC& arc) const
        { return arc.getCost(); }
};
const int ARCCOST::infinity = 10000000;
const int ARCCOST::zero = 0;
typedef network<NODE, ARC, allocator<NODE> > NETWORK;

//
// put a five-node network into the passed parameter
//
void load(NETWORK& net)
{
// ...
}

//
// display the structure of the network
//
void iterate(NETWORK& net)
{
// ...
}

//
// define a simple integer-based network
//
typedef network<int, int, allocator<int> > NETWORK2;

struct ARCCOST2
{
    typedef int value_type;
    static const int infinity;
    static const int zero;
    int operator()(const int& arc) const
        { return arc; }
};
const int ARCCOST2::infinity = 10000000;
const int ARCCOST2::zero = 0;

// vector to use for distance labels
typedef vector<int, allocator<int> > INTVECTOR;

//
// given predecessor list and distance vector, report
// shortest-path results
//
void report(const INTVECTOR& pred, const INTVECTOR& distance)
{
    for(int i=0;i<pred.size();i++)
    {
        cout << "Node " << i+1;
        cout << " Predecessor: " << pred[i]+1;
        cout << " Distance: " << distance[i];
        cout << endl;
    }
}

//
// a simple negative-distance cycle network
//
void neg_cycle()
{
    cout << "Negative cycle network." << endl;
    NETWORK2 net;
    net.insert_nodes(net.begin_nodes(), 4, 0);
    net.insert_arc(0,1,1);
    net.insert_arc(1,2,2);
    net.insert_arc(2,3,-3);
    net.insert_arc(3,1,0);
    net.insert_arc(3,0,1);
    ARCCOST2 a;
    INTVECTOR pred;
    INTVECTOR distance;

    bool b;
    b = shortest_path_fifo_labelcorrecting(net, net.begin_nodes(), 
        pred, distance, a);
    if( b )
    {
        cout << "DIDN'T DETECT NEGATIVE CYCLE. OOPS" << endl;
        report(pred, distance);
    }
    else
        cout << "-->Negative cycle detected!" << endl;
}

//
// yet another shortest-path problem
//
void spath2()
{

    NETWORK2 net;
    net.insert_nodes(net.begin_nodes(), 6, 0);
    net.insert_arc(2, 3, 1);
    net.insert_arc(4, 3, 1);
    net.insert_arc(2, 4, 2);
    net.insert_arc(1, 2, 2);
    net.insert_arc(1, 3, 2);
    net.insert_arc(4, 5, 3);
    net.insert_arc(0, 2, 4);
    net.insert_arc(0, 1, 6);
    net.insert_arc(3, 5, 7);

    ARCCOST2 a;
    INTVECTOR pred;
    INTVECTOR distance;

    bool b = shortest_path_heap_dijkstra(net, net.begin_nodes(), 
        pred, distance, a);
    report(pred, distance);
}

int main()
{
    NETWORK net;
    load(net);
    iterate(net);
    net.erase_nodes(2);
    net.erase_nodes(1,2);
    iterate(net);
    net.insert_nodes(net.begin_nodes()+1, 5);
    iterate(net);
    net.clear();
    iterate(net);

    spath2();
    neg_cycle();
    return 0;
}
//End of File