2
\$\begingroup\$

Graph Interface:

import java.util.*;

public interface Graph<T> {


    boolean addEdge(T src, Edge edge);

    boolean removeEdge(T source, T destination);

    boolean addVertex(T vertex);

    boolean removeVertex(T vertex);

    void printAdjacencyList();

    List<Edge> getNeighbours(T vertex);


    Map<T, List<Edge>> getAdjacencyList();
}

Undirected Graph class:



import java.util.*;

public class UndirectedGraph<T> implements Graph<T> {
    protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();

    @Override
    public boolean addVertex(T vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new LinkedList<Edge>());
            return true;
        }
        return false;
    }

    @Override
    public boolean removeVertex(T vertex) {
        if (adjacencyList.containsKey(vertex)) {
            adjacencyList.remove(vertex);
            for (List<Edge> entry : adjacencyList.values()) {
                List<Edge> list = entry;
                for (Edge e : list) {
                    if (e.getDestination().equals(vertex)) {
                        list.remove(e);
                    }
                }
            }
            return true;
        }
        return false;
    }

    @Override
    public List<Edge> getNeighbours(T vertex) {
        return adjacencyList.get(vertex);
    }

    @Override
    public boolean addEdge(T src, Edge dst) {
        if (adjacencyList.containsKey(src) && adjacencyList.containsKey(dst.getDestination())) {
            adjacencyList.get(src).add(dst);
            adjacencyList.get(dst.getDestination()).add(new Edge(src, dst.getWeight()));
            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 edge from the list of the source and destination
    @Override
    public boolean removeEdge(T source, T destination) {
        if (adjacencyList.containsKey(source) && adjacencyList.containsKey(destination)) {
            for (Edge e : adjacencyList.get(source)) {
                if (e.getDestination().equals(destination)) {
                    adjacencyList.get(source).remove(e);
                    return true;
                }
            }
        }
        return false;
    }

    public Map<T, List<Edge>> getAdjacencyList() {
        return Collections.unmodifiableMap(adjacencyList);
    }

    @Override
    public String toString() {
        return "UndirectedGraph{" +
                "adjacencyList=" + adjacencyList +
                '}';
    }
}

Directed Graph Class:

import java.util.*;

public class DirectedGraph<T> implements Graph<T> {
    protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();

    @Override
    public boolean addVertex(T vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new LinkedList<Edge>());
            return true;
        }
        return false;
    }

    @Override
    public boolean removeVertex(T vertex) {
        if (adjacencyList.containsKey(vertex)) {
            adjacencyList.remove(vertex);
            for (List<Edge> entry : adjacencyList.values()) {
                List<Edge> list = entry;
                for (Edge e : list) {
                    if (e.getDestination().equals(vertex)) {
                        list.remove(e);
                    }
                }
            }
            return true;
        }
        return false;
    }

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


    @Override
    public boolean removeEdge(T source, T destination) {
        if (adjacencyList.containsKey(source)) {
            for (Edge e : adjacencyList.get(source)) {
                if (e.getDestination().equals(destination)) {
                    adjacencyList.get(source).remove(e);
                    return true;
                }
            }
        }
        return false;
    }
    public Map<T, List<Edge>> getAdjacencyList() {
        return Collections.unmodifiableMap(adjacencyList);
    }
    public List<Edge> getNeighbours(T node) {
        return adjacencyList.get(node);
    }

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


}

Edge Class:

public class Edge<T> {

    private T destination;
    private int weight;

    public Edge(T destination) {
        this.destination = destination;

    }

    public Edge(T destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }


    public T getDestination() {
        return destination;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "destination=" + destination +
                ", weight=" + weight +
                '}';
    }
}

Pathfind class:

import java.util.*;


public class Pathfind<T> {


    //Dijkstra's Algorithm
    public void findShortestPath(Graph graph, T source) {
        //gets the adjacency list
        Map<T, List<Edge>> adj = graph.getAdjacencyList();
        int verticesCount = adj.size();
        //Storing the distances here
        Map<Node<T>, Integer> distances = new HashMap<>();
        //Keeping track of visited vertices here
        List<T> visited = new ArrayList<>();
        PriorityQueue<Node> pq = new PriorityQueue<Node>(verticesCount, Node::compareTo);
        //Adding all vertices to distances map and setting the value of distance to max
        for (T vertex : adj.keySet()) {
            distances.put(new Node(vertex), Integer.MAX_VALUE);
        }
        distances.put(new Node(source, 0), 0);

        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node<T> node = pq.poll();
            T vertex = node.getNode();
            visited.add(vertex);

            for (Edge<T> edge : adj.get(vertex)) {
                if (!visited.contains(edge.getDestination())) {
                    int totalCost = node.getCost() + edge.getWeight();
                    T destNode = edge.getDestination();

                    if (totalCost < distances.get(new Node(destNode))) {
                        Node<T> node1 = new Node<T>(destNode, vertex);
                        distances.remove(node1);
                        distances.put(node1, totalCost);

                    }
                    pq.add(new Node(destNode, totalCost, vertex));
                }
            }

        }

        for (Node<T> node : distances.keySet()) {
            if (distances.get(node) < Integer.MAX_VALUE) {
                System.out.print(node.getNode().toString() + " ||| Cost = " + distances.get(node));

            }
            if (node.getPredecessor() != null) {
                System.out.println(" ||| Predecessor = " + node.getPredecessor().toString());
            }
        }

    }


    public class Node<T> implements Comparable<Node<T>> {
        private T node;
        private int cost;
        private T predecessor;

        public Node(T node) {
            this.node = node;
        }

        public Node(T node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        public Node(T node, T predecessor) {
            this.node = node;
            this.predecessor = predecessor;
        }

        public Node(T node, int cost, T predecessor) {
            this.node = node;
            this.cost = cost;
            this.predecessor = predecessor;
        }

        public T getNode() {
            return node;
        }


        public int getCost() {
            return cost;
        }

        public T getPredecessor() {
            return predecessor;
        }

        public void setPredecessor(T predecessor) {
            this.predecessor = predecessor;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?> node1 = (Node<?>) o;
            return Objects.equals(node, node1.node);
        }

        @Override
        public int hashCode() {
            return Objects.hash(node);
        }

        @Override
        public int compareTo(Node<T> other) {
            return Integer.compare(cost, other.getCost());
        }
    }
}

What could I have done better ? I have so much duplicated code in UndirectedGraph and DirectedGraph. I'm also planning to implement other pathfinding algorithms and visualizing them.

\$\endgroup\$
1
  • \$\begingroup\$ Where are the tests? \$\endgroup\$ Jan 15 at 11:15
3
\$\begingroup\$

your major issue is the redunat code you say... so you should try to put things that some classes have in common into a common class

there is a very nice example of the proper usage of interfaces, of abstract classes and impolementing classes on stackoverflow - this answer provides the basic concepts.

so what? what now?

your interface looks good so far, so you need a base implementation that does all the stuff that any would do:

public abstract class BaseGraph<T> implements Graph<T>{

    //this is just a stub - most classes are not shown, do on your own!

    @Override
    public boolean addEdge(T src, Edge dst) {
        if (containsEdge(src, dest) { //this is different
            addEdgeToAdjacency(src, dest); //this is different as well
            return true;
        }
        return false;
    }

    abstract boolean containsEdge(T src, Edge dst);

    abstract void addEdgeToAdjacency(T src, Edge dst);


}

your implementing class now has to implement only the different parts of the code

class UndirectedGraph<T> extends BaseGraph<T>{

    @Override
    boolean containsEdge(T src, Edge dst){
        return adjacencyList.containsKey(src) && adjacencyList.containsKey(dst.getDestination());
    }

    @Override
    void addEdgeToAdjacency(T src, Edge dst){
        adjacencyList.get(src).add(dst);
        adjacencyList.get(dst.getDestination()).add(new Edge(src, dst.getWeight()));
    }

}

Note

i am not an expert on Graphs so you have to decide how far you make your abstract class BaseGraph abstract - i can not tell you how much sense it makes to have an abstract method boolean containsEdge(T src, Edge dst) (or addEdgeToAdjacency), here you have to think on your own.

side note:

what's the difference between node and vertex? - well, there is no difference :-) so you should change your Graph class to a more proper model:

interface Graph<Node<T>> {
   ...
}

this way you would avoid a BUG that may occur if any T does not properly ovverwrite equals and hashCode. that would lead to errors while checking for content of the list (adjacencyList.containsKey(src)).

side note 2

your ShortestPath method is not very readable - you start nice with bringing the algoroth into code (first lines) but then you stop with it - have a look at the Integration Operation Segregation Principle (IOSP) - it says:

IOSP calls for a clear separation:

  • Either a method contains exclusively logic, meaning transformations, control structures or API invocations. Then it’s called an Operation.
  • Or a method does not contain any logic but exclusively calls other methods within its code basis. Then it’s called Integration.

that would clean up your method! (your algorithm is a pure operation methode)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Got rid of the redundant code ! thank you. Will work on making my ShortestPath method more readable. \$\endgroup\$
    – GodLike
    Jan 20 at 15:17
2
\$\begingroup\$

On graph node type name

I see that you named the graph node type N, which is OK since in Java we name the type arguments with a single letter according to the first letter of the name of the underlying concept. However, consider renaming it to V (as in Vertex).

I. General comments

Advice I.1

I strongly suggest you use Javadoc facilities for describing your code. If nothing else, you should explain, for instance, the difference between directed and undirected graphs somewhere in your code (preferably as class comments). Also, you could explain briefly what graphs are all about.

Advice I.2

I suggest you put all your classes in a package with a name like com.yourcompany.graph or similar.

II. Graph interface

First of all, let's take a look at your Graph interface:

import java.util.*;

public interface Graph<T> {

    boolean addEdge(T src, Edge edge);

    boolean removeEdge(T source, T destination);

    boolean addVertex(T vertex);

    boolean removeVertex(T vertex);

    void printAdjacencyList();

    List<Edge> getNeighbours(T vertex);

    Map<T, List<Edge>> getAdjacencyList();
}

Advice II.1

import java.util.*;

I really suggest you import explicitly all the classes you use. So, the above becomes:

import java.util.List;
import java.util.Map;

Advice II.2

In my opinion, introducing the Edge class adds an unnecessary level of indirection. I would have instead:

boolean addEdge(V sourceVertex, V targetVertex);

Advice II.3

I would remove printAdjacencyList and provide the methods for accessing the internals of the graph through the java.util.Collections.unmodifiableXXX wrappers so that the caller cannot tamper with the internal state directly.

Advice II.4: Suggested design

I had this mind:

package com.yourcompany.graph;

import java.util.Collection;
import java.util.Set;

/**
 * This interface defines the API for a graph.
 * 
 * @param <V> the actual graph vertex type.
 */
public interface Graph<V> {
    
    boolean addEdge(V sourceVertex, V targetVertex);
    boolean hasEdge(V sourceVertex, V targetVertex);
    boolean removeEdge(V sourceVertex, V targetVertex);
    
    boolean addVertex(V vertex);
    boolean hasVertex(V vertex);
    boolean removeVertex(V vertex);
    
    Set<V> getVertices();
    Collection<V> getParentVerticesOf(V vertex);
    Collection<V> getChildVerticesOf(V vertex);
    
    int numberOfNodes();
    int numberOfEdges();
}

III. Directed graph

Advice III.1

protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();

I would write:

protected final Map<V, Set<V>> childMap = new HashMap<>();
protected final Map<V, Set<V>> parentMap = new HashMap<>();

That way, you can map each vertex to a java.util.HashSet that provides (expected) \$\mathcal{O}(1)\$ time for add, contains and remove. (java.util.List runs contains and remove in \$\mathcal{O}(n)\$ worst-case time.)

The idea is that childMap.get(\$u\$) will map \$u\$ to all the vertices \$v\$ such that there is a pair \$(u, v)\$ in the edge set of the graph (child nodes of u). Conversely, parentMap.get(\$u\$) will map \$u\$ to all the vertices \$v\$ such that there is a pair \$(v, u)\$ in the edge set (parent nodes of u).

Having separate parentMap allows us to have the method getParentVerticesOf, which, in turn, is required in bidirectional point-to-point pathfinding (bidirectional BFS, bidirectional Dijkstra's algorithm, NBA*).

Advice III.2

public boolean addVertex(T vertex) {
    if (!adjacencyList.containsKey(vertex)) {
        adjacencyList.put(vertex, new LinkedList<Edge>());
        return true;
    }
    return false;
}

java.util.LinkedList is a poor choice. Consider java.util.ArrayList instead. The problem here is that LinkedList introduces \$\Theta(n)\$ worth space overhead for storing the internal linked list nodes. Also, the internal list nodes do not exhibit reference locality, so CPU cache won't help much. Consider this instead:

@Override
public boolean addVertex(V vertex) {
    checkInputNotNull(vertex);
    
    if (!childMap.containsKey(vertex)) {
        childMap.put(vertex, new HashSet<>());
        parentMap.put(vertex, new HashSet<>());
        vertices.add(vertex); // vertices is also a HashSet!
        return true;
    }
    
    return false;
}

Advice III.3

public boolean removeVertex(T vertex) {
    if (adjacencyList.containsKey(vertex)) {
        adjacencyList.remove(vertex);
        for (List<Edge> entry : adjacencyList.values()) {
            List<Edge> list = entry;
            for (Edge e : list) {
                if (e.getDestination().equals(vertex)) {
                    list.remove(e);
                }
            }
        }
        return true;
    }
    return false;
}

The outer for loop iterates around (+1/-1) \$n\$ times and the outer loop iterates around \$m\$ times, so the running time is \$\Theta(m + n + \sum_{i = 1}^n c_i) = \Theta(m + n)\$ where \$c_i\$ is the number of nodes in the adjacency list of the node \$n_i\$. You can definitely drop this to \$\Theta(1)\$ with the following implementation of the method in question:

public boolean removeVertex(V vertex) {
    checkInputNotNull(vertex);
    
    if (!hasVertex(vertex)) {
        return false;
    }
    
    numberOfEdges -= 
            (childMap.get(vertex).size() + parentMap.get(vertex).size());
    
    childMap.remove(vertex);
    parentMap.remove(vertex);
    vertices.remove(vertex);
    return true;
}

Advice III.4

public boolean removeEdge(T source, T destination) {
    if (adjacencyList.containsKey(source)) {
        for (Edge e : adjacencyList.get(source)) {
            if (e.getDestination().equals(destination)) {
                adjacencyList.get(source).remove(e);
                return true;
            }
        }
    }
    return false;
}

Above, the worst-case running time of the method is \$\mathcal{O}(k^2)\$, where \$k = \$ adjacencyList.get(source).size(). You can do this in constant time:

public boolean removeEdge(V sourceVertex, V targetVertex) {
    checkInputNotNull(sourceVertex);
    checkInputNotNull(targetVertex);
    
    if (!childMap.containsKey(sourceVertex)) {
        return false;
    }
    
    if (!childMap.get(sourceVertex).contains(targetVertex)) {
        return false;
    }
    
    childMap.get(sourceVertex).remove(targetVertex);
    parentMap.get(targetVertex).remove(sourceVertex);
    numberOfEdges--;
    return true;
}

Note III.5

public Map<T, List<Edge>> getAdjacencyList() {
    return Collections.unmodifiableMap(adjacencyList);
}

Good!

IV. Dijkstra shortest path tree

Note IV.1

I see that you compute not a shortest path to a target vertex, but rather a shortest path tree. You could encapsulate that tree into a class that supports a query method computing the shortest path from the source vertex to any given input target vertex:

package com.yourcompany.graph;

// imports.

public class ShortestPath<V> {
    
    private final List<V> path = new ArrayList<>();
    
    public ShortestPath(List<V> path) {
        this.path.addAll(path);
    }
    
    public List<V> getVertexList() {
        return Collections.<V>unmodifiableList(path);
    }
    
    public int getPathWeight(WeightFunction<V> weightFunction) {
        int pathWeight = 0;
        
        for (int i = 0; i < path.size() - 1; i++) {
            pathWeight = pathWeight + weightFunction.getWeight(path.get(i),
                                                               path.get(i + 1));
        }
        
        return pathWeight;
    }
}

... and ...

package com.yourcompany.graph;

// imports.

public class ShortestPathTreeBuilder<V> {

    private final Map<V, V> parentMap = new HashMap<>();
    
    public ShortestPathTreeBuilder(Map<V, V> parentMap) {
        this.parentMap.putAll(
                Objects.requireNonNull(
                        parentMap,
                        "The input parent map is null."));
    }
    
    public ShortestPath<V> buildPathTo(V targetVertex) {
        List<V> path = new ArrayList<>();
        V node = targetVertex;
        
        while (node != null) {
            path.add(node);
            node = parentMap.get(node);
        }
        
        Collections.<V>reverse(path);
        return new ShortestPath<>(path);
    }
}

Advice IV.2

I would extract the edge weights from the Edge objects, and code up a simple class for storing the weights for any single ordered pair of vertices:

package com.yourcompany.graph;

public interface WeightFunction<V> {

    void setWeight(V sourceVertex, V targetVertex, int weight);
    int getWeight(V sourceVertex, V targetVertex);
}

Also,

package com.yourcompany.graph.impl;

import com.yourcompany.graph.WeightFunction;
import java.util.HashMap;
import java.util.Map;

public class DirectedGraphWeightFunction<V> 
implements WeightFunction<V> {

    private final Map<V, Map<V, Integer>> map = new HashMap<>();
    
    @Override
    public void setWeight(V sourceVertex, V targetVertex, int weight) {
        if (!map.containsKey(sourceVertex)) {
            map.put(sourceVertex, new HashMap<>());
        }
        
        map.get(sourceVertex).put(targetVertex, weight);
    }
    
    @Override
    public int getWeight(V sourceVertex, V targetVertex) {
        return map.get(sourceVertex).get(targetVertex);
    }
}

Note IV.3

//Keeping track of visited vertices here
List<T> visited = new ArrayList<>();

This will definitely limit your computation speed. The problem is that visited.contains(edge.getDestination()) will run in worst-case \$\mathcal{O}(n)\$ time, where \$n\$ is the number of vertices in the graph. This leads to the fact that your implementation runs in \$\mathcal{O}(mn)\$ worst-case time. Use java.util.HashSet instead and the time complexity will drop to \$\mathcal{(m + n) \log n}\$. (With Fibonacci heap, this drops to \$\mathcal{O}(m + n \log n)\$, but Fibonacci heap hides very large hidden constant factors, so its usage in practice is questionable.)

Summa summarum

I had this implementation in mind.

Hope that helps.

\$\endgroup\$
2
  • \$\begingroup\$ that is a quite fully review +1 \$\endgroup\$ Jan 18 at 15:30
  • \$\begingroup\$ I made some of the changes that i was able to understand from the review so far and I will be trying to understand the rest. Really appreciate your detailed review. Thank you \$\endgroup\$
    – GodLike
    Jan 20 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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