{"id":957,"date":"2019-05-10T16:30:55","date_gmt":"2019-05-10T16:30:55","guid":{"rendered":"http:\/\/tech.avant.net\/q\/?p=957"},"modified":"2019-12-06T04:59:27","modified_gmt":"2019-12-06T04:59:27","slug":"graph-search","status":"publish","type":"post","link":"https:\/\/tech.avant.net\/q\/graph-search\/","title":{"rendered":"Graph Search"},"content":{"rendered":"\n

I would like to discover paths between two nodes on a graph. Let’s say we have a graph that looks something like this:<\/p>\n\n\n\n

graph = {1: set([2, 3]),\n         2: set([1, 4, 5, 7]),\n         3: set([1, 6]),\n         ...\n         N: set([...] }<\/pre>\n\n\n\n
The graph<\/em> object contains a collection of nodes and their corresponding connections. If it’s a bi-directional graph, those connections would have to appear in the corresponding sets (e.g., 1: set([2]) and 2: set([1])).<\/p>\n\n\n\n
Traversing this kind of data structure can be done through recursion, usually something like this:<\/p>\n\n\n\n
def find_paths(from_node, to_node, graph, path=None):\n    ''' DFS search of graph, return all paths between\n        from_node and to_node\n    '''\n    if path is None:\n        path = [from_node]\n    if to_node == from_node:\n        return [path]\n    paths = []\n    for next_node in graph[from_node] - set(path):\n        paths += find_paths(next_node, to_node, graph, path + [next_node])\n    return paths<\/pre>\n\n\n\n
Unfortunately, for large graphs, this can be pretty inefficient, requiring a full depth-first search (DFS), and storing the entire graph in memory. This does have the advantage of being exhaustive, finding all unique paths between two nodes.<\/p>\n\n\n\n
That said, let’s say we want to find the shortest possible path between two nodes. In those cases, you want a breadth-first search (BFS). Whenever you hear the words “shortest path”, think BFS. You’ll want to avoid recursion (as those result in a DFS), and instead rely on a queue, which in Python can be implemented with a simple list.<\/p>\n\n\n\n
def find_shortest_path(from_node, to_node, graph):\n    ''' BFS search of graph, return shortest path between\n        from_node and to_node\n    '''\n    queue = [(from_node, [from_node])]\n    while queue:\n        (qnode, path) = queue.pop(0) #deque\n        for next_node in graph[qnode] - set(path):\n            if next_node == to_node:\n                return path + [next_node]\n            else:\n                queue.append((next_node, path + [next_node]))<\/pre>\n\n\n\n
Because a BFS is guaranteed to find the shortest path, we can return the moment we find a path between to_node<\/em> and from_node<\/em>. Easy!<\/p>\n\n\n\n
In some cases, we may have an extremely large graph. Let’s say you’re searching the Internet for a path between two unrelated web pages, and the graph is constructed dynamically based on scraping the links from each explored page. Obviously, a DFS is out of the question for something like that, as it would spiral into an infinite chain of recursion (and probably on the first link).<\/p>\n\n\n\n
As a reasonable constraint, let’s say we want to explore all the links up to a specific depth. This could be done easily. Simply add a depth_limit<\/em>, as follows:<\/p>\n\n\n\n
def find_shortest_path(from_node, to_node, graph, depth_limit=3):\n    queue = [(from_node, [from_node])]\n    while queue and depth_limit > 0:\n        depth_limit -= 1\n        (qnode, path) = queue.pop(0) #deque\n        for next_node in graph[qnode] - set(path):\n            if next_node == to_node:\n                return path + [next_node]\n            else:\n                queue.append((next_node, path + [next_node]))\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
I would like to discover paths between two nodes on a graph. Let’s say we have a graph that looks something like this: The graph object contains a collection of nodes and their corresponding connections. If it’s a bi-directional graph, those connections would have to appear in the corresponding sets (e.g., 1: set([2]) and 2: […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[6,22],"tags":[],"_links":{"self":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/957"}],"collection":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/comments?post=957"}],"version-history":[{"count":5,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/957\/revisions"}],"predecessor-version":[{"id":962,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/posts\/957\/revisions\/962"}],"wp:attachment":[{"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/media?parent=957"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/categories?post=957"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tech.avant.net\/q\/wp-json\/wp\/v2\/tags?post=957"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}