Meaningless Drivel is fun!*
The moose likes Beginning Java and the fly likes Connection Array into an adjacency Matrix Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Connection Array into an adjacency Matrix" Watch "Connection Array into an adjacency Matrix" New topic
Author

Connection Array into an adjacency Matrix

Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6
Hi there,

I have a 2D array called conArray, which holds values that tell me which nodes are connected to which other nodes.

The format of the array is as follows:

0 1
0 A B
1 B C
2 D E
3 C E

With the numbers representing the location of the characters inside the array.

For example, the first line means that Node A is connected to Node B.

I have been trying to work out of a way of getting these values into an adjacency matrix so that the rows and columns of the matrix represent the characters, and a 1 or 0 is stored in the place when indexed by both of them.

For example, with the array above i would end up with a boolean adjacency matrix that looks like this:

0 1 2 3 4
0 F T F F F
1 T F T F F
2 F T F F T
3 F F F F T
4 F F T T F

where the numbers around the outside represent the characters..(e.g 0=A,1=B)

I can work out the conditional bit of asking whether they connect or not but I have no idea how to put the answer in the right place in the adjacency matrix, if you understand?

Sorry my explaining is a bit poor but many many thanks for any help.
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
In Java, you can create arrays of arrays.

In your case, you could create an array of 5 elements and each element is an array of boolean.

You can use this like a 2-dimensional array, by filling in the first row and first column and then using loops to fill in the rest of the array.

If this isn't clear, let me know.
Yuriy Zilbergleyt
Ranch Hand

Joined: Dec 13, 2004
Posts: 429
Well the matrix would just be an array of arrays, right? Then there are two simple ways of doing this:

1. Initialize the matrix to be all "F". Then go through every single connection and populate the correct places with "T".

2. The matrix starts empty. Have a nested for-loop go through every space in the matrix and check the connections array to see whether or not that spot should be populated, and put the correct value in the space.

Hope this helps,
Yuriy
Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6
Thanks for all your help!

My main problem however is how to place the T in the right place.

For example, if A is connected to B. I need to put a T in the adjacency matrix at [0][1] or [1][0]

How do i convert these letters into places without a long winded method?

Thanks again!
Yuriy Zilbergleyt
Ranch Hand

Joined: Dec 13, 2004
Posts: 429
For example, if A is connected to B. I need to put a T in the adjacency matrix at [0][1] or [1][0]


If you mean "which one to use" you have to decide that for yourself, just be consistent. Do you want [0][1] to represent "1 across, 0 down" or "0 down, 1 across"?

If you mean "what number represents B", just subtract the number 65 from the character 'B'. Make sure you use capital letters. I'd put the conversion code into a seperate method.

Yuriy
[ May 02, 2006: Message edited by: Yuriy Zilbergleyt ]
Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6
I don't actually mind which one it goes in. I just mean how do I get A to represent 0, and B to represent 1 etc etc.

Thanks again for the help!
Yuriy Zilbergleyt
Ranch Hand

Joined: Dec 13, 2004
Posts: 429
^ heh, you replied while I was editing my message
Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6
Yup, thats what I meant. Thank you, why 65 by the way? And how does java know how to subtract a number from a letter?
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
65 is the ASCII value of 'A'.

Whenever you use subtraction involving byte, short, char, or int, both operands are converted to an int.

When 'A' is converted to an int it becomes 65.
Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6
Oh of course!

Many thanks again Yuriy!
Darren Jacobs
Greenhorn

Joined: May 02, 2006
Posts: 6


I've written that but it gives the error "operator cannot be applied to java.lang.String"

I'm guessing its not liking subtracting an integer from a string, how do i sort this?
Yuriy Zilbergleyt
Ranch Hand

Joined: Dec 13, 2004
Posts: 429
NodeLabel needs to be a char, not a String. The method String.charAt(0) will give you the first character of any non-empty String.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Connection Array into an adjacency Matrix
 
Similar Threads
octal, hex
Hexadecimal to decimal
Sun Cirtification
Graphs and identifying adjacent nodes
Algorithm related to Tree data structure