Searching, graphs, trees... aargh!
Hi,
I am having a bit of a problem and would love some pointers. This is what I need to do:
I need to create a bi-directional graph. The nodes are cities, the links are roads. The data is read in from a text file, and I have classes for the cities and the roads. I am currently storing all of the roads in a Vector. The places file is only really used for heuristics later.
(Yes I know Vector is slow compared to say ArrayList but this is what I learned years ago and for now I just want to get something working).
When I apply the search, I am meant to build a tree dynamically as the search goes. So I start with the origin City. Say it's depth first, I then get all the cities it joins to, do down the first one, get its cities, etc. I also need to keep track of the resultant path (currently using a stack). But I need some neat search tree that will work for depth first, breadfirst, hill climbing, A* among others. Also, some cities link to lots of cities so I can't use a binary tree.
If anyone could give me ideas of where to head, I would be so happy! I don't need any graphics in this code, the program can be command line based.
Thanks!
[1193 byte] By [
Steve_wa] at [2007-10-2 17:15:28]
number all your cities
build an array (or ArrayList or Vector) of that size. call it connectsTo
at each slot in the array create an ArrayList (or a Vector or an array)
put all the roads in this structure ( for each road (A,B) go to slot A and add B also go to slot B and add A)
Now given any city it is easy to find all cities that connectsTo that city and it is easy to iterate through all possible choices. IF you want, you can sort each of little arrays by length of road. This may help later processing.
this connectsTo structure is your tree/bi-directional graph. We added each node twice for searching convenience. Since you don't know what kind of search you are going to do (A* among others) I leave you to your own devices for that.
BTW - unless you are doing something unusual with your Vectors, I would bet that you can change them all to ArrayLists and not have to change a single other thing. Both of them support the add(Object o) method, both support the get(int index) method. The fact that you learned something once should not be an impedement to learning something new. Learning about ArrayLists should take you all of maybe 5 minutes. You look at the ArrayList API and say to yourself, "hmm these are just like vectors - piece o' cake."
