1

I am trying to make a graph in java that would have different nodes. some nodes would be connected to others and some wont. If they are connected then some boolean value for that node will be true and another variable will hold the value of the node it is connected to.

...any suggestions on what you guys think is the best way to approach this?

4 Answers 4

3

The two most common ways to represent a graph are adjacency matrix and adjacency lists. Let n be the number of nodes.

Adjacency matrix A is an n x n matrix of boolean values, such that A(i, j) = 1 if nodes i and j are connected, and 0 if they are not.

In adjacency lists representation for each node you maintain a list of the nodes it is connected to (adjacent to).

The question now is what you want to do with the graph. If it is something simple, it may make sense to roll your own. If not, you may want to poke around the web for a java library to handle graphs. JGraphT has been mentioned.

If you want to use adjacency matrix, then you can easily represent it in Java as a 2D array of bool's or int's. You would need to give each node an index. The easiest way to do that is to keep your Node objects in an array, always in the same order. So you would really have two data structures: an array of Nodes, which are objects that represent whatever your nodes actually are, and the adjacency matrix, which refers to the Nodes by their indices.

Once you populate the matrix, if you can easily find a node that is connected to most other nodes by adding up the values (0s and 1s) in all the columns (or rows), and finding the maximum. Hope this helps.

1
  • think an adjacency matrix is what I want. want to do something simple like finding nodes that are most connected between each other. can you give me an idea of how to to about making an adjacency matrix from java pov...where input would be an nxn matrix based on which nodes will be created
    – user41685
    Dec 8, 2008 at 3:50
2

There are two standard models for storing graphs. The one Tom describes is the Adjacency List. The other would be a stand-alone Adjacency Matrix.

If you care about efficiency, study the sparseness of your situation (the more edges, the more performance-friendly is the matrix version). If perf isn't an issue, use what you'd rather program with...

1

Create a Node class and give it an instance variable of type Node. Initialize it to null - if said node is connected to another node, then this instance variable will refer to it; otherwise, it will remain null.

If the node may be connected to numerous nodes (which is quite common for graphs), then use an ArrayList to store all of the nodes to which said node is connected.

0

Possibly a duplicate of 'Good Java graph algorithm library?'. The short answer would be to look at JGraphT.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.