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
  }
}

Edited 7 Years Ago by WaltP: Added CODE tags -- with all the help about them, how could you miss using them????

Will some one please help with the topological sort problem. What am I doing wrong? Thanks in advance for your help!!

1) Using a useless BOLD for your question
2) Not using CODE tags
3) Not explaining what your problem is
4) Not telling us about where in your code the problem is

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.

Comments
Do not resurrect 2 year old posts for this type of comment! Jeez!

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.

This article has been dead for over six months. Start a new discussion instead.