graph.c #include <stdio.h> #include <stdlib.h> typedef enum {FALSE, TRUE} bool;
ID: 3714492 • Letter: G
Question
graph.c
#include <stdio.h>
#include <stdlib.h>
typedef enum {FALSE, TRUE} bool;
#define MAXV 100
typedef str
uct edgenode {
int y;
int weight;
struct edgenode *next;
} edgenodeT;
typedef struct {
edgenodeT *edges[MAXV+1];
int degree[MAXV+1];
int nvertices;
int nedges;
// number of directed edges....
bool directed;
} graphT;
void
initiali
ze_graph(graphT *g, bool directed)
;
void
read_graph(graphT *g
, char *filename
)
;
void
insert_edge(graphT *g, in
t x, int y, int w
)
;
void
print_graph(graphT *g
, char *name
)
;
void
free_graph(graphT *g)
;
graphT *copy_graph(
graphT *g
);
// put prototypes for othe
r functions here....
int
main(
int argc, char *argv[]
)
{
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) {
fp
rintf(stderr, "Cannot allocate memory for the graph");
exit(
-
1);
}
initialize_graph(
myg1, FALSE);
read_graph(
myg1
, argv[1]
);
print_graph(
myg1
, "myg1"
);
//
first implement copy_graph
function and call it
here
myg2 = copy_graph(myg1);
pr
int_graph(myg2
, "myg2"
);
//
NOW
in a loop get commands and
// call related functions to perform them...
free_graph(myg1);
}
void
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;
}
void
read_graph(graphT *g
, char *filename
)
{
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);
}
f
scanf(
fp,
”%d %d %d”, &n, &m, &dir);
g
-
>nvertices = n;
g
-
>nedges =
0; // insert function will increase it
;
g
-
>directed = dir;
for (i=1; i<=m; i++) {
f
scanf(
fp,
”%d
%d %d”, &x, &y, &w);
insert
_edge(g, x, y, w);
if(dir==FALSE)
insert
_edge(g, y, x, w);
}
fclose(fp);
}
void insert_
edge(graphT *g, in
t x, int y, int w
)
{
edgenodeT *pe;
pe = malloc(sizeof(edgenodeT));
// check if NULL
pe
-
>weight = w;
pe
-
>y = y;
// YOU MUST MODIFY THIS FUNCTION SO IT WILL KEEP LINK LIST SORTED
// W.R.T. NEIGHBOR IDs.
pe
-
>next = g
-
>edges[x];
g
-
>edges[x] = pe;
g
-
>degree[x]++;
g
-
>nedges
++;
}
void
print_graph(graphT *g
, char *
name
)
{
edgenodeT *pe;
int i;
if(!g) return
;
printf("Graph Name: %s
n"
, name
);
for(i=1; i<=g
-
>nvertices; i++) {
printf("Node %d: ", i);
pe = g
-
>edges[i];
while(pe){
// printf(" %d", pe
-
>y);
pr
intf(" %d(w=%d),", pe
-
>y, pe
-
>weight);
pe = pe
-
>next;
}
printf("
n");
}
}
void
free_graph(graphT *g)
{
edgenodeT *pe, *olde;
int i;
for(i=1; i<=g
-
>nvertices; i++) {
pe = g
-
>edges[i];
while(pe){
olde
= pe;
pe = pe
-
>next;
free(olde);
}
}
free(g);
}
graphT *copy_graph(
graphT *g
)
{
graphT *newg;
// I simply return the same graph as a copy
// but you really need to dynamically create
// another copy of the giv
en graph
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 tha
t edge is already in the graph, don't insert
anything...
Remember you need to insert edges in a sorted
manner
* 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 t
he 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)an
d count how many times node i appears in the all
adjacency lists, and print that count as the in
-
degree for node
i.
*
c
omplement
myg2
First create the complement graph of myg2 as cg, and call
printgraph(cg) then free complement graph cg.
Don't wor
ry about
weight
in the new graph
cg.
for example,
you can set al weights
to 1 in cg
* eliminatelink
s
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
p
rint edges that are both in
my
g1 and in
my
g2
* dfs_print
_paths
myg1
x
print in which order nodes are visited
then for each node print the path from x to that node
* bfs_print
_paths
myg2
x
pri
nt in which order nodes are visited
then for each node print the path from x to that node
* isconnected
myg1
* numofconncomp
myg2
last two comma
nds
isconnected numofconncomp will be performed
if the graph is UNdirected ...
if the graph is direct
ed don't do anything or just print
"Purchase the next version of this program :)"
Explanation / Answer
#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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.