3
\$\begingroup\$

Attempt to implement undirected graph with intentions of making a directed implementation too. I'm also new to Generics. I'm sure there's a lot of things I can do better


public class UndirectedGraph<T> implements Graph<T> {

    private Map<T, List<T>> adjacencyList;

    public UndirectedGraph() {
        adjacencyList = new HashMap<>();
    }

    //Checks if a vertex with the same name exists, if not adds it and returns true
    @Override
    public boolean addVertex(T vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new LinkedList<T>());
            return true;
        }
        return false;
    }

    @Override
    public boolean addEdge(T src, T dst) {
        if (adjacencyList.containsKey(src) && adjacencyList.containsKey(dst)) {
            adjacencyList.get(src).add(dst);
            adjacencyList.get(dst).add(src);
            return true;
        }
        return false;
    }


    //Prints the adjacecny list
    public void printAdjacencyList() {
        adjacencyList.entrySet().forEach(entry -> {
            System.out.println(entry.getKey() + " " + entry.getValue().toString());
        });
    }


    //Removes the vertex and all the edges tied to it.
    @Override
    public boolean removeVertex(T vertex) {
        if (adjacencyList.containsKey(vertex)) {
            adjacencyList.remove(vertex);
            for (Map.Entry<T, List<T>> entry : getAdjacencyList().entrySet()) {
                List<T> list = entry.getValue();
                for (T e : list) {
                    if (e.equals(vertex)) {
                        entry.getValue().remove(e);
                    }
                }
            }
            return true;
        }
        return false;
    }

    /*IF graph is directed, removes the edge from the list of the source
     * If graph is not directed, removes the edge from the list of the source and destination*/

    @Override
    public boolean removeEdge(T source, T destination) {
        if (source != null && destination != null) {
            adjacencyList.get(source).remove(destination);
            adjacencyList.get(destination).remove(source);
            return true;
        }
        return false;
    }

    public Map<T, List<T>> getAdjacencyList() {
        return adjacencyList;
    }
}

Graph Interface:

public interface Graph<T> {

    public boolean addVertex(T vertex);
    public boolean addEdge(T src, T dst);
    public boolean removeVertex(T vertex);
    public boolean removeEdge(T source, T destination);
} 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice one, but I suggest you add something like getNeighborsOf(T vertex). That way you can apply some graph algorithms to your graph implementation. \$\endgroup\$
    – coderodde
    Jan 4, 2022 at 16:26
  • \$\begingroup\$ will do, thank you ! \$\endgroup\$
    – GodLike
    Jan 4, 2022 at 17:19

1 Answer 1

4
\$\begingroup\$

In the Graph interface, there's no need to declare the methods public. Interface methods are implicitly public.

The adjacency graph should probably be a Map<T, Set<T>>, as the order of connected nodes is not important. This will make some lookups mildly faster, but more importantly it won't imply to readers that the order matters.

The adjacency graph can be assigned inline. There's no reason to make readers go into the constructor to find the assignment.

The adjacency graph can be marked final. This makes it clear to readers that it is never reassigned.

All of the methods return true or false, but if a method fails there is no way for the caller to figure out why. At the very least, all the interface methods need javadoc explaining under what conditions they return which value. Consider also whether throwing runtime exceptions would make sense when these methods are invoked with invalid values.

Prefer guard clauses instead of sticking all the code of a method in an if block. For example,

public boolean removeVertex(T vertex) {
    if (adjacencyList.containsKey(vertex)) {
        return false;
    }
    adjacencyList.remove(vertex);
    //...
    return true;
}

addVertex could leverage putIfAbsent.

Objects should not be responsible for printing themselves. For starters, what if the client code is using a logging framework? Instead, override toString() to return a string representation of the adjacency graph.

removeVertex can be cleaned up by looping over values() instead of entrySet() and by using remove(vertex) on the Collection that is returned.

getAdjacencyList returns the actual backing data structure of the graph, which means a client can accidentally or maliciously break the invariants of the graph. Either return a Collections.unmodifiableMap() or make a copy of the map and return that.

\$\endgroup\$
4
  • \$\begingroup\$ Made most of these changes, thank you. Any tips for making it a weighted graph ? should i do it in a different class ? \$\endgroup\$
    – GodLike
    Jan 5, 2022 at 3:49
  • 2
    \$\begingroup\$ @GodLike For a weighted graph, an edge becomes more than just the two connected vertices, so you should introduce an Edge<T> interface and use that in addEdge() and similar methods. And in many real-world graph applications, the edges have a real-world meaning that should anyway be reflected by being a first-class object implementing Edge<T>. \$\endgroup\$ Jan 5, 2022 at 11:39
  • \$\begingroup\$ ==Ralf Kleberhoff \$\endgroup\$
    – Eric Stein
    Jan 5, 2022 at 12:49
  • \$\begingroup\$ @RalfKleberhoff since it's an undirected graph, adding an edge from A -> B means adding B to the list of edges of A, and adding A to the list of edges to B. the Edge A -> B is passed as a parameter in addEdge but what about the edge B -> A ? I can't create one since Edge is an interface. How do i get around this ? \$\endgroup\$
    – GodLike
    Jan 5, 2022 at 18:23

Your Answer

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

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