In this section, lets create classes for undirected graph, directed graph, edge-weighted undirected graph, edge-weighted directed graph, directed graph with capacity and flow.
We not only build java classes for fun, we build them with purpose. Here is the problem we want to resolve.
1. are point A and point B in a graph (directed/undirected) connected?
2. what is the path from point A to point B in a graph?
3. what is the shortest/longest path from point A to point B in a graph?
4. do we have (negative) cycle in a graph?
5. what is the max flow (min cut) in a graph?
With these question in mind, let's get started.
For a graph without weight, we only concern about connectivity.
Undirected Graph
The graph should have fields for points/vertexes and their relationships.
class Graph {
int N;
int[] points;
Map<Integer, Set<Integer>> neighbors;
}
As a second thought, with the neighbors Map, we can find anything. The neighbors.keySet() is the vertexes, neighbors.values() is the edges. An undirected graph is simply a Map -- the relationship between neighbors, nothing else.
Adding edge A - B is to add B to A's neighbor set, then add B to A's neighbor set. We end up with a very simple class.
class Graph {
Map<Integer, Set<Integer>> neighbors = new HashMap<>();
void addEdge(int a, int b) {
neighbors.computeIfAbsent(a, k -> new HashSet<Integer>()).add(b);
neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(a);
}
}
The rest are the convenient methods. The completed class and test for undirected graph is here Graph.java. The output of Graph.java is here. The Dot language visual result is here.
Directed Graph
Next, we add more information to the edges, an edge now has a direction. For example, point A directs to point B. At the first impression, in order to model the relationship between neighbor points, we now need an Edge class. The Edge class contains the two end points, and a direction, totally 3 fields. However, the direction can be implicit. When we add an edge, we only update the neighbors for one of the two points.
class Graph {
Map<Integer, Set<Integer>> neighbors = new HashMap<>();
void addEdge(int a, int b) {
neighbors.computeIfAbsent(a, k -> new HashSet<Integer>()).add(b);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(a);
}
}
Again, the rest are the convenient methods. The completed class and test for directed graph is here Digraph.java. A sample output of the program is here.
Edge Weighted Undirected Graph
We can add weight attribute to the undirected graph. So The connection between point A and point B now has a weight. This time we have to introduce an Edge class to model the connections, which contains 2 points and a weight.
class Edge {
final int a, b;
final double weight;
public Edge(int a, int b, double weight) {
this.a = a; this.b = b; this.weight = weight;
}
}
With Edge object, we can model the relationships with a Map.
class Graph {
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double weight) {
Edge e = new Edge(a, b, weight);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double weight) {
Edge e = new Edge(a, b, weight);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
The completed class and test for edge weighted undirected graph is here EwGraph.java. A sample output of the program is here.
Edge Weighted Digraph
Let's add direction to the edge wighted graph. Since direction can be implicit, more information gives a simpler model as before EwDigraph.java. A sample output of the program is here.
class Graph {
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double weight) {
Edge e = new Edge(a, b, weight);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double weight) {
Edge e = new Edge(a, b, weight);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
Other Edge Decorators
As we can tell, weight is the first decoration we add to the edge class, we can add as many decorations as we like.
class Edge {
final int a, b;
final double capacity, flow;
final Enum color;
final String label;
final double penwidth;
final Enum color;
final String label;
final double penwidth;
...
}
class Graph {
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double capacity, double flow, ...) {
Edge e = new Edge(a, b, capacity, flow, ...);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
Let's stop our model build up here, we have seen the formula. Next let's use DFS and BFS to play magic on these simple models.
class Graph {
Map<Integer, Set<Edge>> neighbors = new HashMap<>();
void addEdge(int a, int b, double capacity, double flow, ...) {
Edge e = new Edge(a, b, capacity, flow, ...);
neighbors.computeIfAbsent(a, k -> new HashSet<Edge>()).add(e);
//neighbors.computeIfAbsent(b, k -> new HashSet<Integer>()).add(e);
}
}
Let's stop our model build up here, we have seen the formula. Next let's use DFS and BFS to play magic on these simple models.
