Implementing maxflow algorithm with a hashmap instead of adjacency matrix

Question

I was trying to save some space by using a hashmap to represent a graph instead of adjacency matrix, I ran the same snippet using adjacency matrix, and everything worked fine, But as soon as I changed the data structure to a hashmap, it ran into in infinite loop, The infinite loop is because of the bsf function defined which returns a boolean value and more specifically the error is in line : if ((!visited[v]) && (rGraph[make_pair(u, v)] > 0)) somehow this if condition is not working fine while I represent the rGraph as a hashmap.

I would also like to know if using a hashmap to represent the graph is a preferred way ?

Here is the attached code:

bool bfs(map<pair<int, int>, int> rGraph, int s, int t, int parent[])
{

    // Create a visited array and mark all vertices as not visited
    bool visited[V];
    memset(visited, 0, sizeof(visited));

    // Create a queue, enqueue source vertex and mark source vertex
    // as visited
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    // Standard BFS Loop
    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v=0; v<V; v++)
        {
            cout << "Value of graph at: " <<u << "  , " << v << " : " << rGraph[make_pair(u, v)] << "\n";
            //cout << "!visited[v] : " << (!visited[v]) << "rGraph[u][v] : " << rGraph[make_pair(u, v)] << "\n";
            cout << "if condition :  " << ((!visited[v]) && (rGraph[make_pair(u, v)] > 0)) << "\n";
            if ((!visited[v]) && (rGraph[make_pair(u, v)] > 0))
            {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }

    // If we reached sink in BFS starting from source, then return
    // true, else false
    return (visited[t] == true);
}

// Returns tne maximum flow from s to t in the given graph
int fordFulkerson(map<pair<int, int> , int> graph , int s, int t)
{
    int u, v;

    // Create a residual graph and fill the residual graph with
    // given capacities in the original graph as residual capacities
    // in residual graph
    map<pair<int, int>, int>rGraph; // Residual graph where rGraph[i][j] indicates
    // residual capacity of edge from i to j (if there
    // is an edge. If rGraph[i][j] is 0, then there is not)
    for (u = 0; u < V; u++){
        for (v = 0; v < V; v++){
            rGraph[make_pair(u, v)] = graph[make_pair(u, v)];
        }
    }

    int parent[V];  // This array is filled by BFS and to store path

    int max_flow = 0;  // There is no flow initially

    // Augment the flow while tere is path from source to sink
    while (bfs(rGraph, s, t, parent))
    {
        // Find minimum residual capacity of the edhes along the
        // path filled by BFS. Or we can say find the maximum flow
        // through the path found.
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, int(rGraph[make_pair(u, v)]));
        }

        // update residual capacities of the edges and reverse edges
        // along the path
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[make_pair(u, v)] -= path_flow;
            rGraph[make_pair(u, v)] += path_flow;
        }

        // Add path flow to overall flow
        max_flow += path_flow;
    }

    // Return the overall flow
    return max_flow;
}

int main(){
    map< pair<int, int>, int > graph;
    graph[make_pair(0, 1)] = 16;
    graph[make_pair(0, 2)] = 13;
    graph[make_pair(1, 2)] = 10;
    graph[make_pair(1, 3)] = 12;
    graph[make_pair(2, 1)] = 4;
    graph[make_pair(2, 4)] = 14;
    graph[make_pair(3, 2)] = 9;
    graph[make_pair(3, 5)] = 20;
    graph[make_pair(4, 3)] = 7;
    graph[make_pair(4, 5)] = 4;*/


    cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5) << "\n";

return 0;
}

And the adjacency matrix looks like :

int graph[V][V] = { {0, 16, 13, 0, 0, 0},
                    {0, 0, 10, 12, 0, 0},
                    {0, 4, 0, 0, 14, 0},
                    {0, 0, 9, 0, 0, 20},
                    {0, 0, 0, 7, 0, 4},
                    {0, 0, 0, 0, 0, 0}};

Answer 1

You should use the count or find methods to check existence of items in the map, instead of the operator [] because it constructs a new item if it doesn't exist. So change

rGraph[make_pair(u, v)]>0

with

rGraph.count(make_pair(u, v))>0

Also, I might suggest passing any large object (such as the map) by reference. Also, as mentioned here, you can use "unordered_map" which is a hash table, instead of "map" which is a tree, since you don't need the map to be ordered.

Answer 2

First, just by looking at your code - you are not using hashmap - you are using map (read: red-black tree in most implementations). Equivalent of "hashmap" would be unordered_map. However, if you want to save memory - you have chosen the right container (unordered_map may consume more memory than map - unordered_map (hashmap) requires continuous region of memory for buckets: and of course all buckets are never occupied).

And now to problems: When you do rGraph[make_pair(u, v)] you are potentially creating a new element in your map. Indexing operator returns (see cppreference):

• reference to an existing element pointed by the index make_pair(u, v)
• if the element pointed by make_pair(u, v) does not exist - it creates a new element under that index and returns you the reference to that new element.

If you want to check whether an element exists in the map / unordered_map you have to use the find method:

auto p = make_pair(u, v)];
auto iter = rGraph.find(p);
if(iter != rGraph.end())
{//element 'rGraph[p]' exists
}
else
{//element 'rGraph[p]' does not exist
}

You can also combine (potentially) inserting new element with checking whether the new element was actually created - this is usually more efficient than two separate insert and find (see cppreference):

auto p = make_pair(u, v)];
auto res = rGraph.insert(make_pair(p,1)); //insert value '1'
if(res.second)
{//new element was inserted
}
else
{//element already existed
}
//here res.first is an iterator pointing to the element rGraph[p] - newly inserted or not