0
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! What problem do you want solved? Can you give a self-contained problem statement? What is your definition of "realistic"? What distribution on graphs do you want? It sounds like you want a distribution where all possible outputs satisfy the triangle inequality, but that still leaves open many possible distributions, so it's not clear how you want to select among the many possibilities. Also: Python library recommendations are off-topic here. $\endgroup$ – D.W.♦ Feb 2 '16 at 18:12
  • $\begingroup$ I don't know the kinds of distributions that exist. So part of my question is to suggest me a distribution or to tell me where I can search to find out more about this topic. (Yes it should satisfy the triangle inequality) $\endgroup$ – Marius Küpper Feb 2 '16 at 18:37
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

You can also consider actually generating points in the plane $(x,y)$, and then randomly connect points with weight their distance $\sqrt{|x_1 - x_2| + |y_1 - y_2|}$. Additionally, you can try to not connect two points if your edge has to cross an already existing edge.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.