2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can you include a main() that exercises this code? It's not obvious how you can use the generated graph. \$\endgroup\$ Aug 27, 2018 at 7:39

1 Answer 1

1
\$\begingroup\$

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>());
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.