#include #include #include using namespace std; class Edge; //------------------------------------------------------------- // // class Node { public: Node(string iname) { XXXXXXXXXXname = iname; }...

1 answer below »

Download the program graph_top_sort-001.cpp download and implement the init_in_counts() and top_sort() methods. Complete the top_sort() method by enclosing the for each node loop in a while loop to perform a complete topological sort. please conside this is 116 course so there is not much room for advance coding we were just introduced to binary trees and sorting. Thank you




#include #include #include using namespace std; class Edge; //------------------------------------------------------------- // // class Node { public: Node(string iname) { name = iname; } string name; int in_count = 0; bool visited = false; vector out_edge_list; }; //------------------------------------------------------------- // // class Edge { public: Edge(string iname, double iweight, Node *ifrom, Node *ito) { name = iname; weight = iweight; from = ifrom; to = ito; } string name; double weight; Node *from; Node *to; bool visited = false; }; //------------------------------------------------------------- // // class Graph { public: vector node_list; vector edge_list; //---------------------------------------------------------- // int find_node_index(string name) { //for(Node *n : node_list) for(int i = 0; i < node_list.size();="" ++i)="" if="" (node_list[i]-="">name == name) return i; return -1; } //---------------------------------------------------------- // Node* find_node(string name) { for(Node *n : node_list) if (n->name == name) return n; return 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) { Node *node_from, *node_to; if (!(node_from = find_node(node_name_from))) node_list.push_back(node_from = new Node(node_name_from)); if (!(node_to = find_node(node_name_to))) node_list.push_back(node_to = new Node(node_name_to)); Edge *new_edge = new Edge(name, weight, node_from, node_to); edge_list.push_back(new_edge); node_from->out_edge_list.push_back(new_edge); } void print_nodes() { cout < "\nnodes\n="======================\n";" for(node="" *n="" :="" node_list)="" cout="">< n-="">name < '="" '="">< n-="">in_count < endl;="" }="" void="" print_edges()="" {="" cout="">< "\nedges\n="======================\n";" for(edge="" *e="" :="" edge_list)="" cout="">< e-="">name < '="" '="">< e-="">from->name < '="" '="">< e-="">to->name< endl; } //---------------------------------------------------------- // initialize node in counts. // void init_in_counts() { /* for each edge e in the graph increment 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; } endl;="" }="" ----------------------------------------------------------="" initialize="" node="" in="" counts.="" void="" init_in_counts()="" {="" *="" for="" each="" edge="" e="" in="" the="" graph="" increment="" 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;="">
graphtopsort-001-kf1asiu0.cpp
Answered Same DayMar 29, 2021

Answer To: #include #include #include using namespace std; class Edge;...

Kshitij answered on Mar 30 2021
132 Votes
#include
#include
#include
using namespace std;
class Edge;
//-------------------------------------------------------------
//
//
class Node
{
public:
    Node(string iname)
    {
        name = iname;
    }
    string name;
    int in_count = 0;
    bool visited = false;
    vector out_edge_list;
};
//-------------------------------------------------------------
//
//
class Edge
{
public:
    Edge(string iname, double iweight, Node *ifrom, Node *ito)
    {
        name = iname;
        weight = iweight;
        from = ifrom;
        to = ito;
    }
    string name;
    double weight;
    Node *from;
    Node *to;
    bool visited = false;
};
//-------------------------------------------------------------
//
//
class Graph
{
public:
    vector node_list;
    vector edge_list;
    //----------------------------------------------------------
    //
    int find_node_index(string name)
    {
        //for(Node *n : node_list)
        for (int i = 0; i < node_list.size(); ++i)
            if (node_list[i]->name == name) return i;
        return -1;
    }
    //----------------------------------------------------------
    //
    Node* find_node(string name)
    {
        for (Node *n : node_list)
            if (n->name == name) return n;
        return...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?