Homework Soursefirst modify insertedge function so that it can keep the lin
first modify insert_edge() function so that it can keep the link list sorted w.r.t. neighbor IDs. Second implement graph_copy() to create a copy of the given graph. User will call the original graph as myg1 and the copy as myg2 ,for which we use the same pointer names in the program. Now extend the main function so that it can asks user to enter various commands in a loop and performs these commands on the related graphs. Accordingly you also need to implement those functions and call them.
Finally when ending the main function, make sure you free the graphs
Specifically, your program will ask user to enter a command and related parameters (if any) in a loop, and then perform the given commands.
Here is the list of commands that your program must implement:
[Your command names should be as written below so the TA can
copy paste his/her test cases...]
* insert [myg1 | myg2] x y w
* delete [myg1 | myg2] x y
* printgraph [myg1 | myg2]
* printdegree [myg1 | myg2] // if directed ,print both in - and out-degree
* printcomplement [myg1 | myg2]
* eliminatelinks [myg1 | myg2] minW maxW
* differentlinks [myg1 | myg2] [myg1 | myg2]
* commonlinks [myg1 | myg2] [myg1 | myg2]
* dfs_print [myg1 | myg2] x
* bfs_print [myg1 | myg2] x
* isconnected [myg1 | myg2]
* numofconncomp [myg1 | myg2]
* quit
//graph.c program
#include <stdio.h>
#include <stdlib.h>
typedef enum {FALSE, TRUE} bool;
#define MAXV 100
typedef struct edgenode{
int y;
int weight;
struct edgenode *next;
} edgenodeT;
typedef struct{
edgenodeT *edges[MAXV+1];
int degree[MAXV+1];
int nvertices;
int nedges;
bool directed;
} graphT;
void initialize_graph(graphT *g, bool directed);
void read_graph(graphT *g, char *filename);
void insert_edge(graphT *g, int x, int y, int w);
void print_graph(graphT *g, char *name);
void free_graph(graphT *g);
graphT *copy_graph(graphT *g);
main()
// Assume that MAXV is 6
{
graphT *myg1 = NULL, *myg2 = NULL;
if(argc < 2){
fprintf(stderr, \"Usage: %s graph_filename\", argv[0]);
exit(-1);
}
myg1 = (graphT *) malloc(sizeof(graphT));
if (myg1==NULL) {
fprintf(stderr, \"Cannot allocate memory for the graph\");
exit(-1);
}
initialize_graph(myg1, FALSE);
read_graph(myg1, argv[1]);
print_graph(myg1, \"myg1\");
myg2 = copy_graph(myg1);
print_graph(myg2, \"myg2\");
// NOW in a loop get commands and
// call related functions to perform them...
free_graph(myg1);
}
initialize_graph (graphT*g, bool directed)
{
int i;
g->nvertices= 0;
g->nedges= 0;
g->directed = directed;
for (i=1; i<=MAXV; i++)
g->edges[i] = NULL;
for(i=1; i<=MAXV; i++)
g->degree[i] = 0;
}
read_graph(graphT *g)
{
int i;
int n, m, dir;
int x, y, w;
FILE *fp
if((fp=fopen(filename,\"r\"))==NULL){
fprintf(stderr, \"Cannot open the graph file\");
exit(-1);
}
scanf(”%d %d %d”, &n, &m, &dir);
g->nvertices= n;
g->nedges= 0;
g->directed= dir;
for (i=1; i<=m; i++) {
scanf(”%d %d %d”, &x, &y, &w);
insert _edge(g, x, y, w);
if(dir==FALSE)
insert _edge(g, y, x, w);
}
fclose(fp);
}
insert_edge(graphT *g, int x, int y, int w)
{
edgenodeT *pe;
pe= malloc(sizeof(edgenodeT)); // check if NULL
pe->weight = w;
pe->y = y;
pe->next = g->edges[x];
g->edges[x] = pe;
g->degree[x]++;
g->nedges++;
}
print_graph (graphT *g, char *name)
{
edgenodeT *pe;
int i;
if(!g) return;
printf(\"Graph Name: %s\ \", name);
for(i=1; i<=g->nvertices; i++){
printf(\"Node %d: \", i);
pe = g->edges[i];
while(ge){
printf(\" %d %d,\", pe->y, pe->weight);
pe = pe->next;
}
printf(\"\ \");
}
}
free_graph(graphT *g)
{
edgenodeT *pe, *olde;
int i;
for(i=1; i<=g->nvertices;i++){
pe = g->edges[i];
while(pe){
olde = ps;
pe = pe->next;
free(olde);
}
}
free(g);
}
graphT *copy_graph(graphT *g)
{
graphT *newg;
newg = g;
return newg;
}
// your other functions
here are some clarifications
* insert myg1 3 4 20
* delete myg1 2 4
* printgraph myg1
* printdegree myg1
* print complement myg2
* eliminatelinks myg1 minW maxW
check each edge pe
if (pe->w < minW || pe->w > maxW) delete that edge
* differentlinks myg1 myg2
print edges that are in my g1 but not in my g2
* commonlinks myg1 myg2
print edges that are both in my g1 and in myg2
* dfs_print myg1 x
print in which order nodes are visited then for each node print the path from x to that node
* bfs_print myg2 x
print in which order nodes are visited then for each node print the path from x to that node
* isconnected myg1
* numofconncomp myg2
Solution
#include<iostream>
#include<map>
using namespace std;
/* A binary tree node has data, pointer to left child, a pointer to right
child and a pointer to random node*/
struct Node
{
int key;
struct Node* left, *right, *random;
};
/* Helper function that allocates a new Node with the
given data and NULL left, right and random pointers. */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->random = temp->right = temp->left = NULL;
return (temp);
}
/* Given a binary tree, print its Nodes in inorder*/
void printInorder(Node* node)
{
if (node == NULL)
return;
/* First recur on left sutree */
printInorder(node->left);
/* then print data of Node and its random */
cout << \"[\" << node->key << \" \";
if (node->random == NULL)
cout << \"NULL], \";
else
cout << node->random->key << \"], \";
/* now recur on right subtree */
printInorder(node->right);
}
// This function creates clone by copying key and left and right pointers
// This function also stores mapping from given tree node to clone.
Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap)
{
if (treeNode == NULL)
return NULL;
Node* cloneNode = newNode(treeNode->key);
(*mymap)[treeNode] = cloneNode;
cloneNode->left = copyLeftRightNode(treeNode->left, mymap);
cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
return cloneNode;
}
// This function copies random node by using the hashmap built by
// copyLeftRightNode()
void copyRandom(Node* treeNode, Node* cloneNode, map<Node *, Node *> *mymap)
{
if (cloneNode == NULL)
return;
cloneNode->random = (*mymap)[treeNode->random];
copyRandom(treeNode->left, cloneNode->left, mymap);
copyRandom(treeNode->right, cloneNode->right, mymap);
}
// This function makes the clone of given tree. It mainly uses
// copyLeftRightNode() and copyRandom()
Node* cloneTree(Node* tree)
{
if (tree == NULL)
return NULL;
map<Node *, Node *> *mymap = new map<Node *, Node *>;
Node* newTree = copyLeftRightNode(tree, mymap);
copyRandom(tree, newTree, mymap);
return newTree;
}
/* Driver program to test above functions*/
int main()
{
//Test No 1
Node *tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->left->left = newNode(4);
tree->left->right = newNode(5);
tree->random = tree->left->right;
tree->left->left->random = tree;
tree->left->right->random = tree->right;
// Test No 2
// tree = NULL;
// Test No 3
// tree = newNode(1);
// Test No 4
/* tree = newNode(1);
tree->left = newNode(2);
tree->right = newNode(3);
tree->random = tree->right;
tree->left->random = tree;
*/
cout << \"Inorder traversal of original binary tree is: \ \";
printInorder(tree);
Node *clone = cloneTree(tree);
cout << \"\ \ Inorder traversal of cloned binary tree is: \ \";
printInorder(clone);
return 0;
}
