#include
#include
#include
using namespace std;
class Edge;
-------------------------------------------------------------
class Node
{
public:
Node(string iname)
{
XXXXXXXXXXname = iname;
}
string name;
int in_count = 0;
bool visited = false;
vecto
Edge *> out_edge_list;
};
-------------------------------------------------------------
class Edge
{
public:
Edge(string iname, double iweight, Node *ifrom, Node *ito)
{
XXXXXXXXXXname = iname;
XXXXXXXXXXweight = iweight;
XXXXXXXXXXfrom = ifrom;
XXXXXXXXXXto = ito;
}
string name;
double weight;
Node *from;
Node *to;
bool visited = false;
};
-------------------------------------------------------------
class Graph
{
public:
vecto
Node *> node_list;
vecto
Edge *> edge_list;
----------------------------------------------------------
int find_node_index(string name)
{
for(Node *n : node_list)
XXXXXXXXXXfor(int i = 0; i < node_list.size(); ++i)
XXXXXXXXXXif (node_list[i]->name == name) return i;
XXXXXXXXXXreturn -1;
}
----------------------------------------------------------
Node* find_node(string name)
{
XXXXXXXXXXfor(Node *n : node_list)
XXXXXXXXXXif (n->name == name) return n;
XXXXXXXXXXreturn 0;
}
----------------------------------------------------------
Add a new edge ( and possibly new nodes) to the graph.
void add_edge(string name, double weight, string node_name_from, string node_name_to)
{
XXXXXXXXXXNode *node_from, *node_to;
XXXXXXXXXXif (!(node_from = find_node(node_name_from)))
XXXXXXXXXXnode_list.push_back(node_from = new Node(node_name_from));
XXXXXXXXXXif (!(node_to = find_node(node_name_to)))
XXXXXXXXXXnode_list.push_back(node_to = new Node(node_name_to));
XXXXXXXXXXEdge *new_edge = new Edge(name, weight, node_from, node_to);
XXXXXXXXXXedge_list.push_back(new_edge);
XXXXXXXXXXnode_from->out_edge_list.push_back(new_edge);
}
void print_nodes()
{
XXXXXXXXXXcout
"\nNodes\n=======================\n";
XXXXXXXXXXfor(Node *n : node_list)
XXXXXXXXXXcout
n->name
' '
n->in_count
endl;
}
void print_edges()
{
XXXXXXXXXXcout
"\nEdges\n=======================\n";
XXXXXXXXXXfor(Edge *e : edge_list)
XXXXXXXXXXcout
e->name
' '
e->from->name
' '
e->to->name
endl;
}
----------------------------------------------------------
Initialize Node in counts.
void init_in_counts()
{ /*
XXXXXXXXXXfor each edge e in the graph
XXXXXXXXXXincrement the in count of the to node of e
*
}
1st iteration of top_sort(), just find the next node
bool top_sort()
{ /*
for each node n
if n is unvisited and has incount 0
found the next node
mark n as visited
for each edge e going out from n
decrement the in count for the to nodde of e
print name of node n
return true;
*/ return false;
}
};
-------------------------------------------------------------
int main()
{
Graph g;
g.add_edge("e1", 1.0, "1", "4");
g.add_edge("e2", 2.0, "1", "5");
g.add_edge("e3", 3.0, "2", "3");
g.add_edge("e4", 4.0, "2", "4");
g.add_edge("e5", 5.0, "3", "4");
g.add_edge("e6", 6.0, "3", "6");
g.add_edge("e7", 7.0, "3", "8");
g.add_edge("e1", 8.0, "4", "5");
g.add_edge("e3", 9.0, "5", "7");
g.add_edge("e3", 10.0, "5", "9");
g.add_edge("e3", 11.0, "6", "7");
g.add_edge("e3", 12.0, "7", "9");
g.add_edge("e3", 13.0, "8", "9");
g.init_in_counts();
g.print_nodes();
g.print_edges();
g.top_sort();
g.print_nodes();
g.top_sort();
g.print_nodes();
g.top_sort();
g.print_nodes();
return 0;
}