[Solved]: Generate random weighted graphs representing a road network

Problem Detail: 

in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current solution for connecting vertices (and so create an edge) looks like this:

def connectVertices(self, vertexA, vertexB):     vertexA.addNeighbour(vertexB)     vertexB.addNeighbour(vertexA)     weight = randint(1, self.maxDistance)     self.adjacencyMatrix[vertexA.index][vertexB.index] = weight     self.adjacencyMatrix[vertexB.index][vertexA.index] = weight 

I insert a random integer in the adjacency matrix. How ever this can creates graph which can not represent realistic road networks. Example:

Node A has a cost of 1 to B.

Node B has a cost of 1 to C.

Node C has a cost of 60 to A.

Since the cost when travelling over B between A and C is only 2, it does not make much sens to have a cost of 60 for the direct connection between A and C.

(I can not solve this problem by reducing the maximal cost, because I will need to generate large graphs.)

Are there algorithms that solve this problem ?

(Or :Is there maybe a python library which generates random weighted graphs which takes my problem in count ?)

Asked By : Marius Küpper

Answered By : D.W.

One approach is to generate an arbitrary graph $G$ with arbitrary (positive) lengths on each edge. Then, compute all-pairs shortest paths, and build a new fully-connected graph $G'$ where the length of the edge $u \to v$ in $G'$ is equal to the length of the shortest path from $u$ to $v$ in $G$.

The nice thing about this is that you're guaranteed by construction that $G'$ will satisfy the triangle inequality.

If you are happy with generating fully connected graphs, you can then output $G'$ as your random graph. If you don't want the graphs to be fully connected, you could keep only some subset of the edges of $G'$ and delete the rest, then output the result.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52605

 Ask a Question

 Download Related Notes/Documents