Desktop Programming > C/C++ & Visual C++

Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...

<< < (2/2)

David:
Now to some more interesting examples ... (and weighted graphs)

This (fixed-up) example, in C++, may give you some ideas about paths between nodes ...

and could easily be modified to find, from a data file, paths between distinct cities, by city-name.

It needs this data file with the file name to be:

c_graph.txt


--- Code: ---Node1 Node3 2.0
Node2 Node1 1.0
Node3 Node1 1.0
Node3 Node5 2.0
Node4 Node7 0.5
Node4 Node8 4.0
Node5 Node4 2.5
Node6 Node7 1.0
Node6 Node2 1.0
Node7 Node8 0.5
Node8 Node9 1.0

--- End code ---

Check it out:


--- Code: ---// c_ifPathExistsGetDistance.cpp //  // 2014-12-08 //

// use an ISO C++ compiler ... a pre C++11 compiler is ok //

/*
    Edited/fixed-up from code found on web at link below:
   
    http://mooreccac.com/kcppdoc/Dijkstra.htm
   
    on 2014-11-27
   
    Note: original algorithm there, then, was defective/had defective output ...
    It did NOT report if destination was actually reachable ... or NOT ...
    Did NOT utilize the back_pointers that it had produced,
    and it leaked memory, etc...
*/

#include <iostream>
#include <fstream>
#include <string>
#include <sstream> // re. stingstream obj's...
#include <list>
#include <map>
#include <queue>
#include <vector>

#include <cstdlib> // re. exit(1) ... //
#include <cctype> // re. toupper ... //

#include <algorithm> // re. swap ... //

using namespace std;

const string GRAPH_DATA_FILE = "c_graph.txt";

// "graph.txt"
/*
Node1 Node3 2.0

Node2 Node1 1.0

Node3 Node1 1.0
Node3 Node5 2.0

Node4 Node7 0.5
Node4 Node8 4.0

Node5 Node4 2.5

Node6 Node7 1.0
Node6 Node2 1.0

Node7 Node8 0.5
*/

struct Edge; // forward declaration ... //

struct Node
{
string name;
list< Edge* > neighbours;

bool visited;
double cost;
Node* back_pointer;

// ctor...
Node( const string& n )
        : name(n), visited(false), cost(0), back_pointer(0) { }
} ;

struct MyCmp // used by 'priority_queue' below ...
{
   bool operator() ( const Node* a, const Node* b )
   {
      return b->cost < a->cost; // least to greatest ... //
   }
} ;

struct Edge
{
double weight;
Node* dest;

// ctor...
Edge( double c, Node* d = 0 ) : weight(c), dest(d) {}
} ;

struct NodeMap
{
map< string, Node* > myMap;

// ctor... from fName
NodeMap( const string& fName )
    {
    ifstream fin( fName.c_str() );
    if( fin )
    {
        string fromStr, toStr;
        double weightDbl;
        while( fin >> fromStr >> toStr >> weightDbl )
        {
        Node* pTarget = find_in_myNodeMap(toStr);
        Node* pSource = find_in_myNodeMap(fromStr);
        Edge* pNewEdge = new Edge( weightDbl, pTarget );
        pSource->neighbours.push_back( pNewEdge );
        }
        }
        else
        {
            cerr << "\nThere was a problem opening file "
                 << fName
                 << "\n\nPress 'Enter' to exit ... " << flush;
             cin.get();
             exit(1);
        }
    }

Node* find_in_myNodeMap( const string& name )
    {
Node* result = myMap[name];
if( !result )
result = myMap[name] = new Node(name);
return result;
}

~NodeMap()
{
    map< string, Node* >::iterator it = myMap.begin(),
                                        end = myMap.end();
    for( ; it != end; ++ it )
    {
        Node* cur = it->second;
        list< Edge* >::iterator ite = cur->neighbours.begin(),
                                    ende = cur->neighbours.end();
            for( ; ite != ende; ++ ite )
                delete *ite; // delete each new Edge that was created
        delete cur; // now can delete each new Node created ...
    }
}
} ;

// to display the Graph nicely formatted ... //
ostream& operator << ( ostream& os, const NodeMap& nm )
{
map< string, Node* >::const_iterator im;
for( im = nm.myMap.begin(); im != nm.myMap.end(); ++im )
    {
os << im->second->name << endl;;
        list< Edge* > neighbours = im->second->neighbours;
list< Edge* >::iterator e;
for( e = neighbours.begin(); e != neighbours.end(); ++e )
os << " -> " << (*e)->dest->name << " weight "
               << (*e)->weight << endl;;
}
os << endl;
return os;
}



void ifPathExistsGetDistance( string s, string d, NodeMap& myNodeMap )
{
Node* source = myNodeMap.myMap[s];
Node* cur, *ne;

bool dWasReached = false; // flag to tell if d is reached ... //

priority_queue< Node* , deque< Node* > , MyCmp  > pq;


// put the source into pq and loop until empty
pq.push( source );
while( !pq.empty() )
    {
// process least cost node ... //
cur = pq.top();
pq.pop();
cur->visited = true;

// process neighbours ... //
list< Edge* >::iterator edge;
for( edge = cur->neighbours.begin();
             edge != cur->neighbours.end(); ++edge )
        {
ne = (*edge)->dest;

// If this adjacent node is the destination node,
            // then 'reachable'
            if ( ne->name == d )
            {
                dWasReached = true;
                ne->cost = (*edge)->weight;
ne->visited = true;
ne->back_pointer = cur;
break;
            }


if( !ne->visited )
            {
//ne->cost += (*edge)->weight + cur->cost;
ne->cost = (*edge)->weight;
ne->visited = true;
ne->back_pointer = cur;
/*
cout << " pushing " << ne->name
                     << " accumulative cost "
                     << ne->cost << endl;
*/
pq.push( ne );
}
}

if( dWasReached ) break;
}

if( dWasReached )
{
    cout << d << " *WAS* reached from " << s << " ...\n";
    double sum_cost = 0;
   
        cur = ne; // start with this, to get the first back_pointer, ok ... //
       
    while( true )
    {
            sum_cost += cur->cost;
            cout << cur->name
                 << ", cost to reach here from prev: "
                 << cur->cost << ", sum_cost: " << sum_cost<< endl;
            if( cur == source ) break;
            cur = cur->back_pointer;
    }
}
else
        cout << d << " was *NOT* reached from " << s << "\n";
}



// for each solution, reset node information
void reset_nodes( NodeMap& nm )
{
map< string, Node* >::iterator im;
for( im = nm.myMap.begin(); im != nm.myMap.end(); ++im )
    {
im->second->cost = 0;
im->second->back_pointer = 0;
im->second->visited = false;
}
}

// utility to facilitate getting valid user input ... //
bool isValid( string a, string b, int low, int high );

string& to1stUpper( string& s )
{
    s[0] = toupper(s[0]);
    return s;
}


int main() /////////////  MAIN BEGINS HERE  ////////////////
{
NodeMap myNodeMap( GRAPH_DATA_FILE );

    cout << "After read graph from file "
         << GRAPH_DATA_FILE << ": \n";

string s, d; // source, destination ... //
do
    {
        cout << myNodeMap; // display it ... //
       
cout << "Enter source Node (valid range Node1 .. Node9): "
             << flush;
bool ok = true;
if( cin >> s && cin.get() == '\n' )
{
    cout << "Enter target Node (valid range Node1 .. Node9): "
                 << flush;
            if( cin >> d && cin.get() == '\n' && isValid( to1stUpper(s), to1stUpper(d), 1, 9 ) )
    {
        ifPathExistsGetDistance( s, d, myNodeMap );
        reset_nodes( myNodeMap );
       
        swap( s, d );
       
        ifPathExistsGetDistance( s, d, myNodeMap );
        reset_nodes( myNodeMap );
    }
    else ok = false;
    }
    else ok = false;
   
    if( !ok )
    {
        cout << "\nEntry error ...NOTE! 1st 4 char's must be 'Node'\n";
        cin.clear();
        cin.sync();
    }

cout << "\nMore (y/n) ? " << flush;
getline( cin, s );
    }
    while( s != "n" );
} ////////////////////  MAIN ENDS HERE  ////////////////////


// Need to pre-validate input ... so that the data passed in
// here won't cause the program to 'crash' ... //
bool isValid( string a, string b, int low, int high )
{
    if( a.substr(0, 4) != "Node" || b.substr(0, 4) != "Node" )
    {
        cout << "\n1st 4 char's must be 'Node'\n";
        return false;
    }
   
    stringstream ss1, ss2;
    ss1 << a.substr(4); ss2 << b.substr(4);
    int aa, bb;
    bool dataOk = true;
    ss1 >> aa; ss2 >> bb;
    if( aa < low || aa > high )
    {
        cout << "\n" << aa << " NOT in range "
             << low << " to " << high << '\n';
        dataOk = false;
    }
    if( bb < low || bb > high )
    {
        cout << "\n" << bb << " NOT in range "
             << low << " to " << high << '\n';
        dataOk = false;
    }
    return dataOk;
}


--- End code ---

David:
Now, the one you have been waiting for ...

How to find the minimum distance between two nodes in a Graph (or two cities on a map)?



--- Code: ---// dijkstra_shortest_paths.cpp //  // 2014-11-27 //

/*
    Edited/fixed-up from code found at:
    http://en.literateprograms.org/Dijkstra's_algorithm_(C_Plus_Plus)?oldid=19645
    in the public domain under the Creative Commons CC0 1.0 waiver:
    http://creativecommons.org/publicdomain/zero/1.0/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>

#include <limits> // needed to add this ... //

const float INF = std::numeric_limits< float >::infinity();

struct Edge
{
    int target;
    float weight;
    Edge( int t, float w ) : target(t), weight(w) { }
} ;

typedef std::vector< std::list< Edge > > adj_vec_t;
typedef std::vector< std::string > cities_vec_t;
typedef std::pair< int, float > int_float_pair_t;


// functor is for ordering in a 'set' of type int_float_pair_t ... //
struct MyPairCmpLess
{
    bool operator () ( const int_float_pair_t& p1, const int_float_pair_t& p2 )
    {
        return p1.second < p2.second;
    }
} ;


void findAllDijkstraPaths( int source, adj_vec_t& adj_vec,
                          std::vector< float >& min_distance,
                          std::map< int, int >& previous )
{
    // initial all min_distance's to INF (now done by ctor)
    // ... but set 'source' to 0 ...
    min_distance[source] = 0;
   
    // Note: functor 'MyPairCmpLess' is used here ...
    // Note: 'set' is here being used as a type of priority queue ... //
    std::set< int_float_pair_t, MyPairCmpLess > pairs_queue;
   
    // Now ... fill up pairs_queue ... with initial values ...
    for( size_t i = 0; i < adj_vec.size(); ++ i  )
    {
        pairs_queue.insert( int_float_pair_t( i, min_distance[i] ) );
    }

    while( !pairs_queue.empty() )
    {
        int s = pairs_queue.begin()->first;
        pairs_queue.erase( pairs_queue.begin() );

        // Visit each Edge that proceeds from s ...
        for( std::list< Edge >::const_iterator edge_iter = adj_vec[s].begin();
             edge_iter != adj_vec[s].end(); ++ edge_iter )
        {
            int v = edge_iter->target;
            //float weight = edge_iter->weight;
            float sums_distance_to_s = min_distance[s] + edge_iter->weight;
        if( sums_distance_to_s < min_distance[v] )
            {
                // update ...
            pairs_queue.erase( int_float_pair_t( v, min_distance[v] ) );

            min_distance[v] = sums_distance_to_s;
            previous[v] = s; // insert or update ... //
            pairs_queue.insert( int_float_pair_t( v, min_distance[v] ) );
        }
        }
    }
}

// returns a (forward order) list of int for this (min) path  ...
std::list< int > getForwardPath( int start, const std::map< int, int >& previous )
{
    std::list< int > forward_list;
    //int s = start;
    forward_list.push_front(start); // push_front to reverse order of links ... //
   
    std::map< int, int >::const_iterator prev;
    while( (prev = previous.find(start)) != previous.end() )
    {
        start = prev->second;
        forward_list.push_front(start); // push_front to reverse order of links ... //
    }
    return forward_list; // now in forward order ... from source to target ...//
}


void populateGraph( adj_vec_t& adj_vec, cities_vec_t& cities_vec )
{
    cities_vec.push_back("Harrisburg");   // 0
    cities_vec.push_back("Baltimore");    // 1
    cities_vec.push_back("Washington");   // 2
    cities_vec.push_back("Philadelphia"); // 3
    cities_vec.push_back("Binghamton");   // 4
    cities_vec.push_back("Allentown");    // 5
    cities_vec.push_back("New York");     // 6
   
    adj_vec.resize(7);
   
    adj_vec[0].push_back(Edge(1,  79.83));
    adj_vec[0].push_back(Edge(5,  81.15));
    adj_vec[1].push_back(Edge(0,  79.75));
    adj_vec[1].push_back(Edge(2,  39.42));
    adj_vec[1].push_back(Edge(3, 103.00));
    adj_vec[2].push_back(Edge(1,  38.65));
    adj_vec[3].push_back(Edge(1, 102.53));
    adj_vec[3].push_back(Edge(5,  61.44));
    adj_vec[3].push_back(Edge(6,  96.79));
    adj_vec[4].push_back(Edge(5, 133.04));
    adj_vec[5].push_back(Edge(0,  81.77));
    adj_vec[5].push_back(Edge(3,  62.05));
    adj_vec[5].push_back(Edge(4, 134.47));
    adj_vec[5].push_back(Edge(6,  91.63));
    adj_vec[6].push_back(Edge(3,  97.24));
    adj_vec[6].push_back(Edge(5,  87.94));
}



int main()
{
    adj_vec_t adj_vec;
    cities_vec_t cities_vec;
   
    std::string dummy;
   
    populateGraph( adj_vec, cities_vec );
   
   
    // loop through all *starting* cities, 0 to 6 ... //
    for( int s = 0; s <= 6; ++ s )
    {
        std::cout << "\nPress 'Enter' to start at "
                  << cities_vec[s] << " ... " << std::flush;
        getline( std::cin, dummy );

       
        std::vector< float > min_distance( adj_vec.size(), INF );
        std::map< int, int > previous;
   
        findAllDijkstraPaths( s, adj_vec, min_distance, previous );
       
        // show all (min) paths and distances from this 'start' ... //
        for( size_t s = 0; s < adj_vec.size(); ++ s )
        {
            std::list< int > forward_path = getForwardPath( s, previous );
           
            std::cout << "Path: ";
            for( std::list< int >::const_iterator it = forward_path.begin();
                            it != forward_path.end(); ++ it )
                std::cout << cities_vec[*it] << ", ";
               
            std::cout << min_distance[s] << std::endl;
        }
    }
   
    std::cout << "\nPress 'Enter' to exit ... " << std::flush;
    getline( std::cin, dummy );
}

--- End code ---

David:
Now ... C



--- Code: ---/* dijkstra_shortestPath2c.c */  /*  2014-12-02 */


/* A C program for Dijkstra's single source shortest path algorithm.
 The program is for adjacency matrix representation of the graph */
 
/*
    Edited version here taken from original at:
    http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
*/
 
#include <stdio.h>
#include <limits.h>

#define INF INT_MAX
 
#define V 9 /* Number of vertices in the graph */


 
/* A utility function to find the vertex with minimum distance value, from
 the set of vertices not yet included in shortest path tree */
int minDistance( const int dist[], const int sptSet[] )
{
    int min = INF, /* Initialize min value */
        min_index = -1, /* added -1 */
        vi;
    for( vi = 0; vi < V; ++vi )
    {
        if ( !sptSet[vi]  &&  dist[vi] < min ) /* changed from <= */
            min = dist[vi], /* update values ... */
            min_index = vi;
    }

    return min_index;
}
 
/* A utility function to print the constructed distance array */
void printSolution( int src, const int dist[], const char* cities[] )
{
    int i;
    printf( "Destination   Distance from %s\n", cities[src] );
    for( i = 0; i < V; ++i )
        if( i != src )
            printf( "%11s  %21d\n", cities[i], dist[i] ) ;
}


 
/* Function that implements Dijkstra's single source shortest path algorithm
 for a graph represented using adjacency matrix representation */
void dijkstra( int src, const int graph[V][V], const char* cities[]  )
{
    int i,
        count;
    int dist[V];     /* The output array, dist[i], will hold the shortest
                   distance from src to i */

    int sptSet[V]; /* sptSet[i] == 1 if vertex i is included in shortest
                 path tree or shortest distance from src to i is finalized */
                 

    /* Initialize all distances as INFINITE and sptSet[] as 0 */
    for( i = 0; i < V; ++i )
         dist[i] = INF , sptSet[i] = 0;

    /* Distance of source vertex from itself is always 0 */
    dist[src] = 0;

    /* Find shortest path for all vertices */
    for( count = 0; count < V-1; ++count )
    {
        /* Pick the minimum distance vertex from the set of vertices not
        yet processed. u is always equal to src in first iteration. */
        int vi,
            u = minDistance( dist, sptSet );
       
        if( u == -1 ) break; /* I also added this line ... */

        /* Mark the picked vertex as processed */
        sptSet[u] = 1;

        /* Update dist value of the adjacent vertices of the picked vertex. */
        for( vi = 0; vi < V; ++vi )
        {
            /* Update dist[vi] only if is not in sptSet, there is an edge from
            u to v, and total weight of path from src to v through u is
            smaller than current value of dist[vi] */
            if( !sptSet[vi] && graph[u][vi] /* && dist[u] != INF  <- re. possible overflow,
                                          but? handled by prev. condition: '&& graph[u][vi]' */
                            && dist[u]+graph[u][vi] < dist[vi] )
                dist[vi] = dist[u] + graph[u][vi];
        }
    }

    /* print the constructed distance array */
    printSolution( src, dist, cities );
}
 
 

int main() /* driver program to test above function */
{
    int start = 0;
   
    const char* cities[] =
    {
        "City 0", "City 1", "City 2", "City 3", "City 4",
        "City 5", "City 6", "City 7", "City 8"
    } ;
   
    const int graph[V][V] = /* Create an example graph ... */
    {
        { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
        { 4, 0, 8, 0, 0, 0, 0,11, 0 },
        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
        { 0, 0, 7, 0, 9,14, 0, 0, 0 },
        { 0, 0, 0, 9, 0,10, 0, 0, 0 },
        { 0, 0, 4, 0,10, 0, 2, 0, 0 } ,
        { 0, 0, 0,14, 0, 2, 0, 1, 6 },
        { 8,11, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
    } ;

    for( ; start < V; ++start )
    {
        printf( "\nPress 'Enter' to start at %s ... ", cities[start] );
        while( getchar() != '\n' );
        dijkstra( start, graph, cities );
    }
   
    printf( "\nPress 'Enter' to exit ... " ); fflush( stdout );
    while( getchar() != '\n' );
    return 0;
}

/*
Output:

Press 'Enter' to start at City 0 ...
Destination   Distance from City 0
     City 1                      4
     City 2                     12
     City 3                     19
     City 4                     21
     City 5                     11
     City 6                      9
     City 7                      8
     City 8                     14

Press 'Enter' to start at City 1 ...
Destination   Distance from City 1
     City 0                      4
     City 2                      8
     City 3                     15
     City 4                     22
     City 5                     12
     City 6                     12
     City 7                     11
     City 8                     10

Press 'Enter' to start at City 2 ...

Notes:
1) The code calculates shortest distance,
   but doesn’t calculate the path information.
   We can create a parent array, update the parent array when
   distance is updated (like prim’s implementation) and use it
   to show the shortest path from source to different vertices.

2) The code is for undirected graph, same dijekstra function
   can be used for directed graphs also.

3) The code finds shortest distances from source to all vertices.
   If we are interested only in shortest distance from source to
   a single target, we can break the for loop when the picked
   minimum distance vertex is equal to target (Step 3.a of algorithm).

4) Time Complexity of the implementation is O(V^2). If the input
   graph is represented using adjacency list, it can be reduced
   to O(E log V) with the help of binary heap. We will soon be discussing
   O(E Log V) algorithm as a separate post.

5) Dijkstra’s algorithm doesn’t work for graphs with negative
   weight edges. For graphs with negative weight edges,
   Bellman–Ford algorithm can be used, we will soon be discussing
   it as a separate post.
   
*/

--- End code ---

David:
This C++ Shortest Path demo uses a heap as a priority queue ... (Instead of set and map as used in C++ version above.)


--- Code: ---//  dijkstra_shortest_path_via_min_heap.cpp //  // 2018-11-21 //

// This example uses a MIN HEAP as a MIN PRIORITY QUEUE //


#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <limits> // for numeric_limits
#include <algorithm> // re. make_heap(...), pop_heap(...), // renove(...) //


using std::vector;
using std::list;


// utility forward declaration /////////////////////////////////////
template< typename T >
T takeIn( const std::string& msg, const T& min, const T& max );
////////////////////////////////////////////////////////////////////


const double INF = std::numeric_limits< double >::infinity();


struct Edge
{
    size_t target;
    double distance;
    Edge( size_t t, double d ) : target(t), distance(d) {}
};


typedef vector< vector< Edge > > adj_vec_t;
typedef std::pair< size_t, double > pair_t;
typedef vector< std::string > place_vec_t;


struct MyMinCmp
{
    bool operator () ( const pair_t& a, const pair_t& b )
    {
        return b.second < a.second ;
    }
} ;


void dijkstraPaths( int source,
                    const adj_vec_t& adj_vec,
                    vector< double >& min_distance,
                    vector< int >& previous )
{
    size_t n = adj_vec.size();
    min_distance.clear();
    min_distance.resize( n, INF );
    min_distance[source] = 0;
    previous.clear();
    previous.resize( n, -1 );

    vector< pair_t > vertex_queue;
    vertex_queue.push_back( pair_t( source, min_distance[source] ) );

    while( !vertex_queue.empty() )
    {
        size_t u = vertex_queue.front().first;
        double dist_first = vertex_queue.front().second;

        pop_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );
        vertex_queue.pop_back();

        // Visit each edge adjacent to u //
        const vector< Edge > &edges = adj_vec[u];
        vector< Edge >::const_iterator it = edges.begin();
        for ( ; it != edges.end(); ++ it )
        {
            double through_u = dist_first + it->distance;
            size_t v = it->target;
        if( through_u < min_distance[v] )
            {
                pair_t pr = pair_t( v, min_distance[v] );
                // THIS BLOCK OF code may be faster RUNNING than 'remove' below ?? //
                vector< pair_t >::iterator itt = std::find(
                        vertex_queue.begin(), vertex_queue.end(), pr );

                if (itt != vertex_queue.end() )
                {
                    // swap the one to be removed with the last element
                    // and remove the item at the end of the container
                    // to prevent moving all items after '5' by one
                    std::swap( *itt, vertex_queue.back() );
                    vertex_queue.pop_back();
                }
                //std::remove( vertex_queue.begin(), vertex_queue.end(), pr );
                ////////////////////////////////////////////////////

            min_distance[v] = through_u;
            previous[v] = u;

            vertex_queue.push_back( pair_t( v, min_distance[v] ) );
            make_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );
        }
        }
    }
}


list<int> getShortestPath( int vertex, const vector< int >& previous )
{
    list< int > path;
    for ( ; vertex != -1; vertex = previous[vertex])
        path.push_front(vertex);
    return path;
}


void loadAdjList( adj_vec_t& adjacency_list )
{
    // NOTE! insert edges both ways for undirected graphs //

    adjacency_list[0].push_back(Edge(1, 7));
    adjacency_list[1].push_back(Edge(0, 7));
    adjacency_list[0].push_back(Edge(2, 9));
    adjacency_list[2].push_back(Edge(0, 9));
    adjacency_list[0].push_back(Edge(5, 12));
    adjacency_list[5].push_back(Edge(0, 12));

    adjacency_list[1].push_back(Edge(2, 10));
    adjacency_list[2].push_back(Edge(1, 10));
    adjacency_list[1].push_back(Edge(3, 13));
    adjacency_list[3].push_back(Edge(1, 13));

    adjacency_list[2].push_back(Edge(3, 11));
    adjacency_list[3].push_back(Edge(2, 11));
    adjacency_list[2].push_back(Edge(5, 2));
    adjacency_list[5].push_back(Edge(2, 2));

    adjacency_list[3].push_back(Edge(4, 6));
    adjacency_list[4].push_back(Edge(3, 6));

    adjacency_list[4].push_back(Edge(5, 9));
    adjacency_list[5].push_back(Edge(4, 9));
}

void showPlaces( const place_vec_t& places )
{
    for( size_t i = 0; i < places.size(); ++ i )
        std::cout << i << "->" << places[i] << '\n';
}


int main()
{
    place_vec_t places;
    for( size_t i = 0; i < 6; ++ i )
    {
        std::ostringstream oss;
        oss << i;
        places.push_back( "Town_" + oss.str() );
    }


    adj_vec_t adjacency_list(6);
    loadAdjList( adjacency_list );

    size_t n = adjacency_list.size();
    std::stringstream ss;
    ss << n-1;
    std::string topStr = ss.str();

    // these get initialed inside function dijkstraPaths called below
    vector< double > min_distance;
    vector< int > previous;
    ////////////////////////////////////////////////////////////////

    while( true )
    {
        showPlaces( places );
        size_t start = takeIn< int>( "Enter place to start (0.." +
                                     topStr + "): ", 0, n-1 );
        size_t stop =  takeIn< int>( "Enter place to stop (0.." +
                                     topStr + "): ", 0, n-1 );

        dijkstraPaths( start, adjacency_list, min_distance, previous );

        std::cout << "Distance from " << start << " to " << stop << ": "
                  << min_distance[stop] << std::endl;

        list< int > path = getShortestPath( stop, previous );

        std::cout << "Path : ";
        list< int >::const_iterator it = path.begin();
        for( ; it != path.end(); ++ it )
            std::cout << *it << "->" << places[*it] << "  ";
        std::cout << std::endl;

        std::cout << "More (y/n) ? ";
        std::string reply;
        getline( std::cin, reply );
        if( reply.size() && (reply[0] == 'n' || reply[0] == 'N') )
            break;
    }

    std::cout << "Ok ... exiting ... \nPress 'Enter' to continue/exit ... ";
    std::cin.get();
    return 0;
}


////////////////////////////////////////////////////////////////////
// definition utility //////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
template< typename T >
T takeIn( const std::string& msg, const T& min, const T& max )
{
    while( true )
    {
        std::cout << msg;
        std::string s, tmp;
        getline( std::cin, s );

        std::istringstream iss( s );
        T val;
        if( iss >> val && !(iss >> tmp) && val >= min && val <= max )
            return val;
        // else if reach here ... nOT in valid range //
        std::cout << "Only single values in range "
                  << min << ".." << max << " are valid here.\n";
    }
}

--- End code ---

Navigation

[0] Message Index

[*] Previous page