By having a list with mazes houses(2 dimensions), how do i create a directed graph with a dictionary

I can only make an undirected gr开发者_如何学运维aph. no idea on how i can make a directed one.

Any idea?

---

Apologies for the rather long winded post. I had time to kill on the train.

I'm guessing what you're after is a directed graph representing all paths leading away from your starting position (as opposed to a graph representation of the maze which once can use to solve arbitrary start/end positions).

(No offence meant, but) this sounds like homework, or at least, a task that is very suitable for homework. With this in mind, the following solution focuses on simplicity rather than performance or elegance.

Approach

One straight-forward way to do this would be to first store your map in a more navigable format, then, beginning with the start node do the following:

1. look up neighbours (top, bottom, left, right)
2. for each neighbour:
   • if it is not a possible path, ignore
   • if we have processed this node before, ignore
   • else, add this node as an edge and push it a queue (not a stack, more on this later) for further processing
3. for each node in the queue/stack, repeat from step 1.

(See example implementation below)

At this point, you'll end up with a directed acyclic graph (DAG) with the starting node at the top of the tree and end node as one of the leaves. Solving this would be easy at this point. See this answer on solving a maze representing as a graph.

A possible optimisation when building the graph would be to stop once the end point is found. You'll end up with an incomplete graph, but if you're only concerned about the final solution this doesn't matter.

stack or queue?

Note that using a stack (first in last out) would mean building the graph in a depth-first manner, while using a queue (first in first out) would result in a breadth-first approach.

You would generally want to use a queue (breadth first if the intention is to look for the shortest path. Consider the following map:

       START
########   ###### 
########   ######
### b    a ######  
###   ##   ######
###   ## e ######
### c    d ######
########   ######
########      END
#################

If the path is traversed depth-first and at branch a you happen take the a->b path before a->e, you end up with the graph:

 START
   |
   a
  / \
 b   e   <-- end, since d already visited
 |
 c
 |
 d
  \
   END

However, using a breadth-first approach the a->e path would come across node d earlier, resulting in a shorter graph and a better solution:

 START
   |
   a
  / \
 b   e 
 |   |
 c   d
     |
    END

Example code

Sample input provided:

..........
#########.
..........
.#########
......#...
#####...#.
##...####.
##.#......
...#######

e = (0,0)
s = (8,0)

DISCLAIMER: The following code is written for clarity, not speed. It is not fully tested so there is no guarantee of correctness but it should give you an idea of what is possible.

We assumes that the input file is formatted consistently. Most error checking left out for brevity.

# regex to extract start/end positions
import re
re_sepos = re.compile("""
    ^([se])\s* # capture first char (s or e) followed by arbitrary spaces
    =\s*        # equal sign followed by arbitrary spaces
    \(          # left parenthesis
    (\d+),(\d+) # capture 2 sets of integers separated by comma
    \)          # right parenthesis
""", re.VERBOSE)

def read_maze(filename):
    """
    Reads input from file and returns tuple (maze, start, end)
      maze : dict holding value of each maze cell { (x1,y1):'#', ... }
      start: start node coordinage (x1,y1)
      end  : end node coordinate (x2,y2)
    """
    # read whole file into a list
    f = open(filename, "r")
    data = f.readlines()
    f.close()

    # parse start and end positions from last 2 lines
    pos = {}
    for line in data[-2:]: 
        match = re_sepos.match(line)
        if not match:
            raise ValueError("invalid input file")
        c,x,y = match.groups() # extract values
        pos[c] = (int(x),int(y))
    try:
        start = pos["s"]
        end   = pos["e"]
    except KeyError:
        raise ValueError("invalid input file")

    # read ascii maze, '#' for wall '.' for empty slor 
    # store as maze = { (x1,y1):'#', (x2,y2):'.', ... }
    # NOTE: this is of course not optimal, but leads to a simpler access later 
    maze = {}
    for line_num, line in enumerate(data[:-3]): # ignore last 3 lines
        for col_num, value in enumerate(line[:-1]): # ignore \n at end
            maze[(line_num, col_num)] = value

    return maze, start, end

def maze_to_dag(maze, start, end):
    """
    Traverses the map starting from start coordinate.
    Returns directed acyclic graph in the form {(x,y):[(x1,y1),(x2,y2)], ...}
    """
    dag = {}        # directed acyclic graph
    queue = [start] # queue of nodes to process

    # repeat till queue is empty
    while queue:
        x,y = queue.pop(0)      # get next node in queue
        edges = dag[(x,y)] = [] # init list to store edges

        # for each neighbour (top, bottom, left, right)
        for coord in ((x,y-1), (x,y+1), (x-1,y), (x+1,y)): 
            if coord in dag.keys(): continue   # visited before, ignore

            node_value = maze.get(coord, None) # Return None if outside maze
            if node_value == ".": # valid path found
                edges.append(coord) # add as edge
                queue.append(coord) # push into queue

                # uncomment this to stop once we've found the end point
                #if coord == end: return dag

    return dag

if __name__ == "__main__":
    maze,start,end = read_maze("l4.txt")
    dag = maze_to_dag(maze, start, end)
    print dag

---

This page provides a nice tutorial on implementing graphs with python. From the article, this is an example of a directory graph represented by dictionary:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

That said, you might also want to look into existing graph libraries such as NetworkX and igraph.

---

Since you already have a list, try creating an Adjacency Matrix instead of a dictionary.

list_of_houses = []
directed_graph = [][]
for i in xrange(len(list_of_houses)):
    for i in xrange(len(list_of_houses)):
        directed_graph[i][i] = 0

Then for any new edge from one house to another (or w/e the connection is)

directed_graph[from_house][to_house] = 1

and you're done. If there is an edge from house_a to house_b then directed_graph[house_a][house_b] == 1.