Topological sorting question

[calvinfornia]

Hi, everyone. I'm now working on a topological sorting program, which reads in a data.txt and output the sorting result. However, there are some problems and I don't know how to fix it.

The data.txt contains groups of data as below:

5

1 2 3 4 5

3

1 > 3

5 > 2

3 > 4

Which means there are five layers, with indexes 1, 2, 3, 4, and 5, respectively. Also, there are three constraints, indicating “the first layer should be above the third layer”, “the fifth layer should be above the second layer”, and “the third layer should be above the fourth layer”.

And here is the code I've done so far(some variables hasn't been used yet):

//Graph.h
#include<iostream>
#include<list> 
#include<stack> 
using namespace std; 

// Class to represent a graph 
class Graph 
{ 

private:
	
    // Number of vertices 
    int vertex_num;    
  
    // Pointer to an array containing adjacency listsList 
    list<int> *adj; 
  
    // A function used by topologicalSort 
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); 
    
public: 

    // Constructor 
    Graph(int vertex_num);   
  
    // Function to add an edge between vertices v & w 
    void addEdge(int v, int w); 
    
    // Function used to adjust the index of stack 
    void Stack_adjust(int first_num, int diff, stack<int> &Stack);
  
    // Prints a Topological Sort of the complete graph 
    void topologicalSort(); 
}; 

//Graph.cpp
#include<iostream> 
#include<list> 
#include<stack> 
#include"Graph.h"

using namespace std; 

// Constructor  
Graph::Graph(int vertex_num) 
{ 
    this->vertex_num = vertex_num; 
    adj = new list<int>[vertex_num]; 
} 
  
  
// Function to add an edge between vertices v & w 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 
  
  
// Function used to adjust the index of stack 
void Graph::Stack_adjust(int first_num, int diff, stack<int> &Stack)
{
    Stack.top() = first_num + diff * Stack.top();
    cout << Stack.top() << " ";
}
  
  
// A recursive function used by topologicalSort 
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) 
{ 
    // Mark the current node as visited. 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for(i = adj[v].begin(); i != adj[v].end(); ++i) 
    {
	if(visited[*i] == false) 
	{
	     topologicalSortUtil(*i, visited, Stack); 
	}
    }
    // Push current vertex to stack which stores result 
    Stack.push(v); 
} 
  
  
// The function to do Topological Sort. It uses recursive  
// topologicalSortUtil() 
void Graph::topologicalSort() 
{ 
    stack<int> Stack; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[vertex_num]; 
    for (int i = 0; i < vertex_num; i++) 
    {
	visited[i] = false; 
    }
	
    // Call the recursive helper function to store Topological 
    // Sort starting from all vertices one by one 
    for (int i = 0; i < vertex_num; i++) 
    {
	if (visited[i] == false) 
        {
	     topologicalSortUtil(i, visited, Stack); 
       	}
    }
	
    // Print contents of stack 
    while (Stack.empty() == false) 
    { 
        cout << Stack.top() << " "; 
        Stack.pop(); 
    } 
} 
  

//main.cpp
#include<iostream>
#include<fstream>
#include<vector>
#include<list> 
#include<stack> 
#include<cmath>
#include"Graph.h"

using namespace std;

int main()
{
	
     ifstream infile;
	
     // Open and input the data file 
     infile.open("sample data.txt");
     if (infile.is_open())
     {
           cout << "File successfully open." << endl << endl;
     }
     else
     {
           cout << "File not opened.";
           exit(1);
     }
	
	
     while (!infile.eof())
     {
         // Read the vertices from the input data file
	 int vertex_num = 0, edge_num = 0;
	    
	 infile >> vertex_num;
	 Graph graph(vertex_num);
	 cout << "Number of vertices is : " << vertex_num << endl;
	
	 // Used to store all the vertices
	 vector<int> vertex_list;
	 for (int i = 0; i < vertex_num; i++)
	 {
	      int vertex;
	      infile >> vertex;
	      vertex_list.push_back(vertex);
	      cout << vertex << " ";
	 }
	 cout << endl;
	    
	 int first_num = vertex_list[0];
	 int diff = abs(vertex _list[1] - vertex_list[0]);
	    
	 // Read the edges from the input data file
	 infile >> edge_num;
	 cout << "Number of edges is : " << edge_num << endl;
	    
	 for (int i = 0; i < edge_num; i++)
	 {
	     int from;
	     int to;
	     char pointing;
	     infile >> from >> pointing >> to;
	     cout << from << pointing << to << endl;
	     //graph.addEdge(from , to);
	 }
	 cout << endl;
		
	 graph.topologicalSort();
	 cout << endl;

     }
    
    
return 0;
}

And there seems to be something wrong in line 64 of main.cpp, because when I uncomment
graph.addEdge(from , to)
, the for loop runs only one time, but I can't find what's wrong with it.
Thanks for your help in advance !

[ne555]

the code that you've posted does not compile

error: use of undeclared identifier 'layer_list'

fix that first and then we can talk about runtime or logic errors.

[calvinfornia]

Oops, sorry for missing that, I’ve fixed it !

[ne555]

no, you did not
line 45 main.cpp

[calvinfornia]

Right, thanks for reminding haha.
So now the problem is why does the for loop run only one time when
graph.addEdge(from , to);
is added in the loop.

When I add graph.addEdge(from , to); in the for loop, this is what I get:

File successfully open.

Number of vertices is : 47
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
Number of edges is : 65
86 > 83

--------------------------------
Process exited after 4.969 seconds with return value 3221225477

[Niccolo]

In graph.addEdge, from the data file offered, this output:

Number of edges is : 3
1>3
5>2

Shows that "from" is 5.


At that moment, graph shows that vertex_num is 5

However, this function:

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 

is taking in v, which is "from", at 5.

Since vertex_num is 5, the adj array was allocated to store 5 lists, which is from 0 to 4, and therefore 5 is going to cause a segmentation fault in *Nix, or a memory access error in Windows (the same thing), which fires an exception that is never caught, causing the program to terminate.

I suspect something similar is happening in the data example in your last post, where "from" is 86, but I doubt graph's adj has been allocated for 86 entries (I suspect it is 65), so the crash is similar.

I sense there are other problems, probably along similar lines, but you'll probably have to get past this one first.

To that end, consider:

// Class to represent a graph 
class Graph 
{ 

private:
	
    // Number of vertices 
    int vertex_num;    
  
    // Pointer to an array containing adjacency listsList 
    list<int> *adj; 

//.....more material
};    

Graph::Graph(int vertex_num) 
{ 
    this->vertex_num = vertex_num; 
    adj = new list<int>[vertex_num]; 
} 

Here you're resorting to a C style allocation for adj, creating an array of lists. I submit this should probably be switched to either std::array or std::vector, to do away with C style management of this dynamic allocation.

You could, for example, create a type:

typedef std::vector< std::list< int >> adj_lists;

Or something to similar effect, creating a vector of lists. Of course, now you must use "push_back" on adj, but that's a bit smarter in my opinion, though if you still prefer to index more easily with adj.[v] instead of push_back here:

// Function to add an edge between vertices v & w
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

Then perhaps you'd prefer std::array.

Either way, there is some mis-alignment between vertex_num and the "from" parameter to addEdge (parameter v in the body of addEdge), as it is exceeding the size of the allocated array of lists.

[ne555]

std::array needs the size to be known at compile time, not applicable here.

as the layer id may be any number, you can't just simply use it as the index of `adj' vector/dynamic array.
you may use a dictionary to translate them to the range [0; size)
or you could use a map to hold the graph structure
std::map< std::vector<int> > adj;

    // Call the recursive helper function to store Topological 
    // Sort starting from all vertices one by one 
    for (int i = 0; i < vertex_num; i++) 
    {
	if (visited[i] == false) 
        {
	     topologicalSortUtil(i, visited, Stack); 
       	}
    }

that's incorrect
consider this case:
a -> z
b -> z
the order that you want would be {a, b, z} or {b, a, z} but that loop will print {a, z, b} or {b, z, a} instead
you cannot print a node if there is another no-visited node that points to it.