graph.c

#include

#include

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.

*

print

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 :)"