Is there a better way to represent a 2-D array?
Dear All,
I am working on a program which can calculate the shortest route for the London Underground.
I have been representing the connection between one station(node) to another station(node) using a 2 dimensional array.
So if station 1 to station 4 takes 5 minutes, then
matrix[1][4]=5 if there is no connection between two station i and station j then matrix[j]=0
SO the matrix will be sparse.
Instead of manually entering each 198 stations, is there a better way to represent this connectivity between stations,and still allowing me to find out that station 1 to station 4 takes 5 minutes?
Or
Is there a way that I can create a class which can generate the matrix for me provide I have given that station1 to station 2 is 4 minutes
station1 to station 3 is 5 minutes
so that it will store these values into the matrix and put matrix[1][j]=0 where j is all index except for 2 AND 3?
PLEASE HELP, I WOULD BE EXTREMELY GRATEFUL
Thank you in advance
KT
[1054 byte] By [
auwy29] at [2007-9-26 4:48:22]
Create the two-dimensional array and run through a double loop initializing each element to zero. Then manually set the elements that are non-zero.Rich
Did you consider using any other datastructures apart from arrays? Or Is arrays the only way you wanted to go?
> Instead of manually entering each 198 stations [...]
it depends on how you get the data. if you have it in a file, then better write a parser. if you have it on a paper ... well you have to do it by hand. A nice way to format the code can be :
int[][] m = {
{ 0, 26, 34, 4, 5, ..., },
{10, 0,3, 7, 5},
[...]
};
But I'll go for an external file: better for maintenance. Internally I think the way you are representing (arrays) is the best, since this data will not going to be modified after loading.
Ummm... Aren't sparce matrices better represented with graphs?
Implementation is pretty straight forward with Vectors, Lists, ArrayLists or just about any classes of the Collections framework. If there is a connection from node 1 to node 2 there is an arc between those nodes, otherwise not. You could have a separate classes for nodes and and arcs - each node has 0 or more arcs and each arc has two nodes and a weight (=the time it takes). In this case the arcs are undirected.
pick up any introductory book on CS for details....
testing
auwy29 at 2007-6-29 18:38:36 >
Hi
Thank You all for the reply.
SO if I want to represent the London Underground network as a Graph how would I be able to do it?
Can anyone just give me an example? SO that I can than expand it.
ie. if I want to say that station A on the central line and station B on the central line is connected with time taken 3minutes and where station A also exist on the Victoria Line and is connected to station C on the Victoria Line with 5 minutes?
Many Thanks
auwy29 at 2007-6-29 18:38:36 >
if I 've understood, you have for instance.
from A to B 5 min
from B to C 4 min
from A to C 9 min
this information is redundant, the third info should be omitted. If you omit it you will only have information for the times to go from one station to the next one. Thus you can:
1. Use a double dimension array, one dimension for every underground line and other for every station in that line. All members are filled and it is not sparse any more, it also will not be as big as the old one.
2. Use a one-dimension array of station object. Each station object will have information of every next station and the line it belongs to.
Then I would use a backtracking algorithm to find all possible routes to reach a destination and then you can easily calculate the time.
Maybe this approach is more complex, but it solves the problem
> SO if I want to represent the London Underground
> network as a Graph how would I be able to do it?
By writing classes of your own or using some one else's. I don't think that the collections framework has out-of-the-box support for graphs.... So try google first.
The implementation details depend on the API you are going to use, of course...
-
> from A to B 5 min
> from B to C 4 min
> from A to C 9 min
>
> this information is redundant, the third info should be omitted.
<nit-picking>
No it's not - What if there's a special, more direct route from A to C? Also, getting from A to B to C will usually take more time than the time from A to B plus the time from B to C. The trains have to stop at B, don't they?
</nit-picking>
> Maybe this approach is more complex, but it solves the problem
Have I understood correctly - isn't what you describe just another way to implement a graph?
my example was for a given route. In that route, the time for being from A to C y A to B + B to C. If you want to add additional times in every station, you can do it without any problem.
If there is another route A-D-C, then you have another time to get from A to C. The idea is to calculate all possible routes (with a backtracking algorith) and pick the one with shorter time
