Function adjacency

pattern/graph/__init__.py:753–784

Returns a dictionary indexed by node id1's, in which each value is a dictionary of connected node id2's linking to the edge weight. If directed=True, edges go from id1 to id2, but not the other way. If stochastic=True, all the weights for the neighbors of a given node sum to

(graph, directed=False, reversed=False, stochastic=False, heuristic=None)

#--- GRAPH THEORY ----------------------------------------------------------------------------------

def adjacency(graph, directed=False, reversed=False, stochastic=False, heuristic=None):
    """ Returns a dictionary indexed by node id1's,
        in which each value is a dictionary of connected node id2's linking to the edge weight.
        If directed=True, edges go from id1 to id2, but not the other way.
        If stochastic=True, all the weights for the neighbors of a given node sum to 1.
        A heuristic function can be given that takes two node id's and returns
        an additional cost for movement between the two nodes.
    """
    # Caching a heuristic from a method won't work.
    # Bound method objects are transient, 
    # i.e., id(object.method) returns a new value each time.
    if graph._adjacency is not None and \
       graph._adjacency[1:] == (directed, reversed, stochastic, heuristic and heuristic.func_code):
        return graph._adjacency[0]
    map = {}
    for n in graph.nodes:
        map[n.id] = {}
    for e in graph.edges:
        id1, id2 = not reversed and (e.node1.id, e.node2.id) or (e.node2.id, e.node1.id)
        map[id1][id2] = 1.0 - 0.5 * e.weight
        if heuristic:
            map[id1][id2] += heuristic(id1, id2)
        if not directed: 
            map[id2][id1] = map[id1][id2]
    if stochastic:
        for id1 in map:
            n = sum(map[id1].values())
            for id2 in map[id1]: 
                map[id1][id2] /= n
    # Cache the adjacency map: this makes dijkstra_shortest_path() 2x faster in repeated use.
    graph._adjacency = (map, directed, reversed, stochastic, heuristic and heuristic.func_code)
    return map

def dijkstra_shortest_path(graph, id1, id2, heuristic=None, directed=False):
    """ Dijkstra algorithm for finding the shortest path between two nodes.