package GraphAPI;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;
public class Graph {
int v, e, connex;
List[] adj;
boolean[] marked, color;
int[] parent, id;
boolean bipart = true, isCycle = false;
Stack reverseOrder;
public Graph(int n) {
this.v = n;
adj = new List[n];
for (int i = 0; i < n; i++) {
adj[i] = new LinkedList<>();
}
}
/* constructor from a file */
public Graph(File file) {
BufferedReader reader;
try {
reader = new BufferedReader(new FileReader(file));
String line;
v = Integer.parseInt(reader.readLine()); //number of elements (1st line)
e = Integer.parseInt(reader.readLine()); //number of edges (2nd line)
adj = new List[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
}
while ((line = reader.readLine()) != null) {
String[] parts = line.split("\\s");
int from = Integer.parseInt(parts[0]);
int to = Integer.parseInt(parts[1]);
adj[from].add(to);
}
reader.close();
} catch (IOException ex) {
}
}
/* add edge for directed graph */
public void addEdge(int v, int w)
{
adj[v].add(w);
}
public void init() {
parent = new int[v];
id = new int[v];
marked = new boolean[v];
color = new boolean[v];
connex = 0;
reverseOrder = new Stack<>();
}
/* Depth-First Search */
public void dfs(int s) {
id[s] = connex;
marked[s] = true;
adj[s].stream().forEach((x) -> {
if (!marked[x]) {
color[x] = !color[s];
parent[x] = s;
dfs(x);
} else if (color[x] = color[s]) {
bipart = false;
} else {
//not working need dfs(s, origin)
isCycle = true;
}
});
if(!adj[s].isEmpty())
reverseOrder.push(s);
}
/* start a Depth-First Search */
public void exProfondeur(int s) {
init();
dfs(s);
}
/* ckeck if a path exist between a and b */
public boolean pathExist(int a, int b) {
exProfondeur(a);
return marked[b];
}
/* get a path between a and b */
public Stack getPath(int a, int b)
{
if (!pathExist(a, b)) return null;
Stack path = new Stack<>();
while (a != b) {
path.push(b);
b = parent[b];
}
path.push(a);
return path;
}
/* check if all element of the graph are connected */
public boolean isConnexe() {
exProfondeur(adj[0].get(0));
for (boolean isMarked : marked) {
if (!isMarked) {
return false;
}
}
return true;
}
/* count numbre of connexe */
public void countConnexe() {
for (int i = 0; i < v; i++) {
if (!marked[i]) {
dfs(i);
connex++;
}
}
}
/* check if two components are connected */
public boolean areConnected(int C1, int C2) {
return id[C1] == id[C2];
}
/* get connexe by id */
public List getConnexe(int v) {
List list = new LinkedList<>();
for (int i = 0; i < v; i++) {
if (id[i] == v) {
list.add(i);
}
}
return list;
}
/* get all connected componenets */
public Map> getAllConnexe(int v) {
Map> map = new HashMap<>();
for (int i = 0; i < id.length; i++) {
List l = map.get(id[i]);
if (l == null) {
l = new LinkedList<>();
}
l.add(i);
map.put(id[i], l);
}
return map;
}
/* check if this graph has a cycle */
public boolean hasCycle() {
init();
for (int i : id) {
dfs(i);
}
return isCycle;
}
/* still figuring it out */
boolean bipart() {
init();
dfs(0);
return bipart;
}
/* breadth first search */
public void bfs(int s) {
LinkedList q = new LinkedList<>();
q.addLast(s);
marked[s] = true;
while (!q.isEmpty()) {
s = q.getFirst();
for (int w : adj[s]) {
if (!marked[w]) {
q.addLast(w);
parent[w] = s;
marked[w] = true;
}
}
}
}
public Stack topologicalOrder(){
init();
for (int i = 0; i < v; i++) {
if(!marked[i]) dfs(i);
}
return reverseOrder;
}
/* print the graph (obviously) */
public void print(){
for (int i = 0; i < v; i++) {
System.out.print(i + " -> ");
adj[i].stream().forEach(x->{System.out.print( x + " ");});
System.out.println("");
}
}
/* testing */
public static void main(String[] args) {
File file = new File("src/GraphAPI/data.txt");
Graph g = new Graph(file);
System.out.println("------- Graph -------");
g.print();
System.out.println("------- hasCycle -------");
if(g.hasCycle())
System.out.println("yes");
else System.out.println("no");
System.out.println("------- pathExist(0, 4) -------");
if(g.pathExist(0, 4))
System.out.println("yes");
else System.out.println("no");
System.out.println("------- pathExist(3, 0) -------");
if(g.pathExist(3, 0))
System.out.println("yes");
else System.out.println("no");
System.out.println("------- path(3, 0) -------");
Stack path1 = g.getPath(3,0);
while (!path1.isEmpty()) {
System.out.print(path1.pop() + " -> ");
}
System.out.println("");
System.out.println("------- isConnexe -------");
if(g.isConnexe())
System.out.println("yes");
else System.out.println("no");
System.out.println("------- countConnex -------");
g.countConnexe();
System.out.println(g.connex);
System.out.println("------- topologicalOrder -------");
Stack path = g.topologicalOrder();
while (!path.isEmpty()) {
System.out.print(path.pop() + " -> ");
}
System.out.println("");
}
}