Encoding related nodes in a graph
I am trying to make a graph in java that will have different nodes. some nodes will be linked to others and some will be linked to others. If they are connected, then some boolean value will be used for this node, and another variable will contain the value of the node to which it is connected.
... any suggestions for what you guys think is the best way to approach this?
source to share
The two most common ways to represent a graph are adjacency matrices and adjacency lists. Let n be the number of nodes.
Adjacency Matrix A is an nxn boolean matrix such that A (i, j) = 1 if nodes i and j are connected and 0 if they are not.
In adjacency list view, for each node, you maintain a list of nodes it is connected to (next to).
Now the question is what do you want to do with the graph. If it's something simple, it might make sense to quit your business. If not, you may want around the world to use a Java library to handle graphs. JGraphT .
If you want to use an adjacency matrix, you can easily represent it in Java as a 2D bool or int array. You will need to specify each node index. The easiest way to do this is to store the node objects in an array, always in the same order. Thus, you will indeed have two data structures: an array of nodes, which are objects that represent all of your nodes, and an adjacency matrix, which refers to the nodes by their indices.
After filling in the matrix, if you can easily find the node that is connected to most of the other nodes by adding the values (0 and 1) to all columns (or rows) and finding the maximum. Hope this helps.
source to share
There are two standard models for storing graphs. One of them describes the Adjacency List . The other will be a standalone Adjacency Matrix .
If you care about efficiency, study the rarity of your situation (the more edges, the more user-friendly the matrix version is). If performance is not a problem, use what you prefer with the program ...
source to share
Create a class Node
and give it an instance variable of the type Node
. Initialize it to zero - if the specified node is connected to another node, then this instance variable will refer to it; otherwise, it will remain zero.
If a node can be connected to multiple nodes (which is quite common for graphs), use ArrayList
to store all the nodes that the specified node is connected to.
source to share
Possibly a duplicate library Good Java Graph Algorithm Library? ... The short answer is to look at JGraphT .
source to share