Question

JAVA

How to make a graph class that uses a linked list class to store nodes and linked list within each node to store adjacency list

The linked list class has been made already.  

import java.util.*;

public class LinkedList implements Iterable
{
private int size = 0;
private Node head;
private Node tail;

private class Node
{
private T data;
private Node prev;
private Node next;

public Node(T data)
{
this.data = data;

}

}

  
public Iterator iterator()
{
return new LinkedListIterator(this);
}

  
private class LinkedListIterator implements Iterator
{
private Node iterNext;

public LinkedListIterator(LinkedList theList)
{
iterNext = theList.head;
}

public boolean hasNext()
{
return (iterNext != null);
}

public T next()
{
T value;
  
if (iterNext == null)
{
  
value = null;
}
else
{
value = iterNext.data;
iterNext = iterNext.next;
}
  
return value;
}

public void remove()
{
throw new UnsupportedOperationException("Not supported");
}
}

public void insertFirst(T value)
{

Node nodeVal = new Node(value);

if(isEmpty())
{
nodeVal.next = null;
nodeVal.prev = null;
head = nodeVal;
tail = nodeVal;
size++;
}
else
{
nodeVal.next = head;
nodeVal.prev = null;
head.prev = nodeVal;
head = nodeVal;
size++;
}
}

public void insertLast(T value)
{

Node nodeVal = new Node(value);

if (isEmpty())
{
nodeVal.next = null;
nodeVal.prev = null;
head = nodeVal;
tail = nodeVal;
size++;
}
else
{
tail.next = nodeVal;
nodeVal.next = null;
nodeVal.prev = tail;
tail = nodeVal;
size++;
}
}

public int size()
{

return size;

}

public boolean isEmpty()
{
return size() == 0;
}

public Node deleteFirst()
{

Node returnVal;

if (isEmpty())
{
throw new RuntimeException("Empty list");   
}
else
{

Node temp = head;
returnVal = head;
head = temp.next;
head.prev = null;
size--;
}

return returnVal;
}

public Node deleteLast()
{

Node returnVal;
  
if (isEmpty())
{
throw new RuntimeException("Empty list");
}
else
{
Node temp = tail;
returnVal = tail;
tail = temp.prev;
tail.next = null;
size--;
}

return returnVal;
}

public Object peekFirst()
{
if (isEmpty())
{
throw new IllegalArgumentException("Empty list");
}

return head.data;
}

public Object peekLast()
{
if (isEmpty())
{
throw new IllegalArgumentException("Empty list");
}
  
return tail.data;
}

public void printNodes(LinkedList list)
{

Iterator itr = list.iterator();

System.out.println("Here is the current list");
  
if(isEmpty())
{
System.out.println("The list is empty\n");
}
else
{
while(itr.hasNext())
{
T o = (T)(itr.next());
System.out.print(o + " ");
}
}

}

}

  

IMPORTANT! The graph class must include these class fields;

vertices, edges (of type LinkedList)

and must include these methods;

a constructor, insertVertex, insertEdge, hasVertex, getVertexCount, getEdgeCount, getVertex, getEdge, getAdjacent, getAdjacentE

Answer 1

The code is explained in the inline comments.

Graphs used to test:

Screenshot:

Graph.java:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class Graph<T> {

   HashMap< T , LinkedList<T>> graph;
  
   public Graph() {
       graph = new HashMap<T , LinkedList<T>>();
   }
  
   /**
   * The below method is used to add the edge in the graph
   * @param graph
   * @param src
   * @param dest
   */
   public void addEdge(HashMap<T , LinkedList<T>> graph , T src , T dest) {
       if(graph.containsKey(src)){
           // if graph already has the source node
           graph.get(src).insertLast(dest);
       }else {
           // if graph doesn't have source node
           LinkedList<T> res = new LinkedList<T>();
           res.insertFirst(dest);
           graph.put(src,res);
       }
   }
   public static void main(String[] args) {
      
       // we implement graph in adjacency list format
      
       // for testing I'm using the graph with integers
      
       Graph<Integer> g =new Graph<Integer>();
      
       // for undirected graph in both directions
       g.addEdge(g.graph, 71 , 52);
       g.addEdge(g.graph, 52, 71);

       g.addEdge(g.graph, 71 , 85);
       g.addEdge(g.graph, 85, 71);

       g.addEdge(g.graph, 85, 52);
       g.addEdge(g.graph, 52, 85);
       g.addEdge(g.graph, 64, 85);
       g.addEdge(g.graph, 85, 64);
       g.addEdge(g.graph, 85, 96);
       g.addEdge(g.graph, 96, 85);

       g.addEdge(g.graph, 52, 64);
       g.addEdge(g.graph, 64, 52);
       g.addEdge(g.graph, 52, 93);
       g.addEdge(g.graph, 93, 52);

       g.addEdge(g.graph, 93, 64);
       g.addEdge(g.graph, 64, 93);
       g.addEdge(g.graph, 96, 64);
       g.addEdge(g.graph, 64, 96);
      
       g.addEdge(g.graph, 96, 93);
       g.addEdge(g.graph, 93, 96);
      
  
// for directed graph we need to use only 1 edges
/*
       g.addEdge(g.graph, 71 , 52);
      
*/
g.printGraphInAdjacencyList();
   }

   /**
   * The below method is used to get the string format of object for all the destinations from the node
   * @param list
   * @return
   */
   public String getNodesAsStr(LinkedList<T> list) {

       Iterator itr = list.iterator();
       String res = "";

           while (itr.hasNext()) {
               T o = (T) (itr.next());
               if(res!="") {
                   res = res +" -> "+o;  
               }else {res += o;}
              
           }
       return res;

   }
   /**
   * The below method is used to represent the graph
   */
   public void printGraphInAdjacencyList() {
      
       Iterator<Entry<T, LinkedList<T>>> keys = graph.entrySet().iterator();
       while (keys.hasNext()) {
       Map.Entry pair = (Map.Entry)keys.next();
      
       LinkedList<T> res = (LinkedList<T>) pair.getValue();
       System.out.println(pair.getKey() + " => " +getNodesAsStr(res));
      
       }
   }
}