Thread: Represent Maze

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    Represent Maze

    How can i represent this maze using a adjacency list.


    Please help.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You need to decide how to label each point, since you cannot simply use a 2D matrix and call it a 1D list. That's probably important, unless you want to presume the list is in a certain order and refers to a maze of a specific size (also possible).

    Using standard C datatypes: an array of structs, the struct would contain the label and a pointer to an array of pointers to adjacent points. You could use linked list instead of either or both arrays.

    Using the C++ STL: use something like a
    Code:
    map<string,vector<string> >
    Here the strings would be labels for the points (eg. "1,3")
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    in the adjacency list representation do i have to have nodes for each square box?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If you're using an adjacency list, then every node in the list represents two square boxes that are connected.

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Yes, the list is a list of each node/point in the maze, together with a list of all it's adjacent nodes. So a C struct might look like:
    Code:
    typedef struct _point {
        char[8] label;
        struct _point *adj[4];
    } point;
    Since in a 2D maze a point can have at most 4 adjacent points. If less, set the remaining pointers in the adj array to NULL. You need an array of these:
    Code:
    point[48];
    in order for it to be a "list". So adj could also be:
    Code:
    int adj[4];
    instead of a pointer array.

    Using the STL will be less efficient, but possibly "easier" -- it depends which syntax you are interested in learning.

    Quote Originally Posted by tabstop View Post
    If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
    That's a different definition of "adjacency list" than the one here:
    http://en.wikipedia.org/wiki/Adjacency_list
    Last edited by MK27; 04-28-2010 at 07:26 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    Yes, the list is a list of each node/point in the maze, together with a list of all it's adjacent nodes. So a C struct might look like:
    Code:
    typedef struct _point {
        char[8] label;
        struct _point *adj[4];
    } point;
    Since in a 2D maze a point can have at most 4 adjacent points. If less, set the remaining pointers in the adj array to NULL.

    Using the STL will be less efficient, but possibly "easier" -- it depends which syntax you are interested in learning.


    That's a different definition of "adjacency list" than the one here:
    Adjacency list - Wikipedia, the free encyclopedia
    You've got that backwards. The adjacency list is what I have; the incidence list is what you are advocating.

    EDIT: I'll quote:
    If the graph is undirected, every entry is a set (or multiset) of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc.
    some texts, such as that of Goodrich and Tamassia, advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex.

  7. #7
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Quote Originally Posted by tabstop View Post
    If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
    I cannot understand , please help.

    How can each node in the list represent two square boxes?

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    You've got that backwards. The adjacency list is what I have; the incidence list is what you are advocating.

    EDIT: I'll quote:
    No, I'll quote:
    In computer science, an adjacency list is a data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, a list of all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an example of this type of representation. Another example is the representation in Cormen et al. in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.
    So, either you are wrong or the people responsible for the wiki article just made all this stuff up.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iamnew View Post
    I cannot understand , please help.

    How can each node in the list represent two square boxes?
    That would just be a list of pairs, one for each edge (not each point). If this is an assignment, I guess you need to resolve the question of how "adjacency list" is defined, tabstop's way (tabstop is no dummy), or the way described in the wikipedia article on it (see above post):

    Adjacency list - Wikipedia, the free encyclopedia

    I just looked this up today, but the definition there is pretty clear, and it is not a list of edge pairs, so...you do need to resolve that. If you do it one way and the other definition is expected, you'll fail.
    Last edited by MK27; 04-28-2010 at 07:39 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by iamnew View Post
    I cannot understand , please help.

    How can each node in the list represent two square boxes?
    Every edge is represented by a pair of "whatever you're calling your boxes" that represent the two ends. You'll need a structure for pairs, or you can use the built-in library std::pair object.
    Last edited by tabstop; 04-28-2010 at 07:41 AM.

  11. #11
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Okay so the graph that i have to define should be a undirected one. Am i correct.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    No, I'll quote:


    So, either you are wrong or the people responsible for the wiki article just made all this stuff up.
    I've only got two references here at home, one of which doesn't mention adjacency lists at all and the other agrees with you (and obviously wiki has both, since we can both quote it). I had thought that the adjacency/incidence list distinction was more common than it apparently is.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by iamnew View Post
    Okay so the graph that i have to define should be a undirected one. Am i correct.
    Undirected would mean you don't care which direction they travel along the edge (i.e. no one-way doors).

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    I've only got two references here at home, one of which doesn't mention adjacency lists at all and the other agrees with you (and obviously wiki has both, since we can both quote it). I had thought that the adjacency/incidence list distinction was more common than it apparently is.
    Hmmm. I suppose this kind of hinges on what the list is for, since the two versions would be useful in different ways. If it's the goal of an assignment, then it has no real purpose beyond that. Hopefully iamnew understands what's going on.

    Quote Originally Posted by iamnew View Post
    Okay so the graph that i have to define should be a undirected one. Am i correct.
    Looks that way to me, yes.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #15
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    oo no i don't understand whats going on . Iam confused with maze representation. can you guys please explain in the most simplest way. Iam kind of a NOOB.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 12:15 PM
  2. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM
  3. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM
  4. Algorithm to walk through a maze.
    By Nutshell in forum C Programming
    Replies: 30
    Last Post: 01-21-2002, 01:54 AM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 03:27 AM