Cfrtjryk

I am reading a text, that from a higher level explained adjacency list implementation of a graph.

I have now tried to implement this as simply as I could. I did not see any reason to have an actual vertex or node class.

Based on my implementation, does it look like I understood properly how an adjacency list graph works?

import java.util.*;



public class Graph {

    private HashMap<String, HashSet<String>> nodes;    



    public Graph () 

    {

        nodes = new HashMap<String, HashSet<String>>();

    }



    public void addNode(String name)

    {

        if (!nodes.containsKey(name))

            nodes.put(name ,  new HashSet<String>());

    }



    public void addEdge(String src , String dest)

    {

        HashSet<String> adjList = nodes.get(src);



        if (adjList == null)

            throw new RuntimeException("addEdge - src node does not exist");



        adjList.add(dest);

    }

}

I think the code is incomplete. It's possible to build a Graph but there is no way to process it as there are no methods returning the state of a Graph.

To be able to evaluate the shown code I'm going to extend it by two methods:

/**

 * Returns true if a node with the given name was added.

 */

public boolean hasNode(String name) {

    return nodes.containsKey(name);

}





/**

 * Returns true if an edge form source node to destination node (identified by their names) was added.

 */

public boolean hasEdge(String src, String dest) {

    HashSet<String> adjList = nodes.get(src); 

    return adjList != null && adjList.contains(dest);

}

Let's use a simple example to show some shortcomings:

public static void main(String args) {

    Graph g = new Graph();

    g.addNode("A");

    g.addEdge("A", "B");



    System.out.println(g.hasNode("A")); // true

    System.out.println(g.hasNode("B")); // false

    System.out.println(g.hasEdge("A", "B")); // true

}

egdes to missing nodes

The method addEdge verifies that a source node is already present. But it doensn't verify if the destination node is present, too. Thus it's possible to addEdge from an already added node to an unknown node.

Whereas hasNode("B") will state that there is no node "B" in the Graph g, hasEdgde("A", "B") will return true which is at least misleading. I think it's inconsistent as I would expected this implies there is a node "B" also present in the Graph g.

directed graph

Since addEdge adds an edge from a source node to a destination node it's more precise to speak of a directed graph. Otherwise

g.hasEdge("B", "A");

needs to return true. But actually it isn't.

readding a node is possbile

Another point: It's possible to add already added nodes again.

g.addNode("A");

This results in replacing the current node by a new one. There is no exception and hasNode("A") will still return true. But all edges from the previous node to other nodes are lost.

System.out.println(g.hasEdge("A", "B")); // false

This should be prevented.

readding an edge

Readding an edge doesn't throw an exception. But it doesn't add an edge actually. It's impossible since a node is storing it's edges in a Set. A Set will not add an already present element once again. As long as there is no need to know how many times an edge from a node to another was add this isn't severe.

Some further hints:

• You can declare nodes as Map<String, Set<String>>. Since you're using interface methods only, there is no need to use the implementation types.


• When adding a node calling first nodes.containsKey(name) and then on success calling nodes.put(name, new HashSet<String>()) has double complexity as the element within the map has to be looked up twice. But sinnce adding a node several times shouldn't be possible we can write

instead:

public void addNode(String name) {

    Set<String> node = nodes.get(name);

    if (node != null)

        throw new RuntimeException("addNode - node already exist");

    nodes.put(name, new HashSet<String>());

}