Search code examples
pythonrandomgraphtraversalweighted

Weighted Random Graph Traversal in Python

Basically, I have a 300 by 250 area that I want to randomly move about. However, there are areas of interest at points 18750 and 9300 (you can figure out x,y by doing y = 0 while(num > x): num = num - x y += 1 and you'll get the coordinates). Anyway, so if the starting point is (0,0), I want to be able to randomly move about the area but kind of move in the general area of the two given points. Maybe one has a stronger pull so even if the node traversal leads to the weaker one, it will, with enough time, end up at the one with stronger pull.

So far, I have this in order to create my graph and create my vertices and edges. It gives me a 300x250 space with each node connected vertically and horizontally. `

from igraph import *
g = Graph()
x = 300
y = 250
g.add_vertices(x*y)
li = []

for i in range(x-1):
    for j in range(y):
        li.append((i+j*x, i+1+j*x))
for i in range(x):
    for j in range(y-1):
        li.append((i+j*x, i+x+j*x))

g.add_edges(li)

gravity_points = [18750, 9300]
final_point = 24900

` How can I go about this? I want to have the traveling node have to make a choice at every resting node but the probability of it traveling in any direction being completely dependent on the weights of the gravity points. So it might have a 10% chance to go left, a 10% chance to go right, a 50% chance to go down and a 30% chance to go up. Something like that. The probabilities don't have to change with proximity but rather with the direction the gravity points are in.

Any help is welcome!! Thank you in advance.

Solution

  • Not sure, but perhaps your problem is not to find the algorithm but how to use igraph in this context. Which is tricky because it doesn't seem to be adding anything to this requirement. I will start with describing the algorithm: hopefully that will help you tighten your question until we can get to an answer.

    The random traversal is going to look like this, in pseudo-code:

    traveller_node = start_node  # Chosen somehow

while not stopping_condition(traveller_node):
    possible_successors = traveller_node.successors()
    traveller_node = random_choice_from(possible_successors)

    In this case, the simplest approach is to represent each node, including the traveller node, by its x,y coordinates. The successors function does not need to depend on the graph since there are generally four options, except at the edge of the rectangle. So then we can code up your problem pretty directly:

    traveller_x,traveller_y = 10,10  # Or whatever you want

while not at_gravity_points(traveller_x,traveller_y):
    directions = ["left","right","up","down"]
    if traveller_x == 0:
        directions.remove("left")
    if traveller_x == x:
        directions.remove("right")
    if traveller_y == 0:
        directions.remove("down")
    if traveller_y == y:
        directions.remove("up")

    to_gravity_point_1 = []
    if traveller_x < gravity_point_1_x:
        to_gravity_point_1.append("right")
    elif traveller_x > gravity_point_1_x:
        to_gravity_point_1.append("left")
    if traveller_y < gravity_point_1_y:
        to_gravity_point_1.append("up")
    elif traveller_y > gravity_point_1_y:
        to_gravity_point_1.append("down")

    # ... do the same to construct to_gravity_point_2
    # then use these two lists to construct your weighting scheme
    # then use random.random() to choose a direction from directions
    # according to that weighting.

    if direction == "left":
        traveller_x -= 1
    elif direction == "right":
        traveller_x += 1
    elif direction == "up":
        traveller_y += 1
    elif direction == "down":
        traveller_y -= 1

    This is all so straightforward that I don't really think it is what you were asking. So, maybe your question is how to do this using the features of igraph? In which case, my preferred answer is "why?"

    But, to make an effort, you could do something like this. First augment your graph with weights. Do this by iterating over all the vertices and, for each one, compare their x and y to the x and y of the gravity points. Use these comparisons to construct weights for their outgoing edges and store them using the weighted graph functionality in igraph.

    Then define the traveller node to be an igraph.Vertex.

    Then repeatedly:

    Use the igraph successor function on that vertex to find the possible successors. Use the igraph weight lookup to find the weights. Use random.random() to choose between them according to the weights. Change the traveller node to the chosen successor.

    In algorithmic terms, the only difference here is that we pre-calculate the weights rather than doing it on demand.