Topological sort of my graph implementation

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
Topic archived. No new replies allowed.