Algorithms For Dummies

  Considering Heuristics 

     379

    Graph = nx.Graph()

    for j, node in enumerate(letters):

        Graph.add_nodes_from(node)

        x, y = j // 5, j % 5

        x_min = max(0, x-1)

        x_max = min(4, x

+1)+1

        y_min = max(0, y-1)

        y_max = min(4, y

+1)+1

        adjacent_nodes = np.ravel(

            checkboard[x_min:x_max,y_min:y_max])

        exits = np.random.choice(adjacent_nodes,

            size=np.random.randint(1,4), replace=False)

        for exit in exits:

            if exit not in Graph.edge[node]:

                Graph.add_edge(node, exit)

    spacing = np.arange(0.0, 1.0, 0.2)

    coordinates = [[x,y] for x in spacing \

                   for y in spacing]

    position  = {l:c for l,c in zip(letters, coordinates)}

    

    for node in Graph.edge:

        for exit in Graph.edge[node]:

            length = int(round(

                    euclidean_dist(

                        node, exit, position)*10,0))

            Graph.add_edge(node,exit,weight=length)

    if drawing:

        nx.draw(Graph, position, with_labels=True)

        labels = nx.get_edge_attributes(Graph,'weight')

        nx.draw_networkx_edge_labels(Graph, position,

                                     edge_labels=labels)

        plt.show()

    

    return Graph, position

The functions return a NetworkX graph (Graph), a favorite data structure for rep-

resenting graphs, which contains 25 vertexes (or nodes, if you prefer) and a Car-

tesian map of points (position). The vertexes are placed on a 5 x 5 grid, as shown 

in Figure 20-2. The output also applies distance functions and calculates the posi-

tion of vertexes.

graph, coordinates = create_maze(seed=3)

---

380