///////////////////////////////////////////////////////////////////////////////// // FUNCTION NAME: removeNode// PARAMETERS: NodePtr& graph// const char& data// RETURN TYPE: void// PURPOSE: Removes the specified node. Alerts the // user if the node is not found./////////////////////////////////////////////////////////////////////////////////void cmpsc122::removeNode(NodePtr& graph, const char& data){ NodePtr parent = NULL; // initialize NodePtr the_node = NULL; // initialize traverseGraph(graph, parent, the_node, data); // get the_node & parent if (empty(graph)) { // tell the user cout << "The graph is empty!" << endl; } else if (the_node->data != data) { // tell the user cout << "The Node was not found." << endl; } else { while (the_node->edge_list) { // remove the edge! removeEdge(graph, data, the_node->edge_list->terminal->data); } // case 1: head if (graph == the_node) { graph = graph->next; // set head to next (if any) } // case 3: tail else if (the_node->next == NULL) { parent->next = NULL; // set the previous to null } // case 2: between else { parent->next = the_node->next; // set previous to next } delete the_node; // delete it }}///////////////////////////////////////////////////////////////////////////////// // FUNCTION NAME: addEdge// PARAMETERS: NodePtr& graph// const char& initial// const char& terminal// RETURN TYPE: void// PURPOSE: Adds the edge specified by the two nodes. Alerts the // user if the edge is a duplicate./////////////////////////////////////////////////////////////////////////////////void cmpsc122::addEdge(NodePtr& graph, const char& initial, const char& terminal){ if (empty(graph)) { // tell the user cout << "The graph is empty!" << endl; } else { NodePtr parent = NULL; // initialize NodePtr lasti = NULL; // initialize NodePtr lastt = NULL; // initialize traverseGraph(graph, parent, lasti, initial); // get the initial node traverseGraph(graph, parent, lastt, terminal); // get terminal node if ((lasti->data == initial) && (lastt->data == terminal)) { // check for duplicates EdgePtr dup = lasti->edge_list; // temp holder bool duplicate = false; // do we have a duplicate? while (dup) { if (dup->terminal == lastt) { duplicate = true; // yes we do! break; // break out of the loop } else { dup = dup->next; // if no, get the next edge } } if (!duplicate) { NodePtr a = lasti; // set a to lasti NodePtr b = lastt; // set b to lastt for (int x = 0; x < 2; x++) { EdgePtr e = new Edge; // make an new edge e->terminal = b; // set e's terminal to b e->next = a->edge_list; // sets e->next to stuff after a a->edge_list = e; // sticks e inbetween a and edge_list if (a == b) { break; // break the loop if equal } a = lastt; // flip- b = lasti; // flop the a and b } } else { cout << "This edge already exists!" << endl; // already exists! } } else { cout << "Invalid Node!" << endl; // invalid node! } }}///////////////////////////////////////////////////////////////////////////////// // FUNCTION NAME: removeEdge// PARAMETERS: NodePtr& graph// const char& initial// const char& terminal// RETURN TYPE: void// PURPOSE: Removes the edge specified by the two nodes. Alerts the // user if the edge is not found./////////////////////////////////////////////////////////////////////////////////void cmpsc122::removeEdge(NodePtr& graph, const char& initial, const char& terminal){ NodePtr parent = NULL; // initialize NodePtr to_remove = NULL; // initialize NodePtr to_remove2 = NULL; // initialize traverseGraph(graph, parent, to_remove, initial); // get to_remove parent = NULL; // reset parent traverseGraph(graph, parent, to_remove2, terminal); // get to_remove2 // check if the edge is there EdgePtr the_edge = to_remove->edge_list; // get the edge_list bool valid = false; // not valid till both nodes are present while (the_edge) { if (the_edge->terminal == to_remove2) { valid = true; // it is valid break; // break from the loop } else { the_edge = the_edge->next; // continue along } } if (valid) { EdgePtr a = to_remove->edge_list; // store the edge EdgePtr a_p = a; // store a parent NodePtr to_find = to_remove2; // store to_find NodePtr to_find2 = to_remove; // store to_find2 // loop first thru second for (int x = 0; x < 2; x++) { bool deleted = true; // not deleted yet while (a) { if (a->terminal == to_find) { // case 1: head if (to_find2->edge_list == a) { to_find2->edge_list = a->next; // set head to the next } // case 3: tail else if (a->next == NULL) { a_p->next = NULL; // set previous to null } // case 2: middle else { a_p->next = a->next; // set previous to next } delete a; // delete the edge deleted = false; // tell us we have deleted break; // break } else { a_p = a; // store parent a = a->next; // get child } } if (initial == terminal) { break; // break from the loop } a = to_remove2->edge_list; // shift to_find = to_remove; // to next a_p = a; // node to_find2 = to_remove2; // sift again } } else { cout << "The edge does not exist." << endl; // doesnt exist! }}///////////////////////////////////////////////////////////////////////////////// // FUNCTION NAME: traverseGraph// PARAMETERS: const NodePtr graph// NodePtr& parent // NodePtr& last // const char& data// RETURN TYPE: void// PURPOSE: Traverses the graph to find a certain node./////////////////////////////////////////////////////////////////////////////////void cmpsc122::traverseGraph(const NodePtr graph, NodePtr& parent, NodePtr& last, const char& data){ bool found = false; // indicates that the node has been found if ( !empty(graph) ) { // non-empty graph... parent = graph; last = graph; found = (last->data == data); while ((last->next) && (!found)) { // move the pointers... parent = last; last = last->next; found = (last->data == data); } } else { // empty graph... last = NULL; }}