C RSS C RSS

Topological Sort

Reply

•
•
Join Date: Jun 2009
Posts: 5
Reputation: largedimples is an unknown quantity at this point 
Solved Threads: 0
largedimples largedimples is offline Offline
Newbie Poster

Topological Sort

 
0
  #1
Oct 20th, 2009
Will some one please help with the topological sort problem. What am I doing wrong? Thanks in advance for your help!!
c Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. class Vertex 
  5. {
  6.   public char label;
  7.   public Vertex(char lab) 
  8.   {
  9.     label = lab;
  10.   }
  11. }
  12.  
  13. public class Graphs 
  14. {
  15.   private final int MAX_VERTS = 20;
  16.   private Vertex vertexList[]; // list of vertices
  17.   private int matrix[][]; // adjacency matrix
  18.   private int numVerts; // current number of vertices
  19.   private char sortedArray[];
  20.   public Graphs() 
  21.   {
  22.     vertexList = new Vertex[MAX_VERTS];
  23.     matrix = new int[MAX_VERTS][MAX_VERTS];
  24.     numVerts = 0;
  25.     for (int i = 0; i < MAX_VERTS; i++)
  26.       for (int k = 0; k < MAX_VERTS; k++)
  27.         matrix[i][k] = 0;
  28.     sortedArray = new char[MAX_VERTS]; // sorted vert labels
  29.   }
  30.  
  31.   public void addVertex(char lab) 
  32.   {
  33.     vertexList[numVerts++] = new Vertex(lab);
  34.   }
  35.  
  36.   public void addEdge(int start, int end) 
  37.   {
  38.     matrix[start][end] = 1;
  39.   }
  40.  
  41.   public void displayVertex(int v) 
  42.   {
  43.     printf(vertexList[v].label);
  44.   }
  45.  
  46.   // toplogical sort
  47.   public void topo() 
  48.   {
  49.     int orig_nVerts = numVerts; 
  50.  
  51. 	//vertices remain,
  52.     while (numVerts > 0)
  53.     {
  54.       // get a vertex with no successors, or -1
  55.       int currentVertex = noSuccessors();
  56.       if (currentVertex == -1) // must be a cycle
  57.       {
  58.         printf("ERROR: Graph has cycles");
  59.         return;
  60.       }
  61.       // insert vertex label in sorted array (start at end)
  62.       sortedArray[numVerts - 1] = vertexList[currentVertex].label;
  63.  
  64.       deleteVertex(currentVertex); // delete vertex
  65.     }
  66.  
  67.     // vertices all gone; display sortedArray
  68.     printf("Topologically sorted order: ");
  69.     for (int j = 0; j < orig_nVerts; j++)
  70.       printf(sortedArray[j]);
  71.     printf("");
  72.   }
  73.  
  74.   public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
  75.   { 
  76.     boolean isEdge; // edge from row to column in adjMat
  77.  
  78.     for (int row = 0; row < numVerts; row++) {
  79.       isEdge = false; // check edges
  80.       for (int col = 0; col < numVerts; col++) {
  81.         if (matrix[row][col] > 0) // if edge to another,
  82.         {
  83.           isEdge = true;
  84.           break; 
  85.         }
  86.       }
  87.       if (!isEdge) 
  88.         return row;
  89.     }
  90.     return -1; 
  91.   }
  92.  
  93.   public void deleteVertex(int delVert) {
  94.     if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
  95.     {
  96.       for (int j = delVert; j < numVerts - 1; j++)
  97.         vertexList[j] = vertexList[j + 1];
  98.  
  99.       for (int row = delVert; row < numVerts - 1; row++)
  100.         moveRowUp(row, numVerts);
  101.  
  102.       for (int col = delVert; col < numVerts - 1; col++)
  103.         moveColLeft(col, numVerts - 1);
  104.     }
  105.     numVerts--; // one less vertex
  106.   }
  107.  
  108.   private void moveRowUp(int row, int length) {
  109.     for (int col = 0; col < length; col++)
  110.       matrix[row][col] = matrix[row + 1][col];
  111.   }
  112.  
  113.   private void moveColLeft(int col, int length) {
  114.     for (int row = 0; row < length; row++)
  115.       matrix[row][col] = matrix[row][col + 1];
  116.   }
  117.  
  118.   public static void main(String[] args) {
  119.     Graphs g = new Graphs();
  120.     g.addVertex('A'); // 0
  121.     g.addVertex('B'); // 1
  122.     g.addVertex('C'); // 2
  123.     g.addVertex('D'); // 3
  124.     g.addVertex('E'); // 4
  125.     g.addVertex('F'); // 5
  126.     g.addVertex('G'); // 6
  127.     g.addVertex('H'); // 7
  128.  
  129.     g.addEdge(0, 3); // AD
  130.     g.addEdge(0, 4); // AE
  131.     g.addEdge(1, 4); // BE
  132.     g.addEdge(2, 5); // CF
  133.     g.addEdge(3, 6); // DG
  134.     g.addEdge(4, 6); // EG
  135.     g.addEdge(5, 7); // FH
  136.     g.addEdge(6, 7); // GH
  137.  
  138.     g.topo(); // do the sort
  139.   }
  140. }
Last edited by WaltP; Oct 20th, 2009 at 1:08 am. Reason: Added CODE tags -- with all the help about them, how could you miss using them????
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2006
Posts: 3,114
Reputation: WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of WaltP has much to be proud of 
Solved Threads: 281
Moderator
WaltP's Avatar
WaltP WaltP is offline Offline
Posting Sensei
 
0
  #2
Oct 20th, 2009
•
•
•
•
Originally Posted by largedimples View Post
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
The 3 Laws of the Procrastination Society:
1) Never do today that which can be put off until tomorrow
2) Tomorrow never comes
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2009
Posts: 5
Reputation: largedimples is an unknown quantity at this point 
Solved Threads: 0
largedimples largedimples is offline Offline
Newbie Poster
 
0
  #3
Oct 20th, 2009
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.

C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. class Vertex 
  5. {
  6.   public char label;
  7.   public Vertex(char lab) 
  8.   {
  9.     label = lab;
  10.   }
  11. }
  12.  
  13. public class Graphs 
  14. {
  15.   private final int MAX_VERTS = 20;
  16.   private Vertex vertexList[]; // list of vertices
  17.   private int matrix[][]; // adjacency matrix
  18.   private int numVerts; // current number of vertices
  19.   private char sortedArray[];
  20.   public Graphs() 
  21.   {
  22.     vertexList = new Vertex[MAX_VERTS];
  23.     matrix = new int[MAX_VERTS][MAX_VERTS];
  24.     numVerts = 0;
  25.     for (int i = 0; i < MAX_VERTS; i++)
  26.       for (int k = 0; k < MAX_VERTS; k++)
  27.         matrix[i][k] = 0;
  28.     sortedArray = new char[MAX_VERTS]; // sorted vert labels
  29.   }
  30.  
  31.   public void addVertex(char lab) 
  32.   {
  33.     vertexList[numVerts++] = new Vertex(lab);
  34.   }
  35.  
  36.   public void addEdge(int start, int end) 
  37.   {
  38.     matrix[start][end] = 1;
  39.   }
  40.  
  41.   public void displayVertex(int v) 
  42.   {
  43.     printf(vertexList[v].label);
  44.   }
  45.  
  46.   // toplogical sort
  47.   public void topo() 
  48.   {
  49.     int orig_nVerts = numVerts; 
  50.  
  51. 	//vertices remain,
  52.     while (numVerts > 0)
  53.     {
  54.       // get a vertex with no successors, or -1
  55.       int currentVertex = noSuccessors();
  56.       if (currentVertex == -1) // must be a cycle
  57.       {
  58.         printf("ERROR: Graph has cycles");
  59.         return;
  60.       }
  61.       // insert vertex label in sorted array (start at end)
  62.       sortedArray[numVerts - 1] = vertexList[currentVertex].label;
  63.  
  64.       deleteVertex(currentVertex); // delete vertex
  65.     }
  66.  
  67.     // vertices all gone; display sortedArray
  68.     printf("Topologically sorted order: ");
  69.     for (int j = 0; j < orig_nVerts; j++)
  70.       printf(sortedArray[j]);
  71.     printf("");
  72.   }
  73.  
  74.   public int noSuccessors() // returns vert with no successors (or -1 if no such verts)
  75.   { 
  76.     boolean isEdge; // edge from row to column in adjMat
  77.  
  78.     for (int row = 0; row < numVerts; row++) {
  79.       isEdge = false; // check edges
  80.       for (int col = 0; col < numVerts; col++) {
  81.         if (matrix[row][col] > 0) // if edge to another,
  82.         {
  83.           isEdge = true;
  84.           break; 
  85.         }
  86.       }
  87.       if (!isEdge) 
  88.         return row;
  89.     }
  90.     return -1; 
  91.   }
  92.  
  93.   public void deleteVertex(int delVert) {
  94.     if (delVert != numVerts - 1) // if not last vertex, delete from vertexList
  95.     {
  96.       for (int j = delVert; j < numVerts - 1; j++)
  97.         vertexList[j] = vertexList[j + 1];
  98.  
  99.       for (int row = delVert; row < numVerts - 1; row++)
  100.         moveRowUp(row, numVerts);
  101.  
  102.       for (int col = delVert; col < numVerts - 1; col++)
  103.         moveColLeft(col, numVerts - 1);
  104.     }
  105.     numVerts--; // one less vertex
  106.   }
  107.  
  108.   private void moveRowUp(int row, int length) {
  109.     for (int col = 0; col < length; col++)
  110.       matrix[row][col] = matrix[row + 1][col];
  111.   }
  112.  
  113.   private void moveColLeft(int col, int length) {
  114.     for (int row = 0; row < length; row++)
  115.       matrix[row][col] = matrix[row][col + 1];
  116.   }
  117.  
  118.   public static void main(String[] args) {
  119.     Graphs g = new Graphs();
  120.     g.addVertex('A'); // 0
  121.     g.addVertex('B'); // 1
  122.     g.addVertex('C'); // 2
  123.     g.addVertex('D'); // 3
  124.     g.addVertex('E'); // 4
  125.     g.addVertex('F'); // 5
  126.     g.addVertex('G'); // 6
  127.     g.addVertex('H'); // 7
  128.  
  129.     g.addEdge(0, 3); // AD
  130.     g.addEdge(0, 4); // AE
  131.     g.addEdge(1, 4); // BE
  132.     g.addEdge(2, 5); // CF
  133.     g.addEdge(3, 6); // DG
  134.     g.addEdge(4, 6); // EG
  135.     g.addEdge(5, 7); // FH
  136.     g.addEdge(6, 7); // GH
  137.  
  138.     g.topo(); // do the sort
  139.   }
  140. }

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 : '}'
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum
Thread Tools Search this Thread



#include * adobe ansi array asterisks binarysearch centimeter changingto char character cm convert copyimagefile cprogramme creafecopyofanytypeoffileinc database dynamic execv feet fgets file floatingpointvalidation fork function getlogicaldrivestrin givemetehcodez global grade gtkwinlinux hacking histogram ide inches include incrementoperators infiniteloop input interest intmain() iso kernel keyboard kilometer license linked linkedlist linux list locate looping lowest match matrix meter microsoft number oddnumber opendocumentformat opensource openwebfoundation owf pattern pdf performance pointer posix power probleminc process program programming radix recursion recv recvblocked research reversing segmentationfault sequential single socket socketprograming socketprogramming standard strchr string suggestions systemcall test threads turboc unix urboc user variable voidmain() wab whythiscodecausesegmentationfault windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC