Programming-Helpers/topological_Sort.java at main · manitgupt14/Programming-Helpers · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package GraphAlgorithms;
import java.util.*;
class Vertex
{
	public char label;
public Vertex(char lab)
{
	label=lab;
}
}
class Graph
{
	private final int maxVertex=20;
	private Vertex vertexList[];
	private int adjmat[][];
	private  int nverts;
	private char sortedArray[];
	public Graph()
	{
		vertexList=new Vertex[maxVertex];
		adjmat=new int[maxVertex][maxVertex];
	    nverts=0;
	    for(int i=0;i<maxVertex;i++)
	    {
	    	for(int j=0;j<maxVertex;j++)
	    	{
	    		adjmat[i][j]=0;
	    	}
	    }
	    sortedArray=new char[maxVertex];
	}
	public void addVertex(char lab)
	{
		vertexList[nverts++]=new Vertex(lab);
	}
	public void addEdge(int start,int end)
	{
		adjmat[start][end]=1;
	}
	public void displayVertex(int v)
	{
		System.out.println(vertexList[v].label);
	}
	public void topo()
	{
		int ori_nverts=nverts;
		while(nverts>0)
		{
			int currentVertex=noSuccessor();
			if(currentVertex==-1)
			{	System.out.println("Error:Graph has cycles");
			return ;}
			sortedArray[nverts-1]=vertexList[currentVertex].label;
			deleteVertex(currentVertex);
		}
		System.out.println("Topological sorted order");
		for(int i=0;i<ori_nverts;i++)
	    System.out.print(sortedArray[i]+" ");
		System.out.println(" ");
	}
	public int noSuccessor()
	{
		boolean isEdge;
		for(int row=0;row<nverts;row++)
		{
			isEdge=false;
			for(int col=0;col<nverts;col++)
			{
				if(adjmat[row][col]>0)
				{
					isEdge=true;
					break;
				}
			}
			if(!isEdge)
			return row;
		}
		return -1;
	}
	public void deleteVertex(int delVertex)
	{
		if(delVertex!=nverts-1)
		{
			for(int i=delVertex;i<nverts;i++)
				vertexList[i]=vertexList[i+1];
			for(int row=delVertex;row<nverts;row++)
				moverowUp(row,nverts);
			for(int col=delVertex;col<nverts;col++)
				moveColLeft(delVertex,nverts);
		}
		nverts--;
	}
	public void moverowUp(int row,int length)
	{
		for(int col=0;col<length;col++)
			adjmat[row][col]=adjmat[row+1][col];
	}
	public void moveColLeft(int col,int length)
	{
		for(int row=0;row<length;row++)
			adjmat[row][col]=adjmat[row][col+1];
	}
}
public class topologicalsort {
public static void main(String args[])
{
	Graph theGraph=new Graph();
	theGraph.addVertex('A');
	theGraph.addVertex('B');
	theGraph.addVertex('C');
	theGraph.addVertex('D');
	theGraph.addVertex('E');
	theGraph.addVertex('F');
	theGraph.addVertex('G');
	theGraph.addVertex('H');
    theGraph.addEdge(0, 3);
    theGraph.addEdge(0, 4);
    theGraph.addEdge(0, 3);
    theGraph.addEdge(1, 4);
    theGraph.addEdge(2, 5);
    theGraph.addEdge(3, 6);
    theGraph.addEdge(4, 6);
    theGraph.addEdge(5, 7);
    theGraph.addEdge(6, 7);
	theGraph.topo();
}

}