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
insert a new edge 3-4 into myg1 graph with weight of 20. If this is an undirected graph also insert edge 4-3 with weight 20. If that edge is already in the graph, don\'t insert anything...
* delete myg1 2 4
delete edge 2-4 from myg1. If this is an undirected graph also delete edge 4-2. If that edge is not in the graph, don\'t delete anything...
* printgraph myg1
print graph using the code given...\'
* printdegree myg1
if myg1 is undirected, then simply count the number of neighbors in the adjacency list for each node and print that number as the degree of each node..
if the graph is directed, then again you can simply count the number of neighbors in the adjacency list for each node and print that number as the out-degree of each node... BUT you also need to find in-degree. For this, you can check every node (say node i)and count how many times node i appears in the all adjacency lists, and print that count as the in degree or node i.
* print complement myg2
First create the complement graph of myg2 as cg, and call printgraph(cg) then free complement graph cg.
* 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
last two comments isconnected numofconncomp will be performed
Solution
#include <iostream>
using namespace std;
const short int TRUE = 1, FALSE = 0;
template <class ListType>//type of data each evrtex stores
class Graph
{
private:
int max;
struct vertex;//forward declaration for vertex structure
struct node //linked list for mapping edges in the graph
{
vertex *vertexPtr;//points to the vertex to which the edge is adjecent
node *next;//points to the next edge belong to the same vertex
};
struct vertex //struct to store details of a vertex
{
ListType data; //template type of data
int visited; //to check if the vertex is visited or not
node *list; //pointer to all the edges (linked lists)
};
vertex *vertexArray;//array for all the vertices
node *tempList;//to temporarily store the lists
vertex **vertexQueue;//queue of the vertices
ListType SearchElement;
int queueHead, queueTail;//head and the tail of the queue
//allocates initializes and returns a new node from the memory
node* getNode(vertex *v)
{
node *newNode = new node;
newNode->vertexPtr = v;
newNode->next = NULL;
return newNode;
}
//adds a node at the end of the list
//accepts refference to pointer and pointer to vertex
void addAtEnd(node *&n, vertex *v)
{
node *temp;//newly allocated node is stored here
if(n == NULL)//if no nodes exist allocate a node directly and return
{
n = getNode(v);
return;
}
node *endNode = n;//copy of the first node to traverse to last node
temp = getNode(v);//allocating a lode to attach at the end of the list
while(endNode->next != NULL)
//traverse till the last node (next of the node is null)
{
endNode = endNode->next;
}
endNode->next = temp;//attach the new node to the last node
}
//add node to the tail of the queue
void enqueue(vertex *v)
{
if(queueTail < max)
vertexQueue[queueTail++] = v;
}
//remove a node from the head of the queue
vertex* dequeue()
{
if(queueHead < max)
return vertexQueue[queueHead++];
else
return NULL;
}
//delete all the nodes after the specified node
void deleteAllAfter(node *n)
{
node *temp;//store the last node
while(n != NULL)
//till n is not the last node (null) delete node and move to next node
{
temp = n -> next;
delete n;
n = temp;
}
}
public:
Graph(){}
Graph(ListType *value, int size)
//constructor that allocates and initializes the vector array
{
max = size;
vertexArray = new vertex [max];
for (int i = 0; i < max ; ++i)
{
vertexArray[i].data = value[i];
vertexArray[i].list = NULL;
vertexArray[i].visited = 0;
}
}
void setEdge(ListType vert1, ListType vert2)
//set edges between vertuces vert1 and vert2 by iterating
{
for (int i = 0; i < max; ++i)//loop through all the vertices
{
if(vertexArray[i].data == vert1)//when vert1 is found
{
for (int j = 0; j < max; ++j)//loop through all the vertices
{
if(vertexArray[j].data == vert2)//when vert2 is found
{
//connect vert1 to vert2 and vice versa
addAtEnd(vertexArray[i].list,&vertexArray[j]);
addAtEnd(vertexArray[j].list,&vertexArray[i]);
break;
}
}
break;
}
}
}
void dfs(vertex *v)
{
v->visited = TRUE;//since we visited this node
if (v->data == SearchElement)//output the data to know we have visited
cout<<\"(\"<<v->data<<\") \";//element found
else
cout<<v->data<<\" \";//element not found
while(1)
{
if(v->list == NULL)//if we reach the leaf node
break;
//if the node connected to this node is not visited,
if(v->list->vertexPtr->visited == FALSE)
dfs(v->list->vertexPtr);//pass that node to this function
v->list = v->list->next;//point to the next node
}
return;
}
void clearVisited()
{
for (int i = 0; i < max; ++i)//iterate and set all nodes to not visited
{
vertexArray[i].visited = FALSE;
}
}
void bfs(vertex *v)
{
enqueue(v);
v->visited = TRUE;
for (int i = 0; i < max; ++i)
{
if(queueHead >= queueTail)//if head crosses tail during incrementing
{
cout<<endl<<\"FATAL ERROR IN TRAVERSING\";
break;
}
while(v->list->next != NULL)//while there are no more child nodes
{
if(v->list->next->vertexPtr->visited == TRUE)//if child node is visited
{
v = vertexQueue[i];//set element form the queue where the head is pointing
break;
}
v->list = v->list->next;//set the current node to its sibling node
enqueue(v);//enqueue the node to the list
v->visited = TRUE;//set that node as visited
}
if (vertexArray[i].data == SearchElement)//output the data to know we have visited
cout<<\"(\"<<vertexArray[i].data<<\") \";//if found
else
cout<<vertexArray[i].data<<\" \";//if not found
}
}
void search(char type = \'d\')
{
if(type == \'d\')
dfs(vertexArray);
else if(type == \'b\')
{
vertexQueue = new vertex*[max];
queueHead = 0, queueTail = 0;
bfs(vertexArray);
}
}
void setSearchElement(ListType value)
{
SearchElement = value;
}
void display()
//display all the vertices and their connections
{
node *n;
for (int i = 0; i < max; ++i)
{
cout<<\"Vertex: \"<<vertexArray[i].data<<\" \";
cout<<\"Connections: \";
n = vertexArray[i].list;
while(n != NULL)
{
cout<<n->vertexPtr->data;
n = n->next;
cout<<\" \";
}
cout<<endl;
}
}
~Graph(){}
};
int main()
{
int size;
cout<<\"Size: \";
cin>>size;
char *value;
value = new char [size];
cout<<\"Enter vertices: \";
for (int i = 0; i < size; ++i)
{
cin>>value[i];
}
Graph <char>g1(value,size);
Graph <char>g2(value,size);
int choice = 1;
char vertA, vertB, searchElement;
while(1)
{
cout<<\"Do you want to set an edge?(1/0): \";
cin>>choice;
if(choice)
{
cin>>vertA>>vertB;
g1.setEdge(vertA,vertB);
g2.setEdge(vertA,vertB);
}
else
break;
}
cout<<endl;
cout<<\"Search element: \";
cin>>searchElement;
cout<<endl;
g1.display();
g1.setSearchElement(searchElement);
g2.setSearchElement(searchElement);
cout<<\"BFS: \";
g2.search(\'b\');
cout<<endl;
cout<<\"DFS: \";
g1.search(\'d\');
cout<<endl;
}
