WaltP
Posting Sage w/ dash of thyme
Moderator
10,492 posts since May 2006
Reputation Points: 3,348
Solved Threads: 943
Have something to say? Contribute New Article Reply to this Article
Topological Sort
Will some one please help with the topological sort problem. What am I doing wrong? Thanks in advance for your help!!
#include <stdio.h>
#include <limits.h>
class Vertex
{
public char label;
public Vertex(char lab)
{
label = lab;
}
}
public class Graphs
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int matrix[][]; // adjacency matrix
private int numVerts; // current number of vertices
private char sortedArray[];
public Graphs()
{
vertexList = new Vertex[MAX_VERTS];
matrix = new int[MAX_VERTS][MAX_VERTS];
numVerts = 0;
for (int i = 0; i < MAX_VERTS; i++)
for (int k = 0; k < MAX_VERTS; k++)
matrix[i][k] = 0;
sortedArray = new char[MAX_VERTS]; // sorted vert labels
}
public void addVertex(char lab)
{
vertexList[numVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
matrix[start][end] = 1;
}
public void displayVertex(int v)
{
printf(vertexList[v].label);
}
// toplogical sort
public void topo()
{
int orig_nVerts = numVerts;
//vertices remain,
while (numVerts > 0)
{
// get a vertex with no successors, or -1
int currentVertex = noSuccessors();
if (currentVertex == -1) // must be a cycle
{
printf("ERROR: Graph has cycles");
return;
}
// insert vertex label in sorted array (start at end)
sortedArray[numVerts - 1] = vertexList[currentVertex].label;
deleteVertex(currentVertex); // delete vertex
}
// vertices all gone; display sortedArray
printf("Topologically sorted order: ");
for (int j = 0; j < orig_nVerts; j++)
printf(sortedArray[j]);
printf("");
}
public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
{
boolean isEdge; // edge from row to column in adjMat
for (int row = 0; row < numVerts; row++) {
isEdge = false; // check edges
for (int col = 0; col < numVerts; col++) {
if (matrix[row][col] > 0) // if edge to another,
{
isEdge = true;
break;
}
}
if (!isEdge)
return row;
}
return -1;
}
public void deleteVertex(int delVert) {
if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
{
for (int j = delVert; j < numVerts - 1; j++)
vertexList[j] = vertexList[j + 1];
for (int row = delVert; row < numVerts - 1; row++)
moveRowUp(row, numVerts);
for (int col = delVert; col < numVerts - 1; col++)
moveColLeft(col, numVerts - 1);
}
numVerts--; // one less vertex
}
private void moveRowUp(int row, int length) {
for (int col = 0; col < length; col++)
matrix[row][col] = matrix[row + 1][col];
}
private void moveColLeft(int col, int length) {
for (int row = 0; row < length; row++)
matrix[row][col] = matrix[row][col + 1];
}
public static void main(String[] args) {
Graphs g = new Graphs();
g.addVertex('A'); // 0
g.addVertex('B'); // 1
g.addVertex('C'); // 2
g.addVertex('D'); // 3
g.addVertex('E'); // 4
g.addVertex('F'); // 5
g.addVertex('G'); // 6
g.addVertex('H'); // 7
g.addEdge(0, 3); // AD
g.addEdge(0, 4); // AE
g.addEdge(1, 4); // BE
g.addEdge(2, 5); // CF
g.addEdge(3, 6); // DG
g.addEdge(4, 6); // EG
g.addEdge(5, 7); // FH
g.addEdge(6, 7); // GH
g.topo(); // do the sort
}
}Thank for commenting!
I had to Write a program to perform a topological sort on a graph. The program should accept a graph (a list of vertices and corresponding edges) as input and produce the topological sorting order as output.
#include <stdio.h>
#include <limits.h>
class Vertex
{
public char label;
public Vertex(char lab)
{
label = lab;
}
}
public class Graphs
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int matrix[][]; // adjacency matrix
private int numVerts; // current number of vertices
private char sortedArray[];
public Graphs()
{
vertexList = new Vertex[MAX_VERTS];
matrix = new int[MAX_VERTS][MAX_VERTS];
numVerts = 0;
for (int i = 0; i < MAX_VERTS; i++)
for (int k = 0; k < MAX_VERTS; k++)
matrix[i][k] = 0;
sortedArray = new char[MAX_VERTS]; // sorted vert labels
}
public void addVertex(char lab)
{
vertexList[numVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
matrix[start][end] = 1;
}
public void displayVertex(int v)
{
printf(vertexList[v].label);
}
// toplogical sort
public void topo()
{
int orig_nVerts = numVerts;
//vertices remain,
while (numVerts > 0)
{
// get a vertex with no successors, or -1
int currentVertex = noSuccessors();
if (currentVertex == -1) // must be a cycle
{
printf("ERROR: Graph has cycles");
return;
}
// insert vertex label in sorted array (start at end)
sortedArray[numVerts - 1] = vertexList[currentVertex].label;
deleteVertex(currentVertex); // delete vertex
}
// vertices all gone; display sortedArray
printf("Topologically sorted order: ");
for (int j = 0; j < orig_nVerts; j++)
printf(sortedArray[j]);
printf("");
}
public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
{
boolean isEdge; // edge from row to column in adjMat
for (int row = 0; row < numVerts; row++) {
isEdge = false; // check edges
for (int col = 0; col < numVerts; col++) {
if (matrix[row][col] > 0) // if edge to another,
{
isEdge = true;
break;
}
}
if (!isEdge)
return row;
}
return -1;
}
public void deleteVertex(int delVert) {
if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
{
for (int j = delVert; j < numVerts - 1; j++)
vertexList[j] = vertexList[j + 1];
for (int row = delVert; row < numVerts - 1; row++)
moveRowUp(row, numVerts);
for (int col = delVert; col < numVerts - 1; col++)
moveColLeft(col, numVerts - 1);
}
numVerts--; // one less vertex
}
private void moveRowUp(int row, int length) {
for (int col = 0; col < length; col++)
matrix[row][col] = matrix[row + 1][col];
}
private void moveColLeft(int col, int length) {
for (int row = 0; row < length; row++)
matrix[row][col] = matrix[row][col + 1];
}
public static void main(String[] args) {
Graphs g = new Graphs();
g.addVertex('A'); // 0
g.addVertex('B'); // 1
g.addVertex('C'); // 2
g.addVertex('D'); // 3
g.addVertex('E'); // 4
g.addVertex('F'); // 5
g.addVertex('G'); // 6
g.addVertex('H'); // 7
g.addEdge(0, 3); // AD
g.addEdge(0, 4); // AE
g.addEdge(1, 4); // BE
g.addEdge(2, 5); // CF
g.addEdge(3, 6); // DG
g.addEdge(4, 6); // EG
g.addEdge(5, 7); // FH
g.addEdge(6, 7); // GH
g.topo(); // do the sort
}
}
errors:
Line 4: error C2061: syntax error : identifier 'Vertex'
Line 4: error C2059: syntax error : ';'
Line 5: error C2449: found '{' at file scope (missing function header?)
Line 11: error C2059: syntax error : '}'
Simply because you have copied the code (from here I think) and you don't know that this is written in Java and not in C.
This is an OOP based program, and C has no OOP support. So, you need to post this in either a Java, or maybe even a C++ forum. Definitely, not here.
Adak
Nearly a Posting Virtuoso
1,479 posts since Jun 2008
Reputation Points: 425
Solved Threads: 185
WaltP
Posting Sage w/ dash of thyme
Moderator
10,492 posts since May 2006
Reputation Points: 3,348
Solved Threads: 943
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
