Author Topic: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...  (Read 32564 times)

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile



The subject of Graphs, Directed Graphs and Weighted Directed Graphs can be quite daunting (especially at first) ...

This site will feature some simple beginning steps ... and a collation of example code, that was recently found on the web  ... but here it is all together ... edited, fixed and polished some ... to help make it all ... work for YOU!

Here is a little C++ example, to get you started ... that uses an adjacency list  ...(Google it) ...

Check it out.

It simply tests and reports if a target vertex is reachable from some start vertex.
An example might be ... can one get from one place ... in a maze ... to some other?

Code: [Select]
// a_isReachable.cpp //  // 2014-12-08 //

// a DiGraph (Directed Graph) using an adjacency list //

/*
    Edited/augmented & fixed memory leaks
    now uses STL vector containers, etc (instead of new arrays, etc)
   
    Idea and original code found at:
    http://www.sanfoundry.com/cpp-program-find-shortest-path-between-two-vertices-using-dijkstras-algorithm/
   
    This program simply tells if a node 'd', (the destination),
    is 'reachable' from 's', (the start),
    (the node from which we start the search to see if
     there exists any 'reachable path')
   
    The 'digraph' here is unweighted ...
   
    The program stops and reports 'reachable' at the first
    'reachable' path encountered as it traverses the 'graph'
*/

#include <iostream>
#include <vector>
#include <list>

#include <string> // re. more() ...
#include <cctype> // re. tolower(..)

#include <algorithm> // re. swap

using namespace std;

 

// This class represents a directed graph
// (a simple un-weighted digraph)
// using an adjacency list representation ... //

class Graph
{
    vector< list< int > > adj;
public:
    // ctor... v is number of Verticies (Nodes)
    Graph( int v );
   
    // function to add an edge to graph
    void addEdge( int p, int q ) ;
   
    // returns true if there is a path from s to d, other wise returns false
    bool isReachable( int s, int d );
   
    // a wrapper function to return size 'vector< list< int > > adj'
    size_t size() const { return adj.size() ; }
   
    friend ostream& operator << ( ostream&, const Graph& );
} ;


// def'ns

ostream& operator << ( ostream& os, const Graph& g )
{
    int size = g.adj.size();

    if( size )
    {
        list< int >::const_iterator it;
        for( int i = 0; i < size; ++ i )
        {
            for( it = g.adj[i].begin(); it != g.adj[i].end(); ++ it )
                 os << '(' << i << ','<< *it << ")  ";
            os << '\n';
        }
    }
    return os;
}

Graph::Graph( int v ) // ctor...
{
    adj.resize( v );
}

void Graph::addEdge( int v, int w )
{
    adj[v].push_back( w ) ; // Add w to v’s list.
}

// A BFS (Breadth First Search) based function ...
// to check whether d is reachable from s.
// Note the use of a queue (a list < int > here)... FIFO //
bool Graph::isReachable( int s, int d )
{
    // Base case ...
    if( s == d )
        return true;

    // construct & (initial) all the vertices as not yet visited ...
    vector< bool > visited ( this->size(), false );

    // construct an empty queue (a list of int) for BFS ...
    list< int > queue;

    // set the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);

    while( !queue.empty() )
    {
        // Dequeue a vertex from queue ...
        s = queue.front();
        queue.pop_front();
       
        // iterator 'it' will be used to get all the
        // adjacent vertices of a vertex ...
        list< int >::iterator it;

        // Get all adjacent vertices of the dequeued vertex s
        // If an adjacent has not been visited, then mark it visited
        // and enqueue it
        for( it = adj[s].begin(); it != adj[s].end(); ++it )
        {
            // If this adjacent node is the destination node, then return true
            if ( *it == d )
                return true;

            // Else, continue to do BFS
            if( !visited[*it] )
            {
                visited[*it] = true;
                queue.push_back(*it);
            }
        }
    }

    return false;
}


// utiliites to facilitate valid input in a loop ... //
int takeInChr( const std::string& msg = "" )
{
    std::cout << msg << flush;
    std::string reply;
    getline( cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}
bool more()
{
    if( tolower( takeInChr( "\n\nMore (y/n) ? " )) == 'n' )
return false;
    // else ...
    return true;
}

bool uvOkRange( int u, int v, int topVal )
{
    bool goodData = true;
    if( u < 0 || u > topVal )
        { cout << '\n' << u << " NOT in range 0.."
               << topVal << '\n'; goodData = false; }
    if( v < 0 || v > topVal )
        { cout << '\n' << v << " NOT in range 0.."
               << topVal << '\n'; goodData = false; }
    return goodData;
}




// Driver program to test methods of graph class
int main()
{
    // construct an empty graph to hold 5 Verticies (5 Nodes) ..
    Graph g(5);
   
    // get adjacent nodes for each node in graph ...
    g.addEdge(0, 1);  // 1 'is reachable' from 0
    g.addEdge(0, 2);  // 2 'is reachable' from 0
   
    g.addEdge(1, 3);  // 3 'is reachable' from 1
   
   
    g.addEdge(2, 1);
    g.addEdge(2, 3);
   
    g.addEdge(2, 4);
   
    g.addEdge(3, 4);
    g.addEdge(4, 4);

    do
    {
        cout << "The graph g: \n"<< g ;
       
        cout << "\nEnter 2 int's separated by a space ..."
             << "\nthe source and destination vertices, in range 0..4 : ";
        int u, v;
        if( cin >> u >> v && cin.get() == '\n' && uvOkRange( u, v, 4 ) )
        {
            int count = 2;
            while( count-- )
            {
                cout << "\nThere is "
                     << (g.isReachable(u, v) ? "a " : "NO ")
                     << "path from " << u << " to " << v;
                swap( u, v );
            }

        }
        else
        {
            cin.clear();
            cin.sync();
            cout << "\nData entry error ...\n";
        }
    }
    while( more() );
}


For a easy way to download all these example programs, see ...

http://www.4shared.com/folder/WUykX6-t/DiGraphsAndWDiGraphs.html


Addendum:

This subject ... of how to reach a place ... leads to  ... a much BIGGER context !!!



After several days of many hours each ... I suddenly was impressed ...  that the structure and the meaning of any notation  ... is so important!

Abstract symbols have meaning only in pre-defined (real) context.

For example:

What do I mean when I say (two, to, too, ... ) ?

The same sound has several spellings to help differentiate the meaning provided by different contexts ...


It's really quite amazing what a bird's eye look/see ...

by any of God's seeing creation ... can do!


In terms of reach-ability ...

How can (fleshly/finite) man, (ever) see/reach the (invisible infinite Spirit), the Creator of this whole large universe?


Well ... firstly, everything created tells much regarding the creator ...

Firstly ... that a Creator exists!

And much more !!!


But ... since we can see, hear, speak, move, love, hate ... so much more our Creator!

So did / does our creator ever re-veal beyond what the created things speak?


Yes ... the history of this ... His-Story ... is well established and preserved ...

passed on by those to whom it was chosen to be entrusted.


There is a steady line drawn from Adam via Seth, to Noah and via Shem, to Abraham and via Isaac, Jacob/Israel, Judah ... to Yeshua the Messiah, who was also fore-named Emmanuel (i.e. the creator El to be with us, the creator who in the beginning, as Elohim, created the heavens and the earth.)

Please continue at:

http://developers-heaven.net/forum/index.php/topic,2587.0.html
« Last Edit: December 08, 2014, 06:02:09 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #1 on: December 08, 2014, 01:20:46 PM »
This next little example, with imbedded links, is coded in Python 3...

You may like to play with it as you study the link and example code ...

And further read up on:

Breadth First Search (bfs)

vs

Depth First Search (dfs)

Code: [Select]
# graph_2.py #  # 2014-12-07 #  # a simple Python 3 implementation #

'''
    See:
    http://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/slides-full09.pdf
    Inf 2B: Graphs, BFS, DFS
    Kyriakos Kalorkoti
    School of Informatics
    University of Edinburgh
'''

Vx = ( 0,1,2,3,4,5,6 )
E  = ( (0,2),(0,4),(0,5),(1,0),(2,1),(2,5),(3,1),(3,6),(4,0),(4,5),(6,3),(6,5) )
G = ( Vx, E )

LstAdjLsts = ( (2,4,5),(0,),(1,5),(1,6),(0,5),(),(3,5) )


def showLstAdjLsts():
    print( "Showing LstAdjLsts..." )
    for i, e in enumerate(LstAdjLsts):
        for ee in e:
            print( (i, ee), end = ' ' )
        print()

   
def bfsStartAt( v ):
    visited = [ False ]*len(Vx)
    visited[v] = True
    print( v, end = ' ' )
   
    Q = []
    Q.append(v)
    while( Q ):
        v = Q[0]
        Q = Q[1:]
        for w in LstAdjLsts[v]:
            if visited[w] == False:
                visited[w] = True
                print( w, end = ' ' )
                Q.append(w)
    print( "\nShowing visited :", visited )


def dfsStartAt( v ):
    visited = [ False ]*len(Vx)
   
    Stk = []
    Stk.append(v)
    while( Stk ):
        v = Stk[-1]
        Stk = Stk[0:-1]
        if visited[v] == False:
            visited[v] = True
            print( v, end = ' ' )
            for w in LstAdjLsts[v]:
                Stk.append(w)
    print( "\nShowing visited :", visited )


# the recursive part #
def dfs_r( s, visited ):
    visited[s] = True
    print( s, end = ' ' )
    # using reversed order here
    # so output will match non_recursive
    # (using local stack) call above ...
    for w in reversed(LstAdjLsts[s]):
        if visited[w] == False:
            dfs_r( w, visited )
           
def dfsStartAt_r( v ):
    visited = [ False ]*len(Vx)   
    dfs_r( v, visited )       
    print( "\nShowing visited :", visited )



showLstAdjLsts()

loop = 0
while loop < 7 :
    print( "\nShowing bfsStartAt(", loop, ") : ", end = '' )
    bfsStartAt( loop )

    print( "\nShowing dfsStartAt(", loop, ") : ", end = '' )
    dfsStartAt( loop )

    print( "Showing dfsStartAt_r(", loop, ") : ", end = '' )
    dfsStartAt_r( loop )
   
    loop += 1
    if loop < 7:
        input( "Press 'Enter' to continue ... " )
    else:
        input( "\n\n\n*** Press 'Enter' to EXIT *** " )
       

   

« Last Edit: December 08, 2014, 01:22:51 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #2 on: December 08, 2014, 01:31:52 PM »
Now we will jump to C ...

this similar demo ...

(as the Python one above, but in C, and using a MATRIX, instead of an adjacency list)

bfs

vs

dfs (recursive and non-recursive)

You will first need to get a copy of file Clist.h ... as it needs to be included.

It is available here:

http://developers-heaven.net/forum/index.php/topic,2582.0.html

Note: we need a stack (a Clist) and a queue (a Clist) to push and pop data ...


Code: [Select]
/* c_reachable_dfsVSbfs_matrix_c.c */  /* rev. 2014-12-08 */

/* using some globals here to keep code similar...
   to related (coded in Python) example ... */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> /* re. INT_MAX */

/**********************************************************
 ***     re. using Clist.h for stack and queue ***        */
typedef struct ClistOfInt
{
    int val;
    struct ClistOfInt* next;
} List ; /* i.e. ... a node/element/record in the list ...*/

typedef List* pList;

void clearLrec( pList p )
{
/* no dynamic Cstrings, etc... to free here ... */
}

#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char text[] )
{
    if( !condition )
    {
        fprintf(stderr, "%s\n", text );
        fputs( "Press 'Enter' to exit program ... ", stderr );
        getchar();
        exit(1);
    }
}
#endif
/**********************************************************/

/* above needed by Clist.h */
#include "Clist.h" /*  to use ClistOfInt as stack and queue */


/* using some globals here for simpler code ... */

#define N 9  /* N is no of vertices in Graph */
const int G[N][N] = /* 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 }
} ;
int VISITED[N]; /* graph is stored in matrix G[N][N ] */


void dfs_r( int, int );

void isReachable_dfs( int s, int d );

void showGraph( const int g[N][N] );

/* coded for this added function is at bottom here ...
   so can use as stack (with push_front) and queue (with push_back) */
int popClist( Clist* pLst ) ;

void isReachable_dfs_non_recursive( int s, int d );
void isReachable_bfs( int s, int d );


int main()
{
    int j, k;
   
    puts( "Showing Graph ... " );
    showGraph( G );
    putchar( '\n' );

    for( j = 0; j < N; ++ j )
    {
        printf( "Showing isReachable_dfs(s=%d,d=%d) : ", 3, j );
        isReachable_dfs( 3, j ); /* begin at 3 */
        putchar( '\n' );
    }

    printf( "\nPress 'Enter' to continue ... " );
    while( getchar() !=  '\n' ) ;

    for( j = 0; j < N; ++ j )
    {
        printf( "Showing isReachable_dfs(s=%d,d=%d) : ", j, 3 );
        isReachable_dfs( j, 3 ); /* begin at 3 */
        putchar( '\n' );
    }

    printf( "\nPress 'Enter' to continue ... " );
    while( getchar() !=  '\n' ) ;

    for( j = 0; j < N; ++ j )
    {
        for( k = 0; k < N; ++ k )
        {
            if( j != k )
            {
                printf( "now doing 'is reachable_dfs(%15d, %d)' : ", j, k ) ;
                isReachable_dfs( j, k );
                putchar( '\n' );
                printf( "now doing 'is reachable_dfs_non_recursive(%d, %d)' : ", j, k ) ;
                isReachable_dfs_non_recursive( j, k );
                putchar( '\n' );
                printf( "now doing 'is reachable_bfs(%15d, %d)' : ", j, k ) ;
                isReachable_bfs( j, k );
                puts( "\n" );
            }
        }
        printf( "\nPress 'Enter' to continue ... " );
        while( getchar() !=  '\n' ) ;
    }
   
    printf( "\nPress 'Enter' to EXIT ... " ); fflush( stdout );
    while( getchar() !=  '\n' );
    return 0;
}



/* ... just to call recursive drf_r... */
void isReachable_dfs( int s, int d )
{
    int j;
    for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
         VISITED[j] = 0; /* using GLOBAL array here ... */
    dfs_r( s, d );
}
/* begin recursive ... starting from i */
void dfs_r( int i, int d )
{
    int j;
    VISITED[i] = 1; /* Now mark this 'i' as visited ... */
    printf( "%d ", i ); /* show 'i' here at top ... */
   
    if( i == d )
    {
        printf( "found " );
        return;
    }

            /* push in reversed order here, so ...
            output will match non-recursive calls. */
    for( j = N-1; j >= 0; --j )
        if( !VISITED[j]  &&  G [i][j] ) /* if NOT visited and reachable */
            dfs_r( j, d );
}

void isReachable_dfs_non_recursive( int s, int d )
{
    int j;
    Clist stk;
    List lst;
    lst.val = s;
    initClist( &stk );

    for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
         VISITED[j] = 0; /* using GLOBAL array here ... */

    push_frontClist( &stk, &lst );
    while( stk.size )
    {
        int cur = popClist( &stk );
        if( !VISITED[cur] )
        {
            /* Now mark this 'i' as visited ... */
            VISITED[cur] = 1;
            printf( "%d ", cur ); /* show 'cur' here at top */

            if( cur == d )
            {
                printf( "found " );
                break;
            }
           
            /* for all j reachable from cur ... */
            for( j = 0; j < N; ++j )
            {
                if( G[cur][j] )
                {
                    lst.val = j;
                    push_frontClist( &stk, &lst );
                }
            }
        }
    }
    clearClist( &stk ); /* make sure to free any  dynamic memory */
}

void isReachable_bfs( int s, int d )
{
    int j;
    Clist que;
    List lst;
    lst.val = s;
    initClist( &que );

    for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
         VISITED[j] = 0; /* using GLOBAL array here ... */
         
    VISITED[j] = 1;
    printf( "%d ", s );
    if( s == d )
    {
        printf( "found " );
        return;
    }

    push_backClist( &que, &lst );
    while( que.size )
    {
        int cur = popClist( &que );

        /* for all (not-visited) j reachable from cur ... */
        for( j = 0; j < N; ++ j )
        {
            if( !VISITED[j]  &&  G[cur][j] )
            {
                VISITED[j] = 1;
                printf( "%d ", j );

                if( j == d )
                {
                    printf( "found " );
                    break;
                }

                lst.val = j;
                push_backClist( &que, &lst );
            }
        }
    }
    clearClist( &que ); /* make sure to free any  dynamic memory */
}

void showGraph( const int g[N][N] )
{
    int i, j;
    for( i = 0; i < N; ++ i )
    {
        for( j = 0; j < N; ++ j )
             printf( "%3d ", g[i][j] );
        putchar( '\n' );
    }
}



int popClist( Clist* pLst )
{
    if( pLst->size )
    {
        pList cur = pLst->start;
        int tmp = cur->val;
        pLst->start = cur->next;
        free( cur );
        --pLst->size;
        if( pLst->size < 2 )
        {
            pLst->isSorted = 1;
            pLst->end = pLst->start;
        }
        return tmp;
    }
    return INT_MAX;
}



« Last Edit: December 08, 2014, 01:33:23 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #3 on: December 08, 2014, 01:42:15 PM »
Back to C++ ...

And adjacency lists ...

This simple example is very similar to the first, that just searches for a vertex ...  to indicate if it IS reachable?.

(But it demos the use of a set to track the nodes already visited, and not an array or vector.)

See if you can find the very few edits here to go from the first example program that used a STL vector?


Code: [Select]
// a_isReachable_visitedSET.cpp //  // 2014-12-08 //

// a DiGraph (Directed Graph) using an adjacency list //

#include <iostream>
#include <vector>
#include <list>
#include <set> // re. tracking visted ... //

#include <string> // re. more() ...
#include <cctype> // re. tolower(..)

#include <algorithm> // re. swap

using namespace std;

/*
    Edited/augmented & fixed memory leaks
    now uses STL vector containers, etc (instead of new arrays, etc)
   
    Idea and original code found at:
    http://www.sanfoundry.com/cpp-program-find-shortest-path-between-two-vertices-using-dijkstras-algorithm/
   
    This program simply tells if a node 'd', (the destination),
    is 'reachable' from 's', (the start),
    (the node from which we start the search to see if
     there exists any 'reachable path')
   
    The 'digraph' here is unweighted ...
   
    The program stops and reports 'reachable' at the first
    'reachable' path encountered as it traverses the 'graph'
*/



// This class represents a directed graph
// (a simple un-weighted digraph)
// using an adjacency list representation ... //

class Graph
{
    vector< list< int > > adj;
public:
    // ctor... v is number of Verticies (Nodes)
    Graph( int v );
   
    // function to add an edge to graph
    void addEdge( int p, int q ) ;
   
    // returns true if there is a path from s to d, other wise returns false
    bool isReachable( int s, int d );
   
    // a wrapper function to return size 'vector< list< int > > adj'
    size_t size() const { return adj.size() ; }
   
    friend ostream& operator << ( ostream&, const Graph& );
} ;


// def'ns

ostream& operator << ( ostream& os, const Graph& g )
{
    int size = g.adj.size();

    if( size )
    {
        list< int >::const_iterator it;
        for( int i = 0; i < size; ++ i )
        {
            for( it = g.adj[i].begin(); it != g.adj[i].end(); ++ it )
                 os << '(' << i << ','<< *it << ")  ";
            os << '\n';
        }
    }
    return os;
}

Graph::Graph( int v ) // ctor...
{
    adj.resize( v );
}

void Graph::addEdge( int v, int w )
{
    adj[v].push_back( w ) ; // Add w to v’s list.
}

// A BFS (Breadth First Search) based function ...
// to check whether d is reachable from s.
// Note the use of a queue ... FIFO ...  //
bool Graph::isReachable( int s, int d )
{
    // Base case ...
    if( s == d )
        return true;

    // to hold verticied that habe been visited ...
    set< int > visited;

    // construct an empty queue (a list of int) for BFS ...
    list< int > queue;

    // set the current node as visited and enqueue it
    visited.insert(s);
    queue.push_back(s);

    while( !queue.empty() )
    {
        // Dequeue a vertex from queue ...
        s = queue.front();
        queue.pop_front();
       
        // iterator 'it' will be used to get all the
        // adjacent vertices of a vertex ...
        list< int >::iterator it;

        // Get all adjacent vertices of the dequeued vertex s
        // If an adjacent has not been visited, then mark it visited
        // and enqueue it
        for( it = adj[s].begin(); it != adj[s].end(); ++it )
        {
            // If this adjacent node is the destination node, then return true
            if ( *it == d )
                return true;

            // Else, continue to do BFS
            if( !visited.count(*it) )
            {
                visited.insert(*it);
                queue.push_back(*it);
            }
        }
    }

    return false;
}


// utiliites to facilitate valid input in a loop ... //
int takeInChr( const std::string& msg = "" )
{
    std::cout << msg << flush;
    std::string reply;
    getline( cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}
bool more()
{
    if( tolower( takeInChr( "\n\nMore (y/n) ? " )) == 'n' )
return false;
    // else ...
    return true;
}

bool uvOkRange( int u, int v, int topVal )
{
    bool goodData = true;
    if( u < 0 || u > topVal )
        { cout << '\n' << u << " NOT in range 0.."
               << topVal << '\n'; goodData = false; }
    if( v < 0 || v > topVal )
        { cout << '\n' << v << " NOT in range 0.."
               << topVal << '\n'; goodData = false; }
    return goodData;
}




// Driver program to test methods of graph class
int main()
{
    // construct an empty graph to hold 5 Verticies (5 Nodes) ..
    Graph g(5);
   
    // get adjacent nodes for each node in graph ...
    g.addEdge(0, 1);  // 1 'is reachable' from 0
    g.addEdge(0, 2);  // 2 'is reachable' from 0
   
    g.addEdge(1, 3);  // 3 'is reachable' from 1
   
   
    g.addEdge(2, 1);
    g.addEdge(2, 3);
   
    g.addEdge(2, 4);
   
    g.addEdge(3, 4);
    g.addEdge(4, 4);

    do
    {
        cout << "The graph g: \n"<< g ;
       
        cout << "\nEnter 2 int's separated by a space ..."
             << "\nthe source and destination vertices, in range 0..4 : ";
        int u, v;
        if( cin >> u >> v && cin.get() == '\n' && uvOkRange( u, v, 4 ) )
        {
            int count = 2;
            while( count-- )
            {
                cout << "\nThere is "
                     << (g.isReachable(u, v) ? "a " : "NO ")
                     << "path from " << u << " to " << v;
                swap( u, v );
            }

        }
        else
        {
            cin.clear();
            cin.sync();
            cout << "\nData entry error ...\n";
        }
    }
    while( more() );
}

« Last Edit: December 08, 2014, 01:45:31 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #4 on: December 08, 2014, 01:56:48 PM »
More C++ ... Note that this example program needs a C++11 compiler.

More ... and you may like to NOTE the embedded comments in the program here and also the comments at the embedded links ... in the program.

bfs

vs

dfs

Note the C examples above used a Matrix ... whereas ... this C++ example uses an adjacency list.


Code: [Select]
// bfs_vs_dfs.cpp //  // 2014-12-06 //  // use a C++11 compiler //

// Note: this program is an attempt to demo what was said at link below ... //

// using globals here to keep 'match' simple and close to given code ... //

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

using namespace std;

/*
    http://www.ics.uci.edu/~eppstein/161/960215.html

    With a little care it is possible to make BFS and DFS look almost
    the same as each other ...
    (as similar as, say, Prim's and Dijkstra's algorithms are to each other):

(1)
    bfs(G)
    {
    list L = empty
    tree T = empty
    choose a starting vertex x
    search(x)
    while(L nonempty)
        remove edge (v,w) from start of L
        if w not yet visited
        {
        add (v,w) to T
        search(w)
        }
    }
   
vs

(2)
    dfs(G)
    {
    list L = empty
    tree T = empty
    choose a starting vertex x
    search(x)
    while(L nonempty)
        remove edge (v,w) from end of L
        if w not yet visited
        {
        add (v,w) to T
        search(w)
        }
    }

    search(vertex v)
    {
    visit(v);
    for each edge (v,w)
        add edge (v,w) to end of L
    }

    Both of these search algorithms now keep a list of edges to explore;
    the only difference between the two is that,
    while both algorithms adds items to the end of L,

    BFS removes them from the beginning,
    (which results in maintaining the list as a queue),
   
    while DFS removes them from the end,
    (maintaining the list as a stack).
*/

typedef vector< list < int > > Graph;

// globals used here ... (to keep code closer match to given example)
// construct an empty graph g, (to hold 5 Verticies (5 Nodes) )
Graph G;
list< int > L; // the adjancey list ...
set < int > T; // the (red-black?) Tree (set) to track visited Nodes ... //


ostream& operator << ( ostream& os, const Graph& g )
{
    int size = g.size();
    if( size )
    {
        for( int i = 0; i < size; ++ i )
        {
            for( auto e : g[i] )
                 os << '(' << i << ','<< e << ")  ";
            os << '\n';
        }
    }
    return os;
}

void search( int v )
{
    // visit(v);
    cout << v << ' ';
    T.insert(v);
   
    for( auto e: G[v] ) L.push_back( e );
}

void bfs( int s )
{
    L.clear(); // list L = empty
    T.clear(); // tree T = empty
   
    // choose a starting vertex x ... passed in s at top
   
    search(s);

    while( !L.empty() ) // while(L not empty)
    {
        // remove edge (v,w) from *START* of L
        int target = L.front();
        L.pop_front();
       
        if( !T.count(target) ) // if w not yet visited
        {
            T.insert(target); //add (v,w) to T
           
            search(target);
        }
    }
}

void dfs( int s )
{
    L.clear(); // list L = empty,
    T.clear(); // tree T = empty
   
    // choose a starting vertex x ... passed in s at top
    search(s) ;
   
    while( !L.empty() ) // while(L not empty)
    {
        // remove edge (v,w) from *END* of L
        int target = L.back();
        L.pop_back();

        if( !T.count(target) ) // if w not yet visited
        {
            T.insert(target); //add (v,w) to T

            search(target);
        }
    }
}

int main()
{
    G.resize(5);
   
    // get adjacent nodes for each node in graph ...
    G[0].push_back(1);  // 1 'is reachable' from 0
    G[0].push_back(2);  // 2 'is reachable' from 0

    G[1].push_back(3);  // 3 'is reachable' from 1

    G[2].push_back(1);
    G[2].push_back(3);
    G[2].push_back(4);

    G[3].push_back(4);

    G[4].push_back(4);
   
   
    cout << "Showing Graph G : \n" << G;
   
    for( int i = 0; i < 5; ++ i )
    {
        cout << "\nShowing bfs(" << i << ") : ";
        bfs( i );
        cout << "\nShowing dfs(" << i << ") : ";
        dfs( i );
        cout << "\n";
    }
   
   
    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

« Last Edit: December 10, 2014, 10:40:54 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #5 on: December 08, 2014, 02:08:37 PM »
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: [Select]
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

Check it out:

Code: [Select]
// 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;
}

« Last Edit: December 08, 2014, 02:12:59 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #6 on: December 08, 2014, 02:17:59 PM »
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: [Select]
// 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 );
}
« Last Edit: December 08, 2014, 02:19:57 PM by David »

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #7 on: December 08, 2014, 02:21:54 PM »
Now ... C


Code: [Select]
/* 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.
   
*/

Offline David

  • Hero Member
  • *****
  • Posts: 644
    • View Profile
Re: Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
« Reply #8 on: November 22, 2018, 05:26:44 AM »
This C++ Shortest Path demo uses a heap as a priority queue ... (Instead of set and map as used in C++ version above.)

Code: [Select]
//  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";
    }
}
« Last Edit: November 22, 2018, 05:59:12 AM by David »