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 ?)