CODEWITHSUNDEEP
algorithmgraphgraph-theorydijkstra
user1655719
user1655719

Reputation:

Finding out paths in a graph of 175K nodes

I am facing a problem in big data analysis, where I am finding out paths using Dijkstras algorithm for a graph with more than 175K nodes. But the problem is that I do not know for a particular source and destination if a path exists or not. I have to do this for about 1000 sources and destinations. But I cannot pick them randomly, as I am not sure if a path exists between them or not. I am not sure how to handle this. One execution of algorithm in MapReduce enviorment take about 15 mins time locally. So, trial and error is not an option. Only we I can find about at least 1000 sources and destinations is to find cycles(?) or strongly connected components? Is this correct ? I hope my problem is clear to understand.

I am basically looking for finding say 1000 pairs of sources and destinations for which a path exists in a graph of that size

Upvotes: 3

Views: 227

Answers (3)

Travelling Salesman
Travelling Salesman

Reputation: 2281

Here's an algorithm that I suggest:

findPairsPath ()
{
    define 2D Array SD //holds source-destination nodes
    SD = {}
    pick any node u randomly
    k=0

    while (k<1000)
    {
       DFS (u, k)
       pick any node u randomly not stored in SD 
    }
}

DFS (u, k)
{

    for all nodes v adjacent to u and not stored in SD
     {
       store (u,v) in SD //storing a source and a destination
       k++
       DFS (v,k)

     }

}

Upvotes: 0

Jun HU
Jun HU

Reputation: 3314

We can use a data-structure like disjoint-union-set(DUS). We do a initialization to get the connectivity of whole graph. If a can reach b, they will located in same set in the DUS. The complexity of the initialization is all depend on the number of edges in the graph. And the query is about O(1).

Upvotes: 3

Sam Mussmann
Sam Mussmann

Reputation: 5993

I would suggest randomly picking 1000 source nodes, and then for each node run Breadth-First-Search until you've visited k nodes. Then, pick the next node that you would visit and set that as the destination for that source.

With this method, you're guaranteed that each destination is reachable from that source.

Upvotes: 4

Related Questions