Implementation of generic Graph class and Dijkstras

I participate in competitive programming contests, and I found myself implementing and re-implementing graphs constantly. So I decided to create a reusable implementation of a Graph class, and implement some common methods for it, including DFS, BFS, and Dijkstras.

Are there any edge cases that my code misses? Is there anything I could do to improve it?

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.function.BiConsumer;
import java.util.stream.Collectors;

public class Graph<T> {

public class Node {
public T value;
public Map<Integer, Integer> edges;

public Node(T value) {
this.value = value;
edges = new HashMap<>();
}
}

public List<Node> nodes;

public boolean directed;
public int numNodes = 0;
public int numEdges = 0;

public Graph() {
this(false);
}

public Graph(boolean directed) {
nodes = new ArrayList<>();
this.directed = directed;
}

}

public void connect(int i, int j, int weight) {
nodes.get(i).edges.put(j, weight);
if (!directed)
nodes.get(j).edges.put(i, weight);
}

public class DijkstrasNode extends Node {
int dist = -1;
boolean visited = false;
DijkstrasNode previous;

public DijkstrasNode(T value) {
super(value);
}

public DijkstrasNode(Node node) {
super(node.value);
this.edges = node.edges;
}
}

public void processBFS(int source, BiConsumer<Node, Integer> consumer) {
boolean[] visited = new boolean[nodes.size()];
while (!q.isEmpty()) {
int id = q.poll();
if (visited[id])
continue;
visited[id] = true;
Node n = nodes.get(id);
consumer.accept(n, id);
for (int c: n.edges.keySet())
}
}

public void processDFS(int source, BiConsumer<Node, Integer> consumer) {
Stack<Integer> q = new Stack<>();
boolean[] visited = new boolean[nodes.size()];
q.push(source);
while (!q.isEmpty()) {
int id = q.pop();
if (visited[id])
continue;
visited[id] = true;
Node n = nodes.get(id);
consumer.accept(n, id);
for (int c: n.edges.keySet())
}
}

public List<DijkstrasNode> dijkstras(int source) {
List<DijkstrasNode> djk = nodes.stream().map(DijkstrasNode::new).collect(Collectors.toList());
djk.get(source).dist = 0;
PriorityQueue<DijkstrasNode> q = new PriorityQueue<>((i, j) -> i.dist - j.dist);
int visitCount = 0;
while (!q.isEmpty() && visitCount < djk.size()) {
DijkstrasNode n = q.poll();
if (n.visited)
continue;
n.visited = true;
visitCount++;
for (int child : n.edges.keySet()) {
DijkstrasNode cn = djk.get(child);
if (!cn.visited && (cn.dist == -1 || n.dist + n.edges.get(child) < cn.dist)) {
if (cn.dist != -1)
q.remove(cn);
cn.dist = n.dist + n.edges.get(child);
cn.previous = n;
}
}
}
return djk;
}

}

• Nice. You might consider also implementing the graph as a 2d array, which might have performance benefits in some cases – RobAu Jan 16 at 9:27
• @RobAu will that necessarily help with Dijkstras? I've heard that adjacency matrixes are less efficient for Dijkstras. – vikarjramun Jan 16 at 13:57
• Performance is a function of a lot of factors, for example the sparsity of the graph, the implementation, cache and memory-efficiency etc. – RobAu Jan 16 at 14:11

I think you should not extend Node to DijkstraNode, but rather have a Node<Dijkstra>. Or, if you intent to store info in the DijkstraNode, have a Node<Dijkstra<T>>.