Always pertinent:
Problem: determine if a graph has cycles:
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[][] m = new int[5][5]();
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
m[i][j] = 0;
}
}
m[0][1] = 1;
m[0][2] = 1;
m[1][0] = 1;
m[1][3] = 1;
m[2][0] = 1;
m[2][3] = 1;
m[3][1] = 1;
m[3][2] = 1;
m[3][4] = 1;
m[4][3] = 1;
var vertices = InitializeSingleSource(m, 0);
var edges = new HashMap<String, String>();
edges.put("A", "B");
edges.put("A", "C");
edges.put("B", "A");
edges.put("B", "D");
edges.put("C", "A");
edges.put("C", "D");
edges.put("D", "B");
edges.put("D", "C");
edges.put("D", "E");
edges.put("E", "D");
System.out.println(hasCyclesByBellmanFord(vertices, edges));
}
private static List<Vertex> InitializeSingleSource(int[][] m, int start) {
var vertices = new ArrayList<Vertex>();
for (int i = 0; i < m.length; i++){
var v = new Vertex();
v.id = String.valueOf(Character.valueOf('A' + i));
v.d = Integer.MAX_VALUE;
if (i == start) { v.d = 0; }
v.parent = null;
}
return vertices
}
private static Vertex getVertex(List<Vertex> vertices, String id){
for (int i = 0; i < vertices.size(); i++){
if (vertices.get(i).id.equals(id)){
return vertices.get(i);
}
}
return null;
}
// A ->C <-D ->E
// ->B->
private static boolean hasCyclesByBellmanFord(List<Vertex> vertices, Map<String, String> edgeMap) {
boolean result = false;
for (int i = 0; i < vertices.length; i++){
for(var entry: edgeMap.entrySet()) {
var u = getVertex(entry.getKey());
var v = getVertex(entry.getValue());
relax(u, v);
}
}
for (var entry: edgeMap.entrySet()) {
var u = getVertex(entry.getKey());
var v = getVertex(entry.getValue());
if (u != null &&
v != null &&
v.d > u.d + 1) {
result = true;
return result;
}
}
return result;
}
private static void Relax(Vertex u, Vertex v) {
if (u == null || v == null) { return; }
if (v.d > u.d + 1) {
v.d = u.d + 1;
v.parent = u;
}
}
class Vertex {
public String id;
public Vertex parent;
public Integer d;
}
}
