Easier question: Let’s say you have a single node in this graph of 10100 nodes. You want to figure out where that single node should be embedded in your 100-dimensional space, but you only care about its embedding location relative to a few specific other nodes.
You have the following affordances:
List the edges that originate at a node. The edges will always be returned in the same order for the same node, but the order is not necessarily the same for different nodes (i.e. the first edge may point along the 57th axis for one node and in the 22nd axis for a different node)
Given an edge, retrieve the node at the far end of that edge
Compare two nodes to see if they are the same node as each other
That is to say, if you have the following problem definition
import random
class Node:
key = None
edges = None
def __init__(self):
self.edges = []
class Edge:
_src = None
_get_dst = None
_dst = None
def __init__(self, src, get_dst):
self._src = src
self._get_dst = get_dst
def get_dst(self):
if self._dst is None:
self._dst = self._get_dst()
return self._dst
class Graph:
def __init__(self, axis_length, n_dims):
self.axis_length = axis_length
self.n_dims = n_dims
self._nodes = {}
self._next_node_id = 1
def get_node_at(self, coords):
axis_order = list(range(self.n_dims))
random.shuffle(axis_order)
if coords not in self._nodes:
node = Node()
node.key = self._next_node_id
self._next_node_id += 1
for axis in axis_order:
if coords[axis] == 0:
continue
dst_coords = list(coords)
dst_coords[axis] -= 1
dst_coords = tuple(dst_coords)
def make_edge(dst_coords):
def get_dst():
return self.get_node_at(list(coords))
return Edge(node, lambda: self.get_node_at(dst_coords))
edge = make_edge(dst_coords)
node.edges.append(edge)
self._nodes[coords] = node
return self._nodes[coords]
def get_random_node(self):
return self.get_node_at(tuple([random.randint(0, self.axis_length-1) for _ in range(self.n_dims)]))
and you want a function which will take an arbitrary node and give you the coordinates of that node in a consistent basis in finite time with arbitrarily high probability of correctness
class ComputedBasis:
def __init__(self):
self.node_positions_by_key = {}
def get_coords(node):
# Given a node, give the coordinates of that node in some
# consistent basis
pass
I claim that this is indeed possible to do, and the steps to do it look nothing like “compute 10100 things”.
Edit: To be explicit about the motivation, once we define this function, we can find a path from our position to the sandwich using something like
def path_to_sandwich(my_node, sandwich_node):
basis = ComputedBasis()
my_coords = basis.get_coords(my_node)
sandwich_coords = basis.get_coords(sandwich_node)
for axis, (my_pos, sandwich_pos) in zip(my_coords, sandwich_coords):
if my_pos < sandwich_pos:
raise(f"""
Can't get to sandwich from here!
I can only travel towards the origin on each axis.
axis: {axis}
my_pos: {my_pos}
sandwich_pos: {sandwich_pos}
""")
return get_path(basis, my_node, sandwich_node)
def get_path(basis, start_node, goal_node):
curr_node = start_node
path = [curr_node]
goal_coords = basis.get_coords(goal_node)
while curr_node != goal_node:
curr_coords = basis.get_coords(curr_node)
# Find the first axis where we need to move towards the goal along that axis.
for axis, (curr_pos, goal_pos) in zip(cur_coords, goal_coords):
if curr_pos > goal_pos:
step_coords = [p for p in curr_pos]
step_coords[axis] -= 1
step_coords = tuple(step_coords)
break
for edge in curr_node.edges:
dst_node = edge.get_dst()
dst_coords = basis.get_coords(dst_node)
if dst_coords == step_coords:
step_node = dst_node
break
curr = step_node
path.append(curr)
return path
Note that my framing of the problem is slightly different, in that (0, 0, 0, ..., 0, 0, 0) is the point from which there are no outbound edges, rather than (10, 10, 10, ..., 10, 10, 10) in your version. Doesn’t really make a difference logically, just makes the code more readable.
Thanks faul-sname. I came to the comments to give a much lower effort answer along the same lines, but yours is better.
My answer: lazy local evaluations of nodes surrounding either your current position or the position of the goal. So long as you can estimate a direction from yourself to the goal, there’s no need to embed the whole graph. This is basically gradient descent...
Fun side note: in this particular example, it doesn’t actually matter how you pick your direction. “Choose the axis closest to the target direction” performs exactly as well as “choose any edge which does not make the target node unreachable when traversed at random, and then traverse that edge” or “choose the first edge where traversing that edge does not make the target node unreachable, and traverse that edge”.
Edit: at least assuming that the graph is directed
I might not understand exactly what you are saying. Are you saying that the problem is easy when you have a function that gives you the coordinates of an arbitrary node? Isn’t that exactly the embedding function? So are you not therefore assuming that you have an embedding function?
I agree that once you have such a function the problem is easy, but I am confused about how you are getting that function in the first place. If you are not given it, then I don’t think it is super easy to get.
In the OP I was assuming that I have that function, but I was saying that this is not a valid assumption in general. You can imagine you are just given a set of vertices and edges. Now you want to compute the embedding such that you can do the vector planning described in the article.
I agree that you probably can do better than 10100 though. I don’t understand how your proposal helps though.
Do you want me to spoil it for you, do you want me to drop a hint, or do you want to puzzle it out yourself? It’s a beautiful little puzzle and very satisfying to solve. Also note that the solution I found only works if you are given a graph with the structure above (i.e. every node is part of the lattice, and the lattice is fairly small in each dimension, and the lattice has edges rather than wrapping around).
Easier question: Let’s say you have a single node in this graph of 10100 nodes. You want to figure out where that single node should be embedded in your 100-dimensional space, but you only care about its embedding location relative to a few specific other nodes.
You have the following affordances:
List the edges that originate at a node. The edges will always be returned in the same order for the same node, but the order is not necessarily the same for different nodes (i.e. the first edge may point along the 57th axis for one node and in the 22nd axis for a different node)
Given an edge, retrieve the node at the far end of that edge
Compare two nodes to see if they are the same node as each other
That is to say, if you have the following problem definition
and you want a function which will take an arbitrary node and give you the coordinates of that node in a consistent basis in finite time with arbitrarily high probability of correctness
I claim that this is indeed possible to do, and the steps to do it look nothing like “compute 10100 things”.
Edit: To be explicit about the motivation, once we define this function, we can find a path from our position to the sandwich using something like
Note that my framing of the problem is slightly different, in that
(0, 0, 0, ..., 0, 0, 0)is the point from which there are no outbound edges, rather than(10, 10, 10, ..., 10, 10, 10)in your version. Doesn’t really make a difference logically, just makes the code more readable.Thanks faul-sname. I came to the comments to give a much lower effort answer along the same lines, but yours is better. My answer: lazy local evaluations of nodes surrounding either your current position or the position of the goal. So long as you can estimate a direction from yourself to the goal, there’s no need to embed the whole graph. This is basically gradient descent...
Fun side note: in this particular example, it doesn’t actually matter how you pick your direction. “Choose the axis closest to the target direction” performs exactly as well as “choose any edge which does not make the target node unreachable when traversed at random, and then traverse that edge” or “choose the first edge where traversing that edge does not make the target node unreachable, and traverse that edge”.
Edit: at least assuming that the graph is directed
I might not understand exactly what you are saying. Are you saying that the problem is easy when you have a function that gives you the coordinates of an arbitrary node? Isn’t that exactly the embedding function? So are you not therefore assuming that you have an embedding function?
I agree that once you have such a function the problem is easy, but I am confused about how you are getting that function in the first place. If you are not given it, then I don’t think it is super easy to get.
In the OP I was assuming that I have that function, but I was saying that this is not a valid assumption in general. You can imagine you are just given a set of vertices and edges. Now you want to compute the embedding such that you can do the vector planning described in the article.
I agree that you probably can do better than 10100 though. I don’t understand how your proposal helps though.
Do you want me to spoil it for you, do you want me to drop a hint, or do you want to puzzle it out yourself? It’s a beautiful little puzzle and very satisfying to solve. Also note that the solution I found only works if you are given a graph with the structure above (i.e. every node is part of the lattice, and the lattice is fairly small in each dimension, and the lattice has edges rather than wrapping around).