Introduction
Welcome back, graph enthusiasts, for the highly anticipated sequel to our last discussion. Get ready for some significant renovations to the code we wrote last time.
To guide you through this architectural marvel, we've introduced a special instruction: if a code snippet is wrapped with this ---- sign, it means that piece of code is being evicted! Simply remove it and then immediately install the brand-new, shiny code directly below it. That being said, follow my Telegram Channel and let's go to business.
Topological ordering
A topological ordering, or topological sort, is like trying to put your socks on before your shoes (unless you're a true rebel, but then you wouldn't need a topological sort). It's a linear ordering of the vertices in a directed acyclic graph (DAG), which basically means it's a list of things where there's no going in circles (because that would just be chaotic, like trying to tie your shoelaces before you've even picked out the shoes). For every directed edge (u, v), vertex u absolutely, positively must come before vertex v. In simpler terms, it's arranging your tasks so that all dependencies are respected. So, if task A must be completed before task B, then A will appear before B in the sorted list. Otherwise, you'd end up trying to eat dessert before dinner, and we all know how well that goes over with Mom. Look at the figure below for more understanding.
Alright, our definition is done and dusted! Now, let's make our lovely graph's topological ordering happen. Grab that GraphAlgorithms.java file from our last adventure, and go ahead and write the following code right in there.
public static <V> ArrayList<Vertex<V>> topologicalSort(Graph<V> graph) {
ArrayList<Vertex<V>> topological = new ArrayList<>();
Stack<Vertex<V>> stack = new Stack<>();
HashMap<Vertex<V>, Integer> inCount = new HashMap<>();
for (Vertex<V> v : graph.vertices()) {
inCount.put(v, graph.inDegree(v));
if (inCount.get(v) == 0) {
stack.push(v);
}
}
while (!stack.isEmpty()) {
Vertex<V> current = stack.pop();
topological.add(current);
for (Vertex<V> vertex : graph.outgoingVertices(current)) {
inCount.put(vertex, inCount.get(vertex) - 1);
if (inCount.get(vertex) == 0) {
stack.push(vertex);
}
}
}
return topological;
}
So, picture this: our HashMap is basically the graph's gossipy social network, listing every vertex and precisely how many 'friends' (incoming edges) they need to be introduced by. At first, our stack is super exclusive, only letting in the popular kids who have no dependencies—they just waltz right in! But here's the kicker: the more incoming edges a vertex has, the more demanding it is. It's like, 'Sorry, can't be processed until Tasks A, B, and C have cleared the path for me!' Talk about high-maintenance!
To see if the code actually, go on over to your Main.java file. Then, insert the following code snippet inside your main() method. This is where we'll create a graph that resembles the one in the figure below.
AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(true);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);
graph.insertEdge(one, two);
graph.insertEdge(one, three );
graph.insertEdge(one, five);
graph.insertEdge(two, three);
graph.insertEdge(three, four);
graph.insertEdge(three, five);
graph.insertEdge(four, five);
var topological = GraphAlgorithms.topologicalSort(graph);
for (Vertex<Integer> vertex : topological) {
System.out.print(vertex.getElement() + ", "); // [1, 2, 3, 4, 5]
}
While the in-degree method (Kahn's algorithm) is fantastic, the Depth First Search (DFS) approach is another elegant and equally powerful way to achieve a topological ordering.
The core idea with DFS is indeed to push vertices onto a stack after all their dependencies (their outgoing edges) have been fully explored. When you're done, flipping that stack gives you the perfect, reverse-engineered chronological order. I'll leave the thrilling implementation of this particular sorcery to you.
Weighted Graphs
A weighted graph is just a regular graph that started dealing with real-world expenses. Each edge is assigned a numerical (and let me reiterate, numerical) value, known as a 'weight.' This weight could be a cost (like how much that cross-town taxi really hits your wallet), a distance (because some detours are just plain rude), or any other metric that says, 'Hey, this connection actually matters more (or less) than that one. We need to know if that connection is a quick hop or an epic quest.
Okay, so our edges now come with a bonus feature: weights. To incorporate this crucial information into our graph, we'll need to update our existing code. That means it's time to modify some elements from our last post to accurately represent these weighted connections. Go ahead and create an Edge.java file, then add the provided code.
import java.util.ArrayList;
public class Edge<V> {
private Vertex<V> origin, destination;
private int weight;
public Edge(Vertex<V> origin, Vertex<V> destination, int weight) {
this.origin = origin;
this.destination = destination;
this.weight = weight;
}
public int getWeight() {
return weight;
}
public ArrayList<Vertex<V>> endpoints() {
ArrayList<Vertex<V>> endpoints = new ArrayList<>(2);
endpoints.add(origin);
endpoints.add(destination);
return endpoints;
}
public Vertex<V> opposite(Vertex<V> v) {
if (v == origin)
return destination;
return origin;
}
public Vertex<V> getOrigin() {
return origin;
}
public Vertex<V> getDestination() {
return destination;
}
}
Next go to Graph.java file and the following code in our interface.
int outDegree(Vertex<V> v) throws IllegalArgumentException;
int inDegree(Vertex<V> v) throws IllegalArgumentException;
Iterable<Edge<V>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException;
Iterable<Edge<V>> incomingEdges(Vertex<V> v) throws IllegalArgumentException;
Edge<V> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;
}
With the new methods added to our interface, the next logical step—for obvious reasons—is to provide their implementation within our AdjacencyMapGraph class. This is where we'll define the functionality for those methods. Please insert the code below into your AdjacencyMapGraph class.
// ------ snip ----
@Override
public Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> outgoing = validate(v);
---- return outgoing.getOutgoing(); ----
return outgoing.getOutgoing().keySet();
}
@Override
public Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> incoming = validate(v);
---- return incoming.getIncoming(); ----
return incoming.getIncoming().keySet();
}
@Override
public Iterable<Edge<V>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> incoming = validate(v);
return incoming.getOutgoing().values();
}
@Override
public Iterable<Edge<V>> incomingEdges(Vertex<V> v) throws IllegalArgumentException {
InnerVertex<V> outgoing = validate(v);
return outgoing.getIncoming().values();
}
@Override
public Edge<V> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException {
if (!isValidVertex(u) || !isValidVertex(v)) {
throw new IllegalArgumentException("Invalid vertex");
}
if (hasEdge(u, v)) {
InnerVertex<V> origin = validate(u);
InnerVertex<V> destination = validate(v);
return origin.getOutgoing().get(destination);
}
return null;
}
}
Alright, it's time to get our InnerVertex class ready for the big leagues—where edges aren't just connections, they have weight. To make sure our vertices can properly keep track of these weighted relationships, we need to swap out that old HashSet for a more robust HashMap. This way, we can associate each connected vertex (our key) with its specific edge (our value).
So, head into your InnerVertex class and add the following code:
protected static class InnerVertex<V> implements Vertex<V> {
// ---- snip ----
---- private HashSet<Vertex<V>> outgoing, incoming; ----
private HashMap<Vertex<V>, Edge<V>> outgoing, incoming;
public InnerVertex(V element, boolean isDirected) {
this.element = element;
---- outgoing = new HashSet<>(); ----
outgoing = new HashMap<>();
if (isDirected) {
---- incoming = new HashSet<>(); ----
incoming = new HashMap<>();
} else {
incoming = outgoing;
}
}
// ---- snip ----
----
public HashSet<Vertex<V>> getOutgoing() throws IllegalArgumentException {
return outgoing;
}
----
public HashMap<Vertex<V>, Edge<V>> getOutgoing() throws IllegalArgumentException {
return outgoing;
}
----
public HashSet<Vertex<V>> getIncoming() throws IllegalArgumentException {
return incoming;
}
----
public HashMap<Vertex<V>, Edge<V>> getIncoming() throws IllegalArgumentException {
return incoming;
}
// ---- snip ----
}
To clear up those red lines in your AdjacencyMapGraph class, go ahead and add the following code inside it. This should sort out any errors you're seeing in your text editor.
// ---- snip ----
---- private void removeEdge(HashSet<Vertex<V>> edges, Vertex<V> vertex, boolean isOutgoing) { ----
private void removeEdge(HashMap<Vertex<V>, Edge<V>> edges, Vertex<V> vertex, boolean isOutgoing) {
for (Vertex<V> ve : edges.keySet()) {
InnerVertex<V> vert = validate(ve);
if (isOutgoing) {
vert.getIncoming().remove(vertex);
} else {
vert.getOutgoing().remove(vertex);
}
numEdges--;
}
edges.clear();
}
// -- snip --
@Override
public V removeVertex(Vertex<V> v) throws IllegalArgumentException {
// ---- snip ----
---- HashSet<Vertex<V>> outgoing = vertex.getOutgoing(); ----
HashMap<Vertex<V>, Edge<V>> outgoing = vertex.getOutgoing();
removeEdge(outgoing, vertex, true);
---- HashSet<Vertex<V>> incoming = vertex.getIncoming(); ----
HashMap<Vertex<V>, Edge<V>> incoming = vertex.getIncoming();
removeEdge(incoming, vertex, false);
// ---- snip ----
return temp;
}
// ---- snip ----
@Override
public void insertEdge(Vertex<V> u, Vertex<V> v, int wight) throws IllegalArgumentException {
// ---- snip ----
if (!hasEdge(u, v)) {
InnerVertex<V> origin = validate(u);
InnerVertex<V> destination = validate(v);
Edge<V> edge = new Edge<>(origin, destination, wight);
---- origin.getOutgoing().add(destination); ----
---- destination.getIncoming().add(origin); ----
origin.getOutgoing().put(destination, edge);
destination.getIncoming().put(origin, edge);
numEdges++;
} else
throw new IllegalArgumentException("Edge from u to v exists");
}
Dijkstra’s Algorithm
Dijkstra's algorithm a blessing designed for those moments when you absolutely, positively need to find the shortest path between two points in a tangled mess of connections.
This clever little method doesn't just guess; it meticulously explores the graph, like a highly organized detective with a clipboard. It keeps track of where it's been (the "visited nodes" list) and how far it is to everywhere else (the "distance table"). Then, it repeatedly updates its "best guess" for how to get to neighboring nodes until, voilà, it's figured out the shortest route to every single reachable spot. So, next time you're stuck in a labyrinth, just remember Dijkstra—it's probably already mapped the fastest way out!
Our algorithm uses a handy little HashMap to keep tabs on how far each vertex thinks it is from the starting line, and a 'cloud' (because 'set of visited nodes' just sounds too boring) for all the vertices that have already had their moment in the sun.
But the real MVP, the one we built a tiny shrine for, is our magnificent PriorityQueue.This unsung hero makes sure the vertex with the shortest distance always cuts to the front of the line.
Here's the lowdown: we start by stuffing our lovely PriorityQueue and our distance HashMap. If a vertex is the 'source,' we graciously grant it a distance of zero. Everyone else? Straight to 'maximum integer' distance – tough luck, chumps.
Then, it's a looping frenzy until our PriorityQueue is completely exhausted. In each round, we heroically pop the current 'shortest distance' champion. Then, we parade through its outgoing edges, doing some quick math. If we find a path (current distance + edge weight) that's shorter than what's currently in our distance HashMap , we update it and invite that lucky vertex to the PriorityQueue party. Because who doesn't love a good shortcut?
You've absorbed the wisdom; now, go ahead and paste the code below into your GraphAlgorithms class.
import java.util.PriorityQueue;
import java.util.Queue;
public class GraphAlgorithms {
// ----- snip -----
public static <V> HashMap<Vertex<V>, Integer> shortestPathLengths(Graph<V> graph, Vertex<V> source) {
HashMap<Vertex<V>, Integer> distances = new HashMap<>();
HashMap<Vertex<V>, Integer> cloud = new HashMap<>();
Queue<Edge<V>> queue = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
for (Vertex<V> vertex : graph.vertices()) {
if (vertex == source) {
distances.put(vertex, 0);
queue.offer(new Edge<>(source, null, 0));
} else {
distances.put(vertex, Integer.MAX_VALUE);
queue.offer(new Edge<>(source, null, Integer.MAX_VALUE));
}
}
int size = queue.size();
int counter = 0;
while (size > counter && !queue.isEmpty()) {
Edge<V> currentEdge = queue.poll();
Vertex<V> currentVertex = currentEdge.getOrigin();
int distance = currentEdge.getWeight();
cloud.put(currentVertex, distance);
for (Edge<V> edge : graph.outgoingEdges(currentVertex)) {
Vertex<V> vertex = edge.opposite(currentVertex);
if (cloud.get(vertex) == null) {
int weight = edge.getWeight();
int d = distance + weight;
if (d < distances.get(vertex)) {
distances.put(vertex, d);
queue.offer(new Edge<>(vertex, null, distances.get(vertex)));
}
}
}
counter++;
}
return cloud;
}
// ----- snip -----
Alright, let's build that graph and put our Dijkstra's algorithm to the ultimate test! You can see from the figure below that the shortest distance from vertex 0 to vertex 4 is 17. We'll set up the graph just like that, then run our code to confirm it. Head over to your main() method and drop in the following code.
AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(false);
Vertex<Integer> zero = graph.insertVertex(0);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);
Vertex<Integer> six = graph.insertVertex(6);
graph.insertEdge(zero, two, 6);
graph.insertEdge(zero, one, 2);
graph.insertEdge(two, three, 8);
graph.insertEdge(one, three, 5);
graph.insertEdge(three, four, 10);
graph.insertEdge(three, five, 15);
graph.insertEdge(four, six, 2);
graph.insertEdge(five, six, 6);
var dijkstra = GraphAlgorithms.shortestPathLengths(graph, zero);
for (var vertex : dijkstra.entrySet()) {
System.out.println("Start Vertex: " + zero.getElement() + " -> " +
vertex.getKey().getElement()
+ ", Distance: " + vertex.getValue());
}
Minimum Spanning Tree MST
Imagine you've got a bunch of scattered islands (vertices) and a limited budget for bridges (edges with weights). An MST is that clever little subset of bridges that connects every single island, using the absolute minimum amount of bridge-building material possible, all while avoiding any silly circular detours (cycles). Essentially, it's the "cheapest" and most efficient way to wire up your entire network without creating any redundant loops.
When tackling this problem, you'll meet two algorithms: Kruskal's Algorithm and Prim's Algorithm. They're both inherently greedy, always making the seemingly selfish choice at each step to get the job done.
Kruskal's algorithm
Kruskal's Algorithm, works by iteratively snatching up the lowest-weight edge it can find, as long as it doesn't create a cycle in our growing Minimum Spanning Tree. It keeps doing this until every single vertex has been personally invited to the party.
In essence, Kruskal's is the super-organized type: it first lines up all the graph's edges from smallest to largest, like a meticulous librarian. Then, it goes down the line, adding edges and nodes to the MST only if they promise not to cause a cyclical drama. It's all about picking the feather-light edges first and saving the heavy lifters for last. And for the grand finale? It gracefully merges any trees that haven't quite connected yet, like a matchmaker bringing lonely branches together.
Now, as for implementing this genius... ah, my dear friends, I shall leave that thrilling adventure to your capable hands.
Prim's Algorithm
Meet Prim's Algorithm, the other star in our MST show! If Kruskal's is the meticulous librarian, Prim's is more of a social climber. It's another greedy guru for finding the minimum spanning tree of a weighted, undirected graph.
How does it work? Imagine Prim's starting from an arbitrary vertex (like picking a random person at a party). Then, it continuously sniffs out the absolute cheapest connection that links its ever-expanding social circle (the growing tree) to someone new (a fresh vertex). It keeps adding these 'best new friends' until everyone at the party is connected in the most cost-effective way possible! No cycles allowed, just efficient networking.
For our implementation, we're getting super organized! We'll be using an ArrayList<Edge<V>> to neatly store all the edges that make it into our MST. To steer clear of the dreaded cycle, we've got a trusty HashSet on standby, ready to mark vertices as 'visited.'
And, of course, no heroic journey is complete without our hero: the PriorityQueue. Our algorithm will embark on an iterative quest, starting from the source, meticulously adding unvisited vertices to the queue and carefully selecting the edges to populate our ArrayList<Edge<V>>. It's all about precision, avoiding loops, and letting our PriorityQueue do the heavy lifting!
public static <V> ArrayList<Edge<V>> MST(Graph<V> graph, Vertex<V> source) {
ArrayList<Edge<V>> tree = new ArrayList<>();
HashSet<Vertex<V>> visited = new HashSet<>();
Queue<Edge<V>> queue = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
queue.add(new Edge<>(source, null, 0));
while (!queue.isEmpty()) {
Edge<V> currentEdge = queue.poll();
Vertex<V> currentVertex;
if (currentEdge.getDestination() == null) {
currentVertex = currentEdge.getOrigin();
} else {
currentVertex = currentEdge.getDestination();
}
if (!visited.contains(currentEdge.getOrigin()) || !visited.contains(currentVertex)) {
Vertex<V> destination = currentEdge.getDestination();
Edge<V> edge = destination == null ? null : graph.getEdge(currentEdge.getOrigin(), destination);
if (edge != null) {
tree.add(edge);
}
visited.add(currentVertex);
visited.add(currentEdge.getOrigin());
}
for (Edge<V> edge : graph.outgoingEdges(currentVertex)) {
Vertex<V> vertex = edge.opposite(currentVertex);
int weight = edge.getWeight();
if (!visited.contains(vertex) || !visited.contains(currentVertex)) {
Edge<V> edgeWeight = new Edge<>(currentVertex, vertex, weight);
queue.offer(edgeWeight);
}
}
}
return tree;
}
To prove Prim's algorithm, we're going to construct a graph in code that's identical to the figure below. This is where we see if all our hard work pays off. Dive into your main() method and add the code below.
AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(false);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);
// Insert edges
graph.insertEdge(one, two, 2);
graph.insertEdge(one, three, 3);
graph.insertEdge(two, three, 1);
graph.insertEdge(two, four, 3);
graph.insertEdge(two, five, 2);
graph.insertEdge(four, five, 5);
graph.insertEdge(three, five, 1);
var mst = GraphAlgorithms.MST(graph, zero);
for (Edge<Integer> edge : mst) {
System.out.println("Edge: " + edge.getOrigin().getElement() + " -> " +
edge.getDestination().getElement() + ", Weight: " + edge.getWeight());
}
Top comments (0)