Error in implementing a graph in Java

Question

I am trying to create a graph in java using an ArrayList of LinkedList. I have implemented my own list. However, when I try to add connections between the vertices of the graph, I run into an endless loop. I was debugging and I realized that this happens at the point when I am trying to add the element at the end of the LinkedList. I am a beginner, and I don't see what's wrong with my List implementation. Can anyone help?

import java.util.Stack;

// traverse the graph
public class GraphTraversal {


    public static void main(String[] args)
    {
        Graph graph=new Graph();
        initializeGraph(graph);
        graph.breadthFirstSearch();
    }

    public static void initializeGraph(Graph graph)
    {
        Node_Graph node1=new Node_Graph(1, false);
        Node_Graph node2=new Node_Graph(2, false);
        Node_Graph node3=new Node_Graph(3, false);
        Node_Graph node4=new Node_Graph(4, false);
        Node_Graph node5=new Node_Graph(5, false);
        Node_Graph node6=new Node_Graph(6, false);
        Node_Graph node7=new Node_Graph(7, false);
        Node_Graph node8=new Node_Graph(8, false);

        graph.addNode(node1);
        graph.addNode(node2);
        graph.addNode(node3);
        graph.addNode(node4);
        graph.addNode(node5);
        graph.addNode(node6);
        graph.addNode(node7);
        graph.addNode(node8);

        graph.makeConnection(node1, node2);
        graph.makeConnection(node1, node3);
        graph.makeConnection(node3, node4);
        graph.makeConnection(node3, node5);
        graph.makeConnection(node4, node5);
        graph.makeConnection(node4, node6);
        graph.makeConnection(node4, node8);
        graph.makeConnection(node4, node2);
        graph.makeConnection(node6, node5);
        graph.makeConnection(node8, node7);
        graph.makeConnection(node7, node2);
    }

}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

//Class for graph data structure
public class Graph {

    public ArrayList<List> nodes=new ArrayList<List>();


    public void addNode(Node_Graph n)
    {
        List new_node=new List();
        new_node.add(n);
        nodes.add(new_node);
    }

    public void makeConnection(Node_Graph node1, Node_Graph node2)
    {

        for(List list:nodes)
        {
            if(list.head.getId()==node1.getId())
            {
                list.add(node2);
                break;
            }
        }
    }

    public void breadthFirstSearch()
    {
        Stack<Node_Graph> traverse=new Stack<Node_Graph>();
        Node_Graph start=(nodes.get(0)).head;
        start.setVisited(true);
        traverse.push(start);
        while(traverse.empty())
        {
            Node_Graph popped=traverse.pop();
            System.out.println(popped.getId());
            List nextList= nodes.get(popped.getId());
            Node_Graph newElement=nextList.head;
            while(newElement.getNext()!=null)
            {
                newElement=newElement.getNext();
                if(!newElement.getVisited())
                {
                    newElement.setVisited(true);
                    traverse.push(newElement);
                }
            }

            if(!newElement.getVisited())
                traverse.push(newElement);
        }
    }
}

//linked list implementation
public class List{
    public Node_Graph head;
    public int size; 

    public List()
    {
        head=null;
        size=0;
    }

    public void add(Node_Graph element)
    {
        if(head==null)
        {
            head=element;
        }
        else
        {
            Node_Graph last=head;
            while(last.getNext()!=null)
            {
                last=last.getNext();
            }
            last.setNext(element);
        }
    }
}

//node of a graph
public class Node_Graph {

    private int id;
    private boolean visited;
    private Node_Graph next;

    public Node_Graph(int id,boolean visited)
    {
        this.id=id;
        this.visited=visited;
    }
    public void setId(int id)
    {
        this.id=id;
    }

    public int getId()
    {
        return id;
    }

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

    public boolean getVisited()
    {
        return visited; 
    }

    public void setNext(Node_Graph next)
    {
        this.next=next;
    }

    public Node_Graph getNext()
    {
        return next; 
    }
}

The line graph.makeConnection(node4, node6); leads to an infinite loop because the next variable for node 4 is connected endlessly to node 5

Answer 1

First thing I noticed is that the line graph.makeConnection(node3, node5); is causing 4 to become connected to 5, which it shouldn't be.

I added toString methods to your list and node_graph classes to try to make it easier to understand what's going on; here they are so you can try them:

List:

public String toString(){
  Node_Graph h = head;
  String s = "";
  while(h != null){
    s += "[" + h.toString() + "] ";
    h = h.next;
  }
  return s;
}

Node_Graph:

public String toString(){
  String s = id + "";
  if(next != null)
    s += ", " + next.toString();
  return s;
}

Tracked down the error. Let's start with this line:

graph.makeConnection(node1, node3);

That causes the call: {1 -> 2,2 -> null}.add(3) So far so good.

In add, You find the last element of the list: {2}, and set it's next to {3}. Thus, the list now looks like {1 -> 2 -> 3, 2 -> 3, 3}, when it should be {1 -> 2 -> 3, 2, 3}. The first list (incorrectly) implies that 1 is connected to 2 and 3, and 2 is connected to 3, whereas 2 should not be connected to 3, as the second list shows. In your current scheme, this isn't possible, because the '2's are actually the same object with the same, singular next field. It can't be {3} in the 1 element and {null} for itself.

Overall, you need to distinguish between the two "nexts". I believe your goal is that the next field in node_graph represents a node that this node is connected to, whereas the next in list represents the next node in the list, whether there is a connection or not. You're trying to get two birds with one stone with that single next field and it's coming back to bite you with infinite recursion.

There are much cleaner ways to implement a graph - a hashmap (node -> list of neighbor nodes) is much much cleaner and saves you from dealing with all of this next business. If your main goal is to polish your graph algorithms, such as bfs/dfs-ing, you may just want to go with that.

If you really want to implement a graph using lists though, you have some untangling to do. I would advise removing the next field from the Node_Graph class entirely; the Node_Graph class should just worry about its own data, not maintaining list invariants. Then Make the list class have an inner wrapper class that holds a "this" (a Node_Graph instance) and a "next" (a Node_Wrapper) instance. After all that is done, you can give your Node_Graph a neighbors field of type List, which will hold all of its accessible neighbors.

Here's a basic HashMap graph implementation that follows your pattern. You don't need a list implementation either. No wrappers/nexts necessary:

public class Node{

    public final Graph graph; //The graph this Node belongs to 
    private int id;
    private boolean visited;

    /** Constructs a Node with the given inputs. 
      * Also adds itself to g as part of construction */
    public Node(Graph g, int i, boolean v){
        graph = g;
        id = i;
        visited = v;
        graph.addNode(this);
    }

    public int getId(){
        return id;
    }

    public void setVisited(boolean v){
        visited = v;
    }

    //Getters for boolean fields usually follow the is<Field> pattern
    public boolean isVisited(){
        return visited;
    }

    /** Looks up the neighbors of this in the graph */
    public Set<Node> getNeighbors(){
        return graph.neighborsOf(this);
    }
}

public class Graph{

    private HashMap<Node, HashSet<Node>> graph;  //The actual graph. Maps a node -> its neighbors

    public Graph(){
        graph = new HashMap<Node, HashSet<Node>>();
    }

    /** Adds the node to this graph.
        If n is already in this graph, doesn't overwrite */
    public void addNode(Node n) throws IllegalArgumentException{
        if(n.graph != this) 
            throw new IllegalArgumentException(n + " belongs to " + n.graph ", not " + this);
        if(! graph.contains(n))
            graph.put(n, new HashSet<Node>());
    }

    /** Returns the neighbors of the given node. 
      * Returns null if the node isn't in this graph */
    public Set<Node> neighborsOf(Node n){
        if(! graph.contains(n))
            return null;

        return graph.get(n);
    }

    /** Connects source to sink. Also adds both to graph if they aren't there yet */
    public void makeConnection(Node source, Node sink){
        //Make sure source and sink belong to this graph first
        addNode(source);
        addNode(sink);

        //Make the connection by adding sink to source's associated hashset
        graph.get(source).add(sink);
    }
}