Topological sort of my graph implementation
May 2, 2015 at 8:44am May 2, 2015 at 8:44am UTC
I have been working on a graph implementation for the last few days. All of this is really new to me. I am implementing a digraph of courses from an input file. From the file, I can determine which courses are prereqs for other courses. I then create a digraph with courses as nodes, and edges connecting courses that are prereqs (I will later add weights to the edges). My implementation.
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
class vertex{
public :
typedef std::pair<int , vertex*> ve;
std::vector<ve> adjacency;
std::string course;
vertex(std::string c){
course = c;
}
};
class Digraph{
public :
void addVertex(std::string&);
void addEdge(std::string& from, std::string& to, int cost);
typedef std::map<std::string, vertex *> vmap;
vmap work;
int getNumVertices();
int getNumEdges();
void getTopoSort();
};
void Digraph::addVertex(std::string& course){
vmap::iterator iter = work.begin();
iter = work.find(course);
if (iter == work.end()){
vertex *v;
v = new vertex(course);
work[course] = v;
return ;
}
}
void Digraph::addEdge(std::string& from, std::string& to, int cost){
vertex *f = (work.find(from)->second);
vertex *t = (work.find(to)->second);
std::pair<int , vertex *> edge = std::make_pair(cost, t);
f->adjacency.push_back(edge);
}
I am completely lost on how to implement a topological sort on this graph. Any guidance is appreciated.
Last edited on May 2, 2015 at 9:12am May 2, 2015 at 9:12am UTC
Topic archived. No new replies allowed.