Adjacency List implementation for Graph in Java

Question

I am building up a Graph repository which I am planing to use for exploring all the Graph algorithms. This is more from a learning perspective only. I have implemented a basic Graph class using adjacency list and plan to add to this moving further.

Node.java - essentially will contain all node/vertex related information

class Node   {
    String nodeData;
    int nodeNumber;
    boolean isVisited;

    Node next;

    Node( String theNodeData, int nodeNum ) {
        this.nodeData = theNodeData;
        this.nodeNumber = nodeNum;
    }

    Node(int nodeNumber) {
        this.nodeNumber = nodeNumber;
    }

    Node() {
        this.nodeData = null;
        this.nodeNumber=0;
        this.isVisited=false;
        this.next=null;
    }

}

Graph.java

public class Graph {

    private int totalNoOfNodes; 
    private static boolean isDirected;
    private HashMap<Integer,ArrayList<Node>> adjacencyListMap;
    private HashMap<String,Integer> nameToNodeMap;//Map Node data to integer(vertex)
    private Map<Integer,String> nodeToNameMap;// Map vertex or node number to corresponding node data

    public Graph(String inputFileName) throws FileNotFoundException {

        Scanner sc = new Scanner(new File(inputFileName));
        String orientation = sc.next();
        if("directed".equals(orientation)) {
            // Graph is directed 
            isDirected = true;
        } else {
            isDirected = false;
        }

        adjacencyListMap = new HashMap<Integer,ArrayList<Node>>();
        nameToNodeMap = new HashMap<String,Integer>();
        nodeToNameMap = new HashMap<Integer,String>();

        int numberOfNodes = sc.nextInt();
        this.totalNoOfNodes =  numberOfNodes;


        for ( int i =0; i < totalNoOfNodes; ++i ) {
            ArrayList<Node> neighbours = new ArrayList<Node>();
            adjacencyListMap.put(i, neighbours);
        }

        for ( int i =0; i < totalNoOfNodes; ++i) {
            nameToNodeMap.put(sc.next(), i);
        }



        while ( sc.hasNext() ) {

            String nameOne = sc.next();
            String nameTwo = sc.next();

            int source = nameToNodeMap.get(nameOne);
            nodeToNameMap.put(source, nameOne);
            int destination = nameToNodeMap.get(nameTwo);
            nodeToNameMap.put(destination, nameTwo);
            addEdges(source,nameOne, destination, nameTwo);


        }
        sc.close();

    }

    private void addEdges(int source,String nameOne, int destination,String nameTwo) {

        if ( source > adjacencyListMap.size() || destination > adjacencyListMap.size() ) {
            throw new IllegalArgumentException("Source/Destination Vertex invalid. Cannot add edge.");
        }

        (adjacencyListMap.get(source)).add(new Node(nameTwo,destination));
        if ( ! isDirected ) {
            (adjacencyListMap.get(destination)).add(new Node(nameOne,source));
        }

    }

    public int getIndexFromNames(String name ) {

        for ( int i =0; i < adjacencyListMap.size(); ++i ) {
            if ( adjacencyListMap.get(i).equals(name) ) {
                return i;
            }
        }
        return -1;

    }

    public ArrayList<Node> getAdjacentNodesOf(int source) {
        return adjacencyListMap.get(source);
    }

    public int getTotalNoOfNodesInGraph() {
        return totalNoOfNodes;
    }


}

Basic test data

undirected
10
Sara
Sam
Sean
Ajay
Mira
Jane
Maria
Rahul
Sapna
Rohit
Sara Sam
Sara Ajay
Sam Sean
Sam Mira
Mira Jane
Jane Maria
Rahul Sapna
Sapna Rohit

• Graph.java will serve as a basic data type.
• Specific algorithms will be in corresponding classes, say for example DijikstraShortestPath.java and IsGraphAcyclic.java. The underlying data structure used by these algorithms will be Graph.java.

Questions:

1. What do you think of the overall approach? My idea is to just explore various graph algorithms and learn their implementation during the process.
2. Will incorporating generics be of any use?
3. Any pointers on how the code could be improved?

GitHub

Answer 1

Interfaces over implementations

    private HashMap<Integer,ArrayList<Node>> adjacencyListMap;
    private HashMap<String,Integer> nameToNodeMap;//Map Node data to integer(vertex)

These could just be

    private Map<Integer, List<Node>> adjacencyListMap;
    private Map<String, Integer> nameToNodeMap;//Map Node data to integer(vertex)

We can code to the interfaces. This way we can change the implementations later.

Don't use if/else just to assign a Boolean value

        if("directed".equals(orientation)) {
            // Graph is directed 
            isDirected = true;
        } else {
            isDirected = false;
        }

This in general could be simplified to

        // graph is directed iff that's the orientation
        isDirected = "directed".equals(orientation);

I'm not positive that the comment is necessary, but I'm not sure that it's not either.

Different data structures

I don't think that we need node numbers. Consider

class Node   {

    String nodeData;
    boolean isVisited = false;

    Node next = null;

    private final List<Node> neighbors = new ArrayList<>();
    private String name;

    Node( String nodeData ) {
        this.nodeData = nodeData;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void addNeighbor(Node neighbor) {
        neighbors.add(neighbor);
    }

    public void addNeighbors(List<Node> neighbors) {
        this.neighbors.addAll(neighbors);
    }

    public List<Node> getNeighbors() {
        return neighbors;
    }

}

Graph.java

public class Graph {

    private boolean isDirected;
    private Map<String, Node> namesToNodes = new HashMap<>();

    public Graph(String inputFileName) throws FileNotFoundException {
        try ( Scanner sc = new Scanner(new File(inputFileName)) ) {
            isDirected = "directed".equals(sc.next());
            int numberOfNodes = sc.nextInt();

            for ( int i = 0; i < numberOfNodes; ++i ) {
                Node node = new Node();
                node.setName(sc.next());
                namesToNodes.put(node.getName(), node);
            }

            while ( sc.hasNext() ) {
                addEdge(namesToNodes.get(sc.next()), namesToNodes.get(sc.next()));
            }
        }
    }

    private void addEdge(Node source, Node destination) {
        if ( source == null || destination == null ) {
            throw new IllegalArgumentException("Source/Destination Vertex invalid. Cannot add edge.");
        }

        source.addNeighbor(destination);
        if ( ! isDirected ) {
            destination.addNeighbor(source);
        }
    }

    public Node findNodeByName(String name ) {
        return namesToNodes.get(name);
    }

    public List<Node> getAdjacentNodesOf(int source) {
        return source.getNeighbors();
    }

    public int getTotalNoOfNodesInGraph() {
        return namesToNodes.size();
    }

}

This does not store numbers to represent nodes.

It moves the adjacency list into the Node itself.

It uses the existing size tracker of the Map to track the size.

It does still map names to nodes.

Given a node (or a name of a node), we can find the neighbors.

I find this simpler and easier to follow. Node does more, so Graph does not have to do as much.

You don't include code to run this, and I didn't mock up a driver. Beware of typos, etc.