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

ignougroup
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

Leave a Reply