import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author santosh
*/
public class AdjMatGraph {
class Queue {
LinkedList
int size;
public void enqueue(GNode gn) {
size++;
queueHead.add(gn);
}
public GNode dequeue() {
if (size > 0) {
size--;
return queueHead.removeLast();
}
return null;
}
public GNode peek() {
return queueHead.getFirst();
}
public GNode tail() {
return queueHead.getLast();
}
public int qSize() {
return size;
}
public boolean isEmpty() {
if (size <= 0) {
return true;
} else {
return false;
}
}
}
private class GNode {
int vLabel;
boolean isVisited;
}
private int adjMat[][];
private int noOfEdges;
private int noOfVertex;
private GNode vertex[];
private Stack
private Queue queue;
public AdjMatGraph() {
adjMat = new int[100][100];
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
adjMat[i][j] = 0;
}
}
noOfEdges = 0;
noOfVertex = 0;
vertex = new GNode[100];
for (int k = 0; k < 100; k++) {
vertex[k] = new GNode();
vertex[k].isVisited = false;
vertex[k].vLabel = -1;
}
stack = new Stack
queue = new Queue();
}
public void setNoEdges(int val) {
noOfEdges = val;
}
public void setNoVertex(int val) {
noOfVertex = val;
for (int i = 1; i <= val; i++) {
vertex[i - 1].vLabel = i;
}
}
public int findVertex(int v) {
for (int i = 0; i < noOfVertex; i++) {
if (vertex[i].vLabel == v) {
return i;
}
}
return -1;
}
public void addEdge(int v1, int v2) {
int index1 = findVertex(v1);
int index2 = findVertex(v2);
if (index1 != -1 && index2 != -2) {
adjMat[index1][index2] = 1;
adjMat[index2][index1] = 1;
}
}
public void printMatrix() {
for (int i = 0; i < noOfVertex; i++) {
System.out.println();
for (int j = 0; j < noOfVertex; j++) {
System.out.print("\t" + adjMat[i][j]);
}
}
}
public GNode getAdjNode(GNode node) {
int index = findVertex(node.vLabel);
if (index != -1) {
for (int i = 0; i < noOfVertex; i++) {
if (adjMat[index][i] == 1 && !vertex[i].isVisited) {
// System.out.println("GetAdj: " + vertex[i].vLabel);
return vertex[i];
}
}
}
return null;
}
public void DFS() {
System.out.print("DFS: ");
for (int i = 0; i < noOfVertex; i++) {
if (!vertex[i].isVisited) {
stack.add(vertex[i]);
while (!stack.isEmpty()) {
GNode tmp = stack.pop();
if (!tmp.isVisited) {
tmp.isVisited = true;
System.out.print("\t" + tmp.vLabel);
// get adjacent node
GNode t2 = getAdjNode(tmp);
if (t2 != null) {
stack.add(t2);
}
}
}
}
}
for (int i = 0; i < noOfVertex; i++) {
vertex[i].isVisited = false;
}
}
public void BFS() {
System.out.print("\nBFS: ");
for (int i = 0; i < noOfVertex; i++) {
if (!vertex[i].isVisited) {
vertex[i].isVisited = true;
System.out.print("\t" + vertex[i].vLabel);
queue.enqueue(vertex[i]);
while (!queue.isEmpty()) {
GNode tmp = queue.dequeue();
GNode v = null;
tmp.isVisited = true;
while ((v = getAdjNode(tmp)) != null) {
v.isVisited = true;
System.out.print("\t" + v.vLabel);
queue.enqueue(v);
}
}
}
}
System.out.println();
for (int i = 0; i < noOfVertex; i++) {
vertex[i].isVisited = false;
}
}
/**
* This section contains function to help implement Directed Graph
* and topological sorting.
*/
public void addDirectEdge(int v1, int v2) {
int index1 = findVertex(v1);
int index2 = findVertex(v2);
if (index1 != -1 && index2 != -1) {
adjMat[index1][index2] = 1;
}
}
public int noSuccessor() {
for (int i = 0; i < noOfVertex; i++) {
boolean isVisited = false;
for (int j = i; j < noOfVertex; j++) {
if (adjMat[i][j] > 0) {
isVisited = true;
break;
}
}
if (!isVisited) {
return i;
}
}
return -1;
}
public void deleteVertex(int index) {
//int index = findVertex(v);
if (index != noOfVertex - 1) {
// System.out.println("No of Vertex: " + noOfVertex + "\tindex: " + index);
for (int i = index; i < noOfVertex-1; i++) {
vertex[i].vLabel = vertex[i + 1].vLabel;
moveRowUp(i, noOfVertex); // shift all rows next to given vertex to 1 row up.
moveColLeft(i, noOfVertex-1); // shift all column to 1 left from given vertex.
}
}
noOfVertex--;
}
public void topologicalSorting(){
int orig_nVerts = noOfVertex;
while(noOfVertex > 0){
int currVertex = noSuccessor();
if(currVertex == -1){
System.out.println("There is Cycle !!");
return;
}
//System.out.println("Total Vertex: " + noOfVertex + "\tCurrent Vertex: " + vertex[currVertex].vLabel + "\tIndex: " + currVertex);
// insert vertex label in sorted array (start at end)
sortedArray[noOfVertex-1] = vertex[currVertex].vLabel;
// delete vertex
deleteVertex(currVertex);
/*
System.out.println();
printMatrix();
System.out.println();
*
*/
}
System.out.print("Topological Sorted: ");
for(int i=0; i
}
System.out.println();
}
// ------------------
private void moveRowUp(int row, int length) {
for (int col = 0; col < length; col++) {
adjMat[row][col] = adjMat[row + 1][col];
}
}
// ------------------
private void moveColLeft(int col, int length) {
for (int row = 0; row < length; row++) {
adjMat[row][col] = adjMat[row][col + 1];
}
}
// ------------------------------------------------------------
public static void main(String args[]) {
AdjMatGraph graph = new AdjMatGraph();
Scanner stdin = new Scanner(new BufferedInputStream(System.in));
System.out.println("Please enter the #vertex #Edges !!");
graph.setNoVertex(stdin.nextInt());
graph.setNoEdges(stdin.nextInt());
System.out.println("Please enter the Edges
while (true) {
if (stdin.hasNextInt()) {
//System.out.println(stdin.nextInt());
graph.addEdge(stdin.nextInt(), stdin.nextInt());
} else {
break;
}
}
graph.printMatrix();
System.out.println("\n");
graph.DFS();
System.out.println();
graph.BFS();
}
}
No comments:
Post a Comment