creating graphs in Java with ArrayLists

Question

I'm new to Java and I wanted to practice by creating a graph. I am having trouble creating the graph because I'm not sure how to do so correctly. I am lacking the logic and being new in Java makes things quite difficult. I was wondering if anyone could help me or guide me in the right path! Thanks!

Basically I am trying to create something like this as a graph. A node will contain an ArrayList for it's neighbors.

    A,B,C,D
A = 0,1,3,0
B = 1,0,0,2
C = 1,0,0,3   //shorter path to A (cycle)
D = 0,0,3,0

The nodes are connected to each other with or without weights (if I change numbers to 1)

Here is what I have so far (it is incomplete):

public class GraphNode {
    boolean visited;


    public GraphNode() {
        List<GraphNode> node = new ArrayList<GraphNode>();  // store neighbors
        this.visited = false;

    }

    public void addNeighbor(GraphNode root, GraphNode target, int distance) {
        root.add(target);     // cannot use "add" to ArrayList

    }
}

Don't put ArrayList inside your GraphNode class. Instead define a graph class that contains a 2D array of GraphNode (the graph's adjacency matrix). This decouples the node from the logic involved with managing a collection of nodes in a graph. This is what's done in the JUNG java graph library. In fact, I recommend trying this library. It supports running algorithms on the graph (ex Dijkstra's algorithm) and visualizing the graph. — twj
– twj, Commented Jan 14, 2014 at 6:32

Avetis · Accepted Answer · 2015-07-17 00:29:47Z

3

To be able to access the ArrayList from accross methods within the same class, you would need to promote that local variable to a global variable (field), like below:

public class GraphNode {
    /*Global Variables*/
    boolean visited;
    List<GraphNode> nodeNeighbours;
    /*Global Variables*/

    public GraphNode() {
        this.nodeNeighbours = new ArrayList<GraphNode>();  // store neighbors
        this.visited = false;

    }

    public void addNeighbor(GraphNode target) {
        this.nodeNeighbours.add(target);    //This will add target to the neighbours of this given node.
    }
}

EDIT:
Shortest path algorithms (as far as memory serves) have a fixed starting point, meaning that the root will always be the same. The same can be said to their weight, which usually does not change.

However, as different paths are explored, the distance to the root node is most likely to change. With that in mind, you could re write your class as follows:

public class GraphNode {
    /*Global Variables*/
    protected double weight;
    protected double distanceFromRoot;
    protected List<GraphNode> neighbours;
    protected boolean visited;
    /*Global Variables*/

    public GraphNode(double weight, double distanceFromRoot) {
        this.weight = weight;
        this.distanceFromRoot = distanceFromRoot;
        this.neighbours = new ArrayList<GraphNode>();
        this.visited = false;
    }

    public void setDistanceFromRoot(double distanceFromRoot) {
         this.distanceFromRoot = distanceFromRoot;
    }

    public void setVisited(boolean visited) {
         this.visited = visited;
    }

    public double getWeight() {
        return this.weight;
    }

    public double getDistanceFromRoot() {
        return this.distanceFromRoot;
    }

    public List<GraphNode> getNeighbours() {
        return this.neighbours;
    }   

    public void addNeighbour(GraphNode neighbour) {
        this.neighbours.add(neighbour)
    }
}

This might be a little bit more extensive than what you started with. The main change in your code is that this code promoted encapsulation. Encapsulation is one of the core fundamentals of OOP in which you essentially deny direct access to your global variables. The access is offered through appropriate set and get method which you can use to define how and when does someone external to your program modifies the internal state of your program.

edited Jul 17, 2015 at 0:29

Avetis

1,3772 gold badges11 silver badges31 bronze badges

answered Jan 14, 2014 at 6:25

npinti

52.2k5 gold badges74 silver badges98 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Vincent van der Weele Over a year ago

The answer is correct, but the formulation not completely accurate. Rather: "promote the local variable to a field".

Liondancer Over a year ago

Actually, one more question. I'm not sure how I can store the distance variable into teh ArrayList because I've already made it store the neighbors. Is it possible to store another type of data with the nodeNeighbor? inside the ArrayList as well?

npinti Over a year ago

@Heuster: Yes, thanks a lot for pointing that out. I have fixed it.

npinti Over a year ago

@Liondancer: I have made some amendments to my code. I hope this helps.

Collectives™ on Stack Overflow

creating graphs in Java with ArrayLists

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related