6 Clean implementations of Java Graph algorithms

Hi ! In this post I will share with you 6 Java Graph algorithms I had to code for a discrete mathematics final exam in college. The algorithms were presented in an Applet I built and which I also include for you to play around with them.

Before presenting the algorithms I will give a general background about Graph Theory.

What is a graph?

(from Wikipedia) A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.

Type of graphs

There are many, many, many type graphs, most of them associated to maths properties. For the purpose of the API I developed for the algorithms implementations you should know the following:

In terms of representation, a graph can be represented either by an adjacency matrix or an adjacency list. In an adjacency matrix, a true/false (x,y) cell represents if exists a link between node “x” and node “y”. This is the one which I used because of its better performance. In an adjacency list, each node has an own list for storing referenced lists.

Graphs can be also classified by its links, we say that a graph is “weighted” when all links haves a “weight” o “cost” for going from one node to another.

Finally, graphs can be “directed” o “undirected” which means if it’s links are bidirectional or not.

So, the API of my implementations is something like:

public abstract class GraphADT { ... }

Implementations:

public class Graph extends GraphADT { ... }
public class WeightedGraph extends GraphADT { ... }

Prim

Given a connected weighted graph and a** source vertex, returns a minimum spanning **tree which is a tree that includes every vertex but** the total weight of all the edges in the tree is minimized**.

WeightedGraph prim(WeightedGraph graph, int s) { ... }

Warshall

Warshall’s algorithm calculates a transitive closure for a given graph. In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R.

void warshall(Graph g) { ... }

BFS

Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

int BFS(GraphADT graph, int v, int[] levelOrder) { ... }

DFS

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

int DFS(GraphADT graph, int v, int[] pre, int[] post) { ... }

Dijkstra

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing.

Integer[] dijkstra(WeightedGraph graph, int source) { ... }

Floyd

The Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights).

int[][] floyd(WeightedGraph graph) { ... }

Checkout the project from http://code.google.com/p/javagraphalgorithms/.

java

Comments

comments powered by Disqus