-
August 1st, 2007, 04:18 PM
#1
Topological Sort Algrithm
I need to write a program that takes a graph using adjacency lists and prints the topological order of the graph. How the hell do I do this? I know how to find the topological order, but I have to calculate in the program the indegree of each vertex. I have no idea how to implement this. If any of you guys can help explain it, that'd be much appretiated.
The book mentions using maps to implement the adjacency lists, but i'm pretty confused. If my list looks like this:
Code:
s -> A, D, G
A -> B, E
B -> C
C -> t
D -> A, E
E -> C, F, I
F -> C, t
G -> D, E, H
H -> E, I
I -> F, t
t -> nothing
how would I turn that into a map? and how would I find the indegree of each vertex? If you can't tell, I'm pretty confused. Please help.
-
August 1st, 2007, 08:37 PM
#2
Re: Topological Sort Algrithm
taking the "s -> A, D, G" statement alone. i'm going to assume it means s is adjacent to A, D, and G - so outdegree of 3, and A, D, and G have indegree of 1 each. so take it one step at a time - if A, for example, appears on the left, incerement its indegree, if it appears on the right, increment its outdegree. so perhaps:
Code:
typedef pair<unsigned int, unsigned int> deg_t;
map<char, deg_t> graph;
where deg_t.first is the indegree, deg_t.second is outdegree. iterate through the adjacency list, get the left and right sides, parse, increment the respective value in the map.
good luck man, take it slow, take it easy, take it one step at a time.
-
August 1st, 2007, 09:53 PM
#3
Re: Topological Sort Algrithm
The adjacency list was given on a piece of paper. It's not in the program, I have to put it in. I'm also not sure what you mean by "if A, for example, appears on the left, incerement its indegree, if it appears on the right, increment its outdegree" could you clarify that, please? also, would I have to make 2 maps for this? one holding the adjacency list that looks like map<char, array> adlist that would say adlist["s"] = [A, D, G], etc. and another that looks like you're example that says graph["s"] = [0, 3]?
-
August 1st, 2007, 10:45 PM
#4
Re: Topological Sort Algrithm
I recommend you should do this:
First of all, star in a node, lets call it node[0]. Find the nodes that are adjacency, or the nodes that are child of it, but... not call them child, because this is a graph, is only for confusion, but sometimes it is easy. Well, the node[0] has a indegree of the adjacency nodes (If they are 4 nodes, then you have 4 indegree...). Apart from that, the adjacency nodes have to increment their outdegree by one.
You are thinking "How on earth do i do that?" Well, with a BFC it is easy.
If you didn't understand I will give you same examples:
Node A = [2, 2]
It has two indegrees that are B and E, and has two outdegrees that are S and D.
-
August 1st, 2007, 10:58 PM
#5
Re: Topological Sort Algrithm
is it possible to create an array of strings? i was thinking i could do something like s=["A", "D", "G"]
-
August 2nd, 2007, 07:53 AM
#6
Re: Topological Sort Algrithm
how about something like this:
Code:
template <typename T>
struct vector_builder
{
vector<T> m_vec;
vector_builder() {}
vector_builder(const T& c) : m_vec(1)
{
m_vec.push_back(c);
}
vector_builder(const vector_builder<T>& rhs) : m_vec(rhs) {}
vector_builder<T>& operator ()(const T& c)
{
m_vec.push_back(c);
return *this;
}
operator vector<T>&() { return m_vec; }
};
class AdjecencyList {
private:
typedef vector<char> adj_list;
typedef pair<char, adj_list> adj_pair;
vector<adj_pair> m_list;
public:
AdjecencyList() {}
~AdjecencyList() {}
AdjecencyList& Add(char s, const adj_list& l)
{
m_list.push_back(make_pair(s, l));
return *this;
}
void Print() const
{
vector<adj_pair>::const_iterator i = m_list.begin();
for (; i != m_list.end(); ++i) {
cout<<i->first<<" is adjecent to ";
adj_list::const_iterator j = i->second.begin();
for (; j != i->second.end(); ++j)
cout<<*j<<" ";
cout<<endl;
}
}
};
int main(int argc, char *argv[])
{
AdjecencyList List;
List.Add('s', vector_builder<char>('A')('D')('G'))
.Add('A', vector_builder<char>('B')('E'))
.Add('B', vector_builder<char>('C'));
List.Print();
return 0;
}
-
August 2nd, 2007, 07:01 PM
#7
Re: Topological Sort Algrithm
ok, since i'm having trouble grasping this, i've decided to do it an easy way and then refine it. since it's done really easy, it's pretty long, so any help you guys can give to make it shorter would be good. here's what i've got:
Code:
int main () {
//creates map of adjacency list
map<char, set<char> >adlist;
adlist['s'].insert('A');
adlist['s'].insert('D');
adlist['s'].insert('G');
adlist['A'].insert('B');
adlist['A'].insert('E');
adlist['B'].insert('C');
adlist['C'].insert('t');
adlist['D'].insert('A');
adlist['D'].insert('E');
adlist['E'].insert('C');
adlist['E'].insert('F');
adlist['E'].insert('I');
adlist['F'].insert('C');
adlist['F'].insert('t');
adlist['G'].insert('D');
adlist['G'].insert('E');
adlist['G'].insert('H');
adlist['H'].insert('E');
adlist['H'].insert('I');
adlist['I'].insert('F');
adlist['I'].insert('t');
//creates map of indegree
map<char, int> indegree;
indegree['s'];
indegree['A'];
indegree['B'];
indegree['C'];
indegree['D'];
indegree['E'];
indegree['F'];
indegree['G'];
indegree['H'];
indegree['I'];
indegree['t'];
//searches adlist for vertex: if vertex is found, indegree[vertex]++
set<char>::iterator it;
it=adlist['s'].find('s');
if(it!=adlist['s'].end())
indegree['s']++;
it=adlist['s'].find('A');
if(it!=adlist['s'].end())
indegree['A']++;
it=adlist['s'].find('B');
if(it!=adlist['s'].end())
indegree['B']++;
it=adlist['s'].find('C');
if(it!=adlist['s'].end())
indegree['C']++;
it=adlist['s'].find('D');
if(it!=adlist['s'].end())
indegree['D']++;
it=adlist['s'].find('E');
if(it!=adlist['s'].end())
indegree['E']++;
it=adlist['s'].find('F');
if(it!=adlist['s'].end())
indegree['F']++;
it=adlist['s'].find('G');
if(it!=adlist['s'].end())
indegree['G']++;
it=adlist['s'].find('H');
if(it!=adlist['s'].end())
indegree['H']++;
it=adlist['s'].find('I');
if(it!=adlist['s'].end())
indegree['I']++;
it=adlist['s'].find('t');
if(it!=adlist['s'].end())
indegree['t']++;
it=adlist['A'].find('s');
if(it!=adlist['A'].end())
indegree['s']++;
it=adlist['A'].find('A');
if(it!=adlist['A'].end())
indegree['A']++;
it=adlist['A'].find('B');
if(it!=adlist['A'].end())
indegree['B']++;
it=adlist['A'].find('C');
if(it!=adlist['A'].end())
indegree['C']++;
it=adlist['A'].find('D');
if(it!=adlist['A'].end())
indegree['D']++;
it=adlist['A'].find('E');
if(it!=adlist['A'].end())
indegree['E']++;
it=adlist['A'].find('F');
if(it!=adlist['A'].end())
indegree['F']++;
it=adlist['A'].find('G');
if(it!=adlist['A'].end())
indegree['G']++;
it=adlist['A'].find('H');
if(it!=adlist['A'].end())
indegree['H']++;
it=adlist['A'].find('I');
if(it!=adlist['A'].end())
indegree['I']++;
it=adlist['A'].find('t');
if(it!=adlist['A'].end())
indegree['t']++;
it=adlist['B'].find('s');
if(it!=adlist['B'].end())
indegree['s']++;
it=adlist['B'].find('A');
if(it!=adlist['B'].end())
indegree['A']++;
it=adlist['B'].find('B');
if(it!=adlist['B'].end())
indegree['B']++;
it=adlist['B'].find('C');
if(it!=adlist['B'].end())
indegree['C']++;
it=adlist['B'].find('D');
if(it!=adlist['B'].end())
indegree['D']++;
it=adlist['B'].find('E');
if(it!=adlist['B'].end())
indegree['E']++;
it=adlist['B'].find('F');
if(it!=adlist['B'].end())
indegree['F']++;
it=adlist['B'].find('G');
if(it!=adlist['B'].end())
indegree['G']++;
it=adlist['B'].find('H');
if(it!=adlist['B'].end())
indegree['H']++;
it=adlist['B'].find('I');
if(it!=adlist['B'].end())
indegree['I']++;
it=adlist['B'].find('t');
if(it!=adlist['B'].end())
indegree['t']++;
it=adlist['C'].find('s');
if(it!=adlist['C'].end())
indegree['s']++;
it=adlist['C'].find('A');
if(it!=adlist['C'].end())
indegree['A']++;
it=adlist['C'].find('B');
if(it!=adlist['C'].end())
indegree['B']++;
it=adlist['C'].find('C');
if(it!=adlist['C'].end())
indegree['C']++;
it=adlist['C'].find('D');
if(it!=adlist['C'].end())
indegree['D']++;
it=adlist['C'].find('E');
if(it!=adlist['C'].end())
indegree['E']++;
it=adlist['C'].find('F');
if(it!=adlist['C'].end())
indegree['F']++;
it=adlist['C'].find('G');
if(it!=adlist['C'].end())
indegree['G']++;
it=adlist['C'].find('H');
if(it!=adlist['C'].end())
indegree['H']++;
it=adlist['C'].find('I');
if(it!=adlist['C'].end())
indegree['I']++;
it=adlist['C'].find('t');
if(it!=adlist['C'].end())
indegree['t']++;
it=adlist['D'].find('s');
if(it!=adlist['D'].end())
indegree['s']++;
it=adlist['D'].find('A');
if(it!=adlist['D'].end())
indegree['A']++;
it=adlist['D'].find('B');
if(it!=adlist['D'].end())
indegree['B']++;
it=adlist['D'].find('C');
if(it!=adlist['D'].end())
indegree['C']++;
it=adlist['D'].find('D');
if(it!=adlist['D'].end())
indegree['D']++;
it=adlist['D'].find('E');
if(it!=adlist['D'].end())
indegree['E']++;
it=adlist['D'].find('F');
if(it!=adlist['D'].end())
indegree['F']++;
it=adlist['D'].find('G');
if(it!=adlist['D'].end())
indegree['G']++;
it=adlist['D'].find('H');
if(it!=adlist['D'].end())
indegree['H']++;
it=adlist['D'].find('I');
if(it!=adlist['D'].end())
indegree['I']++;
it=adlist['D'].find('t');
if(it!=adlist['D'].end())
indegree['t']++;
it=adlist['E'].find('s');
if(it!=adlist['E'].end())
indegree['s']++;
it=adlist['E'].find('A');
if(it!=adlist['E'].end())
indegree['A']++;
it=adlist['E'].find('B');
if(it!=adlist['E'].end())
indegree['B']++;
it=adlist['E'].find('C');
if(it!=adlist['E'].end())
indegree['C']++;
it=adlist['E'].find('D');
if(it!=adlist['E'].end())
indegree['D']++;
it=adlist['E'].find('E');
if(it!=adlist['E'].end())
indegree['E']++;
it=adlist['E'].find('F');
if(it!=adlist['E'].end())
indegree['F']++;
it=adlist['E'].find('G');
if(it!=adlist['E'].end())
indegree['G']++;
it=adlist['E'].find('H');
if(it!=adlist['E'].end())
indegree['H']++;
it=adlist['E'].find('I');
if(it!=adlist['E'].end())
indegree['I']++;
it=adlist['E'].find('t');
if(it!=adlist['E'].end())
indegree['t']++;
it=adlist['F'].find('s');
if(it!=adlist['F'].end())
indegree['s']++;
it=adlist['F'].find('A');
if(it!=adlist['F'].end())
indegree['A']++;
it=adlist['F'].find('B');
if(it!=adlist['F'].end())
indegree['B']++;
it=adlist['F'].find('C');
if(it!=adlist['F'].end())
indegree['C']++;
it=adlist['F'].find('D');
if(it!=adlist['F'].end())
indegree['D']++;
it=adlist['F'].find('E');
if(it!=adlist['F'].end())
indegree['E']++;
it=adlist['F'].find('F');
if(it!=adlist['F'].end())
indegree['F']++;
it=adlist['F'].find('G');
if(it!=adlist['F'].end())
indegree['G']++;
it=adlist['F'].find('H');
if(it!=adlist['F'].end())
indegree['H']++;
it=adlist['F'].find('I');
if(it!=adlist['F'].end())
indegree['I']++;
it=adlist['F'].find('t');
if(it!=adlist['F'].end())
indegree['t']++;
it=adlist['G'].find('s');
if(it!=adlist['G'].end())
indegree['s']++;
it=adlist['G'].find('A');
if(it!=adlist['G'].end())
indegree['A']++;
it=adlist['G'].find('B');
if(it!=adlist['G'].end())
indegree['B']++;
it=adlist['G'].find('C');
if(it!=adlist['G'].end())
indegree['C']++;
it=adlist['G'].find('D');
if(it!=adlist['G'].end())
indegree['D']++;
it=adlist['G'].find('E');
if(it!=adlist['G'].end())
indegree['E']++;
it=adlist['G'].find('F');
if(it!=adlist['G'].end())
indegree['F']++;
it=adlist['G'].find('G');
if(it!=adlist['G'].end())
indegree['G']++;
it=adlist['G'].find('H');
if(it!=adlist['G'].end())
indegree['H']++;
it=adlist['G'].find('I');
if(it!=adlist['G'].end())
indegree['I']++;
it=adlist['G'].find('t');
if(it!=adlist['G'].end())
indegree['t']++;
it=adlist['H'].find('s');
if(it!=adlist['H'].end())
indegree['s']++;
it=adlist['H'].find('A');
if(it!=adlist['H'].end())
indegree['A']++;
it=adlist['H'].find('B');
if(it!=adlist['H'].end())
indegree['B']++;
it=adlist['H'].find('C');
if(it!=adlist['H'].end())
indegree['C']++;
it=adlist['H'].find('D');
if(it!=adlist['H'].end())
indegree['D']++;
it=adlist['H'].find('E');
if(it!=adlist['H'].end())
indegree['E']++;
it=adlist['H'].find('F');
if(it!=adlist['H'].end())
indegree['F']++;
it=adlist['H'].find('G');
if(it!=adlist['H'].end())
indegree['G']++;
it=adlist['H'].find('H');
if(it!=adlist['H'].end())
indegree['H']++;
it=adlist['H'].find('I');
if(it!=adlist['H'].end())
indegree['I']++;
it=adlist['H'].find('t');
if(it!=adlist['H'].end())
indegree['t']++;
it=adlist['I'].find('s');
if(it!=adlist['I'].end())
indegree['s']++;
it=adlist['I'].find('A');
if(it!=adlist['I'].end())
indegree['A']++;
it=adlist['I'].find('B');
if(it!=adlist['I'].end())
indegree['B']++;
it=adlist['I'].find('C');
if(it!=adlist['I'].end())
indegree['C']++;
it=adlist['I'].find('D');
if(it!=adlist['I'].end())
indegree['D']++;
it=adlist['I'].find('E');
if(it!=adlist['I'].end())
indegree['E']++;
it=adlist['I'].find('F');
if(it!=adlist['I'].end())
indegree['F']++;
it=adlist['I'].find('G');
if(it!=adlist['I'].end())
indegree['G']++;
it=adlist['I'].find('H');
if(it!=adlist['I'].end())
indegree['H']++;
it=adlist['I'].find('I');
if(it!=adlist['I'].end())
indegree['I']++;
it=adlist['I'].find('t');
if(it!=adlist['I'].end())
indegree['t']++;
//prints indegree of verticies
cout<<"indegree of s is: "<<indegree['s']<<endl;
cout<<"indegree of A is: "<<indegree['A']<<endl;
cout<<"indegree of B is: "<<indegree['B']<<endl;
cout<<"indegree of C is: "<<indegree['C']<<endl;
cout<<"indegree of D is: "<<indegree['D']<<endl;
cout<<"indegree of E is: "<<indegree['E']<<endl;
cout<<"indegree of F is: "<<indegree['F']<<endl;
cout<<"indegree of G is: "<<indegree['G']<<endl;
cout<<"indegree of H is: "<<indegree['H']<<endl;
cout<<"indegree of I is: "<<indegree['I']<<endl;
cout<<"indegree of t is: "<<indegree['t']<<endl;
return 0;
}
like i said, really long. help?
-
August 2nd, 2007, 08:20 PM
#8
Re: Topological Sort Algrithm
Yes. First of all, I you would rather recommend you do a BFS function. That Topological Sort is very nasty and hard-code, but, well the idea is better now for you.
Do a BFS function, and then you will realize HOW to do the Topological Sort better.
-
August 2nd, 2007, 08:21 PM
#9
Re: Topological Sort Algrithm
-
August 2nd, 2007, 09:00 PM
#10
Re: Topological Sort Algrithm
holy <explative deleted>, that's long! if it works, it works man. bfs = breadth first search (http://en.wikipedia.org/wiki/Breadth-first_search)
-
August 2nd, 2007, 09:24 PM
#11
Re: Topological Sort Algrithm
The BFS is a tree-traversal algorithm applied in Graphs (And Binary Trees) for visiting all the nodes.
-
August 3rd, 2007, 02:00 PM
#12
Re: Topological Sort Algrithm
ok, so i've cleaned the code up. i decided to use 3 maps, i hope it's pretty easy to understand. it seems to work, so that's good. it's for a class, so i'm don't really care if it's amazingly efficent. the prof did say we could hard code the adjacency lists, so that part is cool. i didn't really have to do a BFS. anyway, feel free to poke fun at it, won't hurt my feelings
Code:
#include <map>
#include <set>
#include <iostream>
#include <stack>
using namespace std;
int main () {
//creates the 3 maps used and others
map<int, set<int> > adlist;
map<int, int> indegree;
map<int, char> label;
int i,j;
set<int>::iterator itr;
stack<int> stack;
//adlist and label have to be hard coded
adlist[1].insert(2);
adlist[1].insert(5);
adlist[1].insert(8);
adlist[2].insert(3);
adlist[2].insert(6);
adlist[3].insert(4);
adlist[4].insert(11);
adlist[5].insert(2);
adlist[5].insert(6);
adlist[6].insert(4);
adlist[6].insert(7);
adlist[6].insert(10);
adlist[7].insert(4);
adlist[7].insert(11);
adlist[8].insert(5);
adlist[8].insert(6);
adlist[8].insert(9);
adlist[9].insert(6);
adlist[9].insert(10);
adlist[10].insert(7);
adlist[10].insert(11);
adlist[11];
label[1]='s';
label[2]='A';
label[3]='B';
label[4]='C';
label[5]='D';
label[6]='E';
label[7]='F';
label[8]='G';
label[9]='H';
label[10]='I';
label[11]='t';
//gets indegree of each vertex
for( i=1; i<=adlist.size(); i++ )
{
for( j=1; j<=adlist.size(); j++ )
{
itr=adlist[i].find(j);
if(itr!=adlist[i].end()) indegree[j]++;
}
}
//checks to see if graph/adlist is one vertex
if( adlist.size()==1 )
{
cout << "\ntopological map is: " << label[1] << endl;
}else //finds topological order using decrementing indegrees
{
cout << "\ntopologiclal order of graph is: ";
for( j=1; j<=indegree.size(); j++ )
{
for( i=1; i<=indegree.size(); i++ )
{ //puts i in stack if the indegree is 0
if( indegree[i]==0 ) stack.push(i);
}
//if the stack is empty, then there is no indegree of 0, so not a DAG and breaks out of loop
if( stack.empty() ) break;
//takes the vectors in adjacency list and decreases them in indegree
for( i=1; i<=adlist.size(); i++ )
{
itr=adlist[stack.top()].find(i);
if( itr!=adlist[stack.top()].end() ) indegree[i]--;
}
cout << label[stack.top()] << " ";
indegree[stack.top()]=-1;
stack.pop();
}
//prints that the graph/adlsit is not a DAG so cannot print topological order
if( stack.empty() ) cout << "\nnot a DAG, cannont find a starting vertex\n";
}
return 0;
}
-
August 3rd, 2007, 03:35 PM
#13
Re: Topological Sort Algrithm
The code is better... you should read information about graphs... despite the fact that it is better, the code is nasty anyway...
It is matter of learning... you should do a BFS as I told you... then all your ideas will be better.
If you like my post, please rate it, if you don't like my way of talking, please let me know
-
September 4th, 2010, 03:33 PM
#14
Re: Topological Sort Algrithm
Originally Posted by cky83
I need to write a program that takes a graph using adjacency lists and prints the topological order of the graph. How the hell do I do this? I know how to find the topological order, but I have to calculate in the program the indegree of each vertex. I have no idea how to implement this. If any of you guys can help explain it, that'd be much appretiated.
The book mentions using maps to implement the adjacency lists, but i'm pretty confused. If my list looks like this:
Code:
s -> A, D, G
A -> B, E
B -> C
C -> t
D -> A, E
E -> C, F, I
F -> C, t
G -> D, E, H
H -> E, I
I -> F, t
t -> nothing
how would I turn that into a map? and how would I find the indegree of each vertex? If you can't tell, I'm pretty confused. Please help.
Hi there
I know this is an old thread, but yesterday I had the same problem from my mates, I worked as a tutor for 2 juniors to earn extra money
I use 2d array and it was so easy to calculate the degree for each vertice, I didn't use the map as itwasm;t necessary
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|