Data Structure question...

[fs5]

I need something that will handle something like this gracefully (in java, I'll call the data structure a tree even though it's not)
here

basically I need to have a starting point (head, like a linked list) and be able to traverse the entire tree. Any node can have any number of connections.

I don't need to find nodes but I DO need to be able to compare tree A to tree B to see if they have the same structure. Speed is not an issue as there won't be more than 10 nodes at any given time.

I would place this is in the software forum but the topics in there are too board.

 

[siliconhairdryer]

Since you want no limit to how many nodes, the most elegant way I can think to do it would be in a database. It would still not be elegant though, but it does meet your requirements.


Create a table called Node_Definition with 3 fields: ID (PK), Xcoord, Ycoord. ID should be an identity column (in ms sql, or a sequence in oracle). There should be a primary key (or unique key) on Xcoord,YCoord. For every node, you see if the coordinates are in use. If not, you allocate a node in that table. If so, you use the one already allocated.

Create a second table called Node_Relationships with two fields: Host, Link

For every link you would have a row in this table, with Host containing the ID of the node in question, and Link containing the ID of one of the nodes it's connected to. So, if node 1 had four links, there would be four records in this table with a Host value of 1, but the link value would correspond to the four node's its linked to.

In this way you could elegantly describe what you have shown, with the ability to have any number of links on any node.

Of course if you dont care for databases you could write this functionality described above in software.

Steve

 

[sao123]

research the data structure of a graph. Similar to a tree, yet allowing more complex structure. Certain traversals of graphs can provide the information you seek.

 

[fs5]

Originally posted by: sao123
research the data structure of a graph. Similar to a tree, yet allowing more complex structure. Certain traversals of graphs can provide the information you seek.

is there a built in java graph class?
edit: I found one by a third party, thanks. 4 years removed from data structures has affected my memory