How can i represent this maze using a adjacency list.
Please help.
Printable View
How can i represent this maze using a adjacency list.
Please help.
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
Here the strings would be labels for the points (eg. "1,3")Code:map<string,vector<string> >
in the adjacency list representation do i have to have nodes for each square box?
If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
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:
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:typedef struct _point {
char[8] label;
struct _point *adj[4];
} point;
in order for it to be a "list". So adj could also be:Code:point[48];
instead of a pointer array.Code:int adj[4];
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:Quote:
Originally Posted by tabstop
http://en.wikipedia.org/wiki/Adjacency_list
You've got that backwards. The adjacency list is what I have; the incidence list is what you are advocating.Quote:
Originally Posted by MK27
EDIT: I'll quote:
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.
Quote:
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.
I cannot understand , please help.Quote:
Originally Posted by tabstop
How can each node in the list represent two square boxes?
No, I'll quote:Quote:
Originally Posted by tabstop
So, either you are wrong or the people responsible for the wiki article just made all this stuff up.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.
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):Quote:
Originally Posted by iamnew
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.
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.Quote:
Originally Posted by iamnew
Okay so the graph that i have to define should be a undirected one. Am i correct.
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.Quote:
Originally Posted by MK27
Undirected would mean you don't care which direction they travel along the edge (i.e. no one-way doors).Quote:
Originally Posted by iamnew
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 tabstop
Looks that way to me, yes.Quote:
Originally Posted by iamnew
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.
Alright, first off, is this for a homework assignment? That's okay, we can still help you, but it makes a big difference with regard to what you are trying to accomplish. I think both those definitions make sense, would serve a purpose, and you could write a program to derive such a thing from a graph which describes a maze.Quote:
Originally Posted by iamnew
If it's not homework, explain why you are doing this. Also: do you understand how to implement a graph in a computer program?
An adjacency list is just a list of all the adjacent squares. So the list for the maze you posted might start ((A0,A1), (A2,A3), (A4,A5), (A1,B1), (A2,B2), (A4,B4), (A5,B5), (A6,B6), (A7,B7), (B0,B1), (B1,B2), ......) Or you can sort by vertex and keep a list, for every square, which other squares are adjacent. So the list for A0 would be (A1); for A1 it would be (A0, B1); for A2 it would be (A3, B2); etc.
Isn't the adjacency list representation the best way of solving the maze problem. Since it requires substantially lesser amount of nodes.
Compared to what? You probably wouldn't be storing actual whatever-you're-using-for-your-squares in your lists, but pointers.Quote:
Originally Posted by iamnew
In any event, you need to work out what your algorithm is for getting through the maze; that will probably suggest a data structure for storing your maze.
If you want to use this to solve the maze, I would think the second kind (a list for each node) would be more useful. Like tabstop says, you need some idea of how you are going to solve the maze.
But if that is your goal (to solve the maze), an adjacency list is probably not necessary at all since that information is encapsulated in a graph structure anyway.
Oh well i have to use a graph representation anyway. Now in the adjacency representation a node is the point at which a decision has to be taken in the maze. So since in the entire maze has only a few decision points only a few nodes are needed.
You're going to have 48 nodes no matter what, since that's how many squares there are.
Sure, but a graph node (for a 2D maze) looks (something) like this:Quote:
Originally Posted by iamnew
It already contains a list of adjacent nodes.Code:struct node {
int ID; // not necessary
struct node *north;
struct node *south;
struct node *east;
struct node *west;
}
Also, you need all the nodes, not just the decision points, or the "decision points" will have no relation.
Why there will be no relation. The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.Quote:
Originally Posted by MK27
How do you know what the "right" decision points are until you solve the maze? If you're going by the unsolved version, every square is then a "decision point".Quote:
Originally Posted by iamnew
>>The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.
Good point. I guess you could describe a maze that way too. It still renders the "adjacency list" question superfluous. I also don't see the point in weighting the edge, unless you are looking for the shortest route. :p
Actually using a weighted edge introduces a form of complication such that I don't think this will be an improvement over graphing all the nodes UNLESS you are thinking of a maze with many long straight corridors. Even then, I don't think it is necessarily better. Maybe.
okay the other way that iam thinking of is using a boolean 2D array. Is this a good method over adjacency matrix? Can i do graph traversals using a boolean 2D array?
A boolean 2D array is an adjacency matrix.
I feel like using a adjacency list and taking nodes as the decision point is not very good because we have to compute the edge value. I like if all the computing is done by the PC.
SO with which representation should go forward? IS it the matrix or list? Iam exhausted now. I feel like giving up.
The data structures are not going to matter a great deal -- how are you going to get the maze into the program? (Do you have to parse a file, read a list of vertices, ???) How are you going to solve the maze? Those are the only questions that matter, and you appear to have not started on them.
Oh yeah good point. I think i will be able to read the maze from a text file as it is. Afterwards it has to be converted to adjacency matrix notation. How to do that?Quote:
Originally Posted by tabstop
You do that as you read it in. How you do it depends on how the maze is represented in the file.Quote:
Originally Posted by iamnew
say this is the maze in the text file
S - Start F- FinishCode:Soxxxxooooooxxxx
oooooooooooxoxxo
xooooooxxxxoooox
xoxxxoxoooooooox
xxxoooxoooxxxxox
ooooxxxxoooxooox
oxoooxoooooxooox
oxoooxooooxooooo
oxoooxxxxoxoxooo
oxoooxooooxxxxxo
xxxxoxxxxoxooxoo
oooooxoooooooxoo
oxooooooxxxxxxoo
oxxxxooooxxooooo
ooxoooooxoxoxxxx
oooooxxxooxooooF
Now once i read it and put it into a 2D array i get is the same thing
This will not be a adjacency matrix
How can i resolve this issue.
To build an adjacency matrix you have to
- figure out how many squares there are in the maze
- make a 2D matrix that is that many on each side
- Using the text, decide which squares are connected
- Put a 1 in the appropriate places in the adjacency matrix
- Make a note of starting node and finishing node
- Use whatever algorithm you feel appropriate to solve the maze
- Print the solution, making conversions from internal representation to user representation
How do i represent walls?
You don't. An adjacency matrix only stores the places you can move to. (EDIT: To be more clear, a 0 in the adjacency matrix means you can't get from point A to point B, for whatever reason, whether it's a wall, or because the two squares aren't next to each other.)Quote:
Originally Posted by iamnew
okay then the no of movable nodes = total no of nodes - no of walls
am i correct?