Weighted Directed Graph Implementation in Java & Bellman-Ford

Question

I am trying to figure out the best way to implement a Weighted Directed Graph in Java so to I can keep the running time on Bellman-Ford to |V|*|E|. Essentially my question is on how to represent the edges in the graph.

I have seen the use of an adjacency matrix, but I cannot seem to figure out how to use an adjacency matrix while at the same time keeping the running time below O(V^2). The reason I get V^2 as the running time is because Bellman-Ford requires that we loop through all edges, but it order to get a list of the edges I would need to loop through the entire matrix to get all edges. Is there anyway to get the list of edges faster than O(V^2) time with using an adjacency matrix?

Or do I need to use an adjacency list?

Answer 1

You can easily implement a class for Adjacency List. Following is the class which I use as an Adjacency List quite often which is easy to understand also. It maps an integer to a linked list.

class Adjacencylist {

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

    public Adjacencylist(int v){    //Constructor
        adjacencyList = new HashMap<Integer,List<Integer>>();
        for(int i=0;i<v;++i){
            adjacencyList.put(i, new LinkedList<Integer>());
        }
    }

    public void setEdge(int a,int b){    //method to add an edge
        List<Integer> edges=adjacencyList.get(a);
        edges.add(b);
    }

    public List<Integer> getEdge(int a){
        return adjacencyList.get(a);
    }

    public boolean contain(int a,int b){
        return adjacencyList.get(a).contains(b);
    }

    public int numofEdges(int a){
        return adjacencyList.get(a).size();
    }

    public void removeEdge(int a,int b){
        adjacencyList.get(a).remove(b);
    }

    public void removeVertex(int a){
        adjacencyList.get(a).clear();
    }

    public void addVertex(int a){
        adjacencyList.put(a, new LinkedList<Integer>());
    }
}

Before you complain that I need to implement a weighted graph, think about mapping a HashMap to an Integer. You can change the functions accordingly by replacing linked list with hash map. This saves you from O(n^2) time complexity.

Answer 2

My version. This one worked fine for me in one of the use case.

public class DirectedWeightedGraph<E> {

// Map having Vertex as key and List of Edges as Value.
Map<Vertex<E>, List<Edge<E>>> adj = new HashMap<>();


public static class Vertex<E> {
    E value;

    public Vertex(E value) {
        this.value = value;
    }
}

public static class Edge<E> {
    E from;
    E to;
    double weight;

    public Edge(E from, E to, double weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

}

public void addVertex(E value) {
    Vertex<E> v = new Vertex<E>(value);
    List<Edge<E>> edges = new ArrayList<>();
    this.adj.put(v, edges);
}

public void addEdge(E from, E to, double weight) {
    List<Edge<E>> fromEdges =  this.getEdges(from);
    List<Edge<E>> toEdges =  this.getEdges(from);

    // Add source vertex and then add edge
    if(fromEdges == null) {
        this.addVertex(from);
    }
    if(toEdges == null) {
        this.addVertex(to);
    }

    fromEdges.add(new Edge<E>(from, to, weight));
}

}

Example:

DirectedWeightedGraph <Integer> graph = new DirectedWeightedGraph<>();
graph.addEdge(1, 2, 10.0);
graph.addEdge(2,3,15.0);