main.cpp
// Generates a random directed graph that ensures there exists some s-t path, where
// s is node 0 and t is node numVxs - 1. 
Generates a random directed graph that ensures there exists some s-t path, where
s is node 0 and t is node numVxs - 1.
Generates a random directed graph that ensures there exists some s - t path where s is node 0 and t is node numVxs - 1 .
Graph *generateGraph(int numVxs, int numEdges, int maxCap) {
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->n = numVxs;
    g->capacities = (int *)calloc((numVxs * numVxs), sizeof(int));
    std::vector<int> path;
    for (int i = 1; i < numVxs; i++) {
        path.push_back(i);
    }
    std::random_shuffle(path.begin(), path.end());
    int t = numVxs - 1;
    int first = path.at(0);
    int capacity = (rand() % (maxCap - 1)) + 1;
    g->capacities[IDX(0, first, g->n)] = capacity;
    int remaining = numEdges - 1;
    int last = first;
    for (auto it = (path.begin()++); ((it != path.end()) && (*it != t)); it++) {
        capacity = (rand() % (maxCap - 1)) + 1;
        g->capacities[IDX(last, (*it), g->n)] = capacity;
        last = *it;
        remaining--;
    }
    capacity = (rand() % (maxCap - 1)) + 1;
    g->capacities[IDX(last, t, g->n)] = capacity;
    remaining--;
    for (int i = 0; i < remaining; i++) {
        capacity = (rand() % (maxCap - 1)) + 1;
        int j = rand() % g->n;
        int k = rand() % g->n;
        if (j != k) {
            g->capacities[IDX(j, k, g->n)] = capacity;
        }
    }
    return g;
}
Graph * generateGraph ( int numVxs , int numEdges , int maxCap ) { Graph * g = ( Graph * ) malloc ( sizeof ( Graph ) ) ; g -> n = numVxs ; g -> capacities = ( int * ) calloc ( ( numVxs * numVxs ) , sizeof ( int ) ) ; std :: vector < int > path ; for ( int i = 1 ; i < numVxs ; i ++ ) { path . push_back ( i ) ; } std :: random_shuffle ( path . begin ( ) , path . end ( ) ) ; int t = numVxs - 1 ; int first = path . at ( 0 ) ; int capacity = ( rand ( ) % ( maxCap - 1 ) ) + 1 ; g -> capacities [ IDX ( 0 , first , g -> n ) ] = capacity ; int remaining = numEdges - 1 ; int last = first ; for ( auto it = ( path . begin ( ) ++ ) ; ( ( it != path . end ( ) ) && ( * it != t ) ) ; it ++ ) { capacity = ( rand ( ) % ( maxCap - 1 ) ) + 1 ; g -> capacities [ IDX ( last , ( * it ) , g -> n ) ] = capacity ; last = * it ; remaining -- ; } capacity = ( rand ( ) % ( maxCap - 1 ) ) + 1 ; g -> capacities [ IDX ( last , t , g -> n ) ] = capacity ; remaining -- ; for ( int i = 0 ; i < remaining ; i ++ ) { capacity = ( rand ( ) % ( maxCap - 1 ) ) + 1 ; int j = rand ( ) % g -> n ; int k = rand ( ) % g -> n ; if ( j != k ) { g -> capacities [ IDX ( j , k , g -> n ) ] = capacity ; } } return g ; }
Generates a random directed graph that ensures there exists some s-t path, where
s is node 0 and t is node numVxs - 1.
Generates a random directed graph that ensures there exists some s - t path where s is node 0 and t is node numVxs - 1 .