0

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 by WaltP: Added CODE tags -- with all the help about them, how could you miss using them????

4
Contributors
5
Replies
8
Views
7 Years
Discussion Span
Last Post by WaltP
0

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

0

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

-1

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!
0

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.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.