C++

Forum

 
Problem when writing Kosaraju’s algorithm on Mac

kaiwei (14)
I ran some C++ codes in order to realize Kosaraju’s algorithm on my mac. I want to output the largest 5 SCCs in terms of their number of nodes. I have to write a class of graph. I don't know whether my class of graph is OK. The code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <fstream>
#include <iostream>
#include <list>
#include <stack>
#include <string>
#include <vector>

using namespace std;

class Graph
{
	int V; // No. of vertices
	list<int> * adj; 
public:
	Graph();
	Graph(int v);
	Graph getTrans(); // reverse graph
	int DFSlen (int v, bool visited[]); // return the length of the SCC of v
	void fillOrder (int v, bool visited[], stack<int> &Stack);
	vector<int> top5SCC();
	void parseFile(const string filename);
};

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

Graph Graph::getTrans(){
	Graph g(V);
	for (int i = 0; i < V; ++i){
		list<int>::iterator j;
		for(j = adj[i].begin(); j != adj[i].end(); ++j)
			g.adj[*j].push_back(i);
	}
	return g;
}

int Graph::DFSlen (int v, bool visited[]) {
	visited[v] = true;
	static int len = 0;
	len += 1;
	list<int>::iterator i;
	for(i = adj[v].begin(); i != adj[v].end(); ++i)
	{
		if (!visited[*i])
			DFSlen (*i, visited);
	}
	return len;
}

void Graph::fillOrder (int v, bool visited[], stack<int> &Stack){
	visited[v] = true;
	list<int>::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i)
	{
		if (!visited[*i])
			fillOrder(*i, visited, Stack);
	}
	Stack.push(v);
}

int getNodeCount(const string filename){
	ifstream graphFile(filename);
	int n = 0;
	string str;
	while(getline(graphFile, str, '\n')){
		++n;
	}
	return n;
}

// parse file into graph
void Graph::parseFile(const string filename){
	this->V = getNodeCount(filename);
	ifstream graphFile(filename);
	int nodeIndex;
	int outIndex;
	
	while (graphFile) {
		graphFile >> nodeIndex;
		graphFile >> outIndex;
		adj[nodeIndex - 1].push_back(outIndex - 1);
	}
}

void top5array(vector<int>& ar, int a){
	int temp = 0;
	int i = 0;
	for(; i < 5; ++i)
	{
		if(a > ar[i])
		{
			temp = ar[i];
			ar[i] = a;
			break;
		}
	}
	if(i<4){
		ar[i+1] = temp;
		for(int j = 4; j>i+1; --j)
			ar[j] = ar[j-1];
	}
}

vector<int> Graph::top5SCC(){
	stack<int> Stack;
	vector<int> vec(5, 0);
	bool *visited = new bool[V];
	for (int i = 0; i < V; ++i)
		visited[i] = false;
	for (int i = 0; i < V; ++i)
		if (!visited[i])
			fillOrder(i, visited, Stack);
		Graph gr = getTrans();
	for (int i = 0; i < V; ++i)
		visited[i] = false;
	while (!Stack.empty())
	{
		int v = Stack.top();
		Stack.pop();
		if (!visited[v])
		{
			top5array(vec, gr.DFSlen(v, visited));
		}
	} 
	return vec;
}

int main()
{
	Graph g(5);
	g.parseFile("1.txt");
	vector<int> a = g.top5SCC();
	for(int i = 0; i < a.size(); ++i)
		cout << a[i] << endl;
	return 0;
}


Here "1.txt" is a file
1
2
3
4
5
6
7
8
9
10
11
 
1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 5
8 6
9 7
9 3


Then I just got the following error massage from the terminal:

1
2
3
4
5
6
7
8
9
10
11
 
Undefined symbols for architecture x86_64:
  "std::__1::__vector_base_common<true>::__throw_length_error() const", referenced from:
      std::__1::vector<int, std::__1::allocator<int> >::allocate(unsigned long) in kosaraju-a4f23c.o
  "std::__1::locale::has_facet(std::__1::locale::id&) const", referenced from:
      std::__1::basic_filebuf<char, std::__1::char_traits<char> >::basic_filebuf() in kosaraju-a4f23c.o
  "std::__1::locale::use_facet(std::__1::locale::id&) const", referenced from:
      std::__1::basic_ostream<char, std::__1::char_traits<char> >& std::__1::endl<char, std::__1::char_traits<char> >(std::__1::basic_ostream<char, std::__1::char_traits<char> >&) in kosaraju-a4f23c.o
      std::__1::basic_filebuf<char, std::__1::char_traits<char> >::imbue(std::__1::locale const&) in kosaraju-a4f23c.o
      std::__1::basic_filebuf<char, std::__1::char_traits<char> >::basic_filebuf() in kosaraju-a4f23c.o
  "std::__1::ios_base::getloc() const", referenced from:
...


The message is quite long and I just post a piece of it.

Anyone knows what is the problem? Many thanks ahead.
Last edited on
ne555 (10692)
¿is that a build error? If that's the case, show your build command and the full error message.

However, your program seg-fault.
iirc in 1.txt you say that there are going to be 11 nodes (maybe is an upper limit), but your graph is initialized for just 5 nodes Graph g(5);


By the way, you don't have a single delete[]
Topic archived. No new replies allowed.