· 6 years ago · Jun 24, 2019, 12:22 PM
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAX 5
5
6/*
7 * defines a struct named Graph
8 * the variable 'vertices' holds the number of current vertices
9*/
10typedef struct {
11 int pinax[MAX][MAX];
12 int vertices;
13} Graph;
14
15/*
16 * creates a new graph
17 * sets vertices = 0
18*/
19void create(Graph *g) {
20 int i, j;
21 for(i = 0; i < MAX; i++) {
22 for(j = 0; j < MAX; j++) {
23 g->pinax[i][j] = 0;
24 }
25 }
26 g->vertices = 0;
27}
28
29/*
30 * checks whether a graph is empty
31 * returns 1 if yes 0 otherwise
32*/
33int isEmpty(Graph g) {
34 if(g.vertices == 0)
35 return 1;
36 else
37 return 0;
38}
39
40/*
41 * checks whether a graph is full
42 * returns 1 if yes or else 0
43*/
44int isFull(Graph g) {
45 if(g.vertices == MAX)
46 return 1;
47 else
48 return 0;
49}
50
51/*
52 * checks whether a vertex is part of a graph
53 * returns 1 if successful or else 0
54*/
55int isVertex(Graph g, int p) {
56 if(p>0 && p <= g.vertices)
57 return 1;
58 else
59 return 0;
60}
61
62/*
63 * adds vertex at the end of the graph
64*/
65void addVertex(Graph *g) {
66 g->vertices++;
67 g->pinax[g->vertices - 1][g->vertices - 1] = 1;
68}
69
70/*
71 * deletes last vertex of the graph
72*/
73void delLastVertex(Graph *g) {
74 /* must clear row and column */
75 int i;
76 for(i=0; i<MAX; i++) {
77 g->pinax[g->vertices - 1][i] = 0;
78 g->pinax[i][g->vertices - 1] = 0;
79 }
80 g->vertices--;
81}
82
83/*
84 * checks whether second (y) vertex is incoming neighbor (x <- y)
85 * returns 1 if true, 0 if not and -1 if something is wrong
86*/
87int isNeighborIn(Graph g, int x, int y) {
88 if(g.pinax[y - 1][x - 1] == 1)
89 return 1;
90 else
91 return 0;
92}
93
94/*
95 * checks whether second (y) vertex is outgoing neighbor (x -> y)
96 * returns 1 if true, 0 if not and -1 if something is wrong
97*/
98int isNeighborOut(Graph g, int x, int y) {
99 if(g.pinax[x - 1][y - 1] == 1)
100 return 1;
101 else
102 return 0;
103}
104
105/*
106 * adds incoming arrow to x from y (x <- y)
107*/
108void addEdgeIn(Graph *g, int x, int y) {
109 g->pinax[y-1][x-1] = 1;
110}
111
112/*
113 * adds outgoing arrow from x to y (x -> y)
114*/
115void addEdgeOut(Graph *g, int x, int y) {
116 g->pinax[x-1][y-1] = 1;
117}
118
119/*
120 * deletes incoming arrow from y to x (x <- y)
121*/
122void delEdgeIn(Graph *g, int x, int y) {
123 g->pinax[y-1][x-1] = 0;
124}
125
126/*
127 * deletes outgoing arrow from x to y (x -> y)
128*/
129void delEdgeOut(Graph *g, int x, int y) {
130 g->pinax[x-1][y-1] = 0;
131}
132
133/*
134 * returns the number of nodes
135*/
136int getNumOfVertices(Graph g) {
137 return g.vertices;
138}
139
140/*
141 * prints graph as a table
142*/
143void printGraph(Graph g) {
144 int i, j;
145 for(i = 0; i < MAX; i++) {
146 for(j = 0; j < MAX; j++) {
147 printf("%d\t", g.pinax[i][j]);
148 }
149 printf("\n"); /* line break */
150 }
151}
152
153//----------------------------------------------------------------------------------
154void getCommonNeighbors(Graph g,int x, int y){
155 int i,j,sum=0;
156 i=y-1;//arxikopoiisi tou j ws y-1 gia na min eleksei ta panta para mono ti grami pou 8eloume
157 printf("\n%d %d\n",&x,&y);
158 for(j = 0; j < MAX; j++) {//gia ka8e epanalipsi alazei stiles stin idia grami
159 if (g.pinax[i][j]==1){//an brei 1 sti grami pou briskete ,alazontas styles, tote
160 if(g.pinax[x-1][j]==1)//elenxei an i antistixi grami stin idia stili exei kai auti asso
161 sum=sum+1;//an exei tote kanei a8risma gt auto simenei oti einai geitones
162 }
163 }
164
165 printf("Oi duo korifes exoun %d koinous geitones\n",sum);
166}
167
168
169//----------------------------------------------------------------------------------
170int main() {
171 Graph g;
172 create(&g);
173 int temp, temp1, temp2,x,y;
174
175 int i=100;
176 do {
177 puts("1. Create New Graph");
178 puts("2. Add Vertex at End"); /* adds a new node at the end of the graph */
179 puts("3. Delete Last Vertex"); /* deletes last Vertex of the graph */
180 puts("4. Check if Vertex Exists");
181 puts("5. Add Incoming Arrow"); /* adds an incoming Arrow */
182 puts("6. Add Outgoing Arrow"); /* adds an outgoing Arrow */
183 puts("7. Delete Incoming Arrow"); /* deletes Arrow */
184 puts("8. Delete Outgoing Arrow"); /* deletes Arrow */
185 puts("9. Check if Incoming Neighbor");
186 puts("10. Check if Outgoing Neighbor");
187 puts("11. Get Number of Vertices"); /* gets current number of Vertices */
188 puts("12. Print Table"); /* prints the table */
189 //----------------------------------------------------------------------------------
190 puts("13. Get common Neighbors");
191 //----------------------------------------------------------------------------------
192 puts("0. Exit\n");
193 scanf("%d", &i);
194
195 //system("clear"); /* UNIX */
196 //system("cls"); /* DOS */
197
198 switch(i) {
199 case 1: /* creates a graph */
200 create(&g);
201 puts("Graph created\n");
202 break;
203 case 2:
204 if(isFull(g)) {
205 puts("oops, Graph is full\n");
206 } else {
207 addVertex(&g);
208 puts("Vertex added\n");
209 }
210 break;
211 case 3:
212 if(isEmpty(g)) {
213 puts("oops, graph is empty\n");
214 } else {
215 delLastVertex(&g);
216 puts("Vertex deleted\n");
217 }
218 break;
219 case 4:
220 printf("Give vertex to check: ");
221 scanf("%d", &temp);
222 if(isVertex(g, temp))
223 printf("Vertex %d exists.\n", temp);
224 else
225 printf("Vertex %d does NOT exist.\n", temp);
226 break;
227 case 5:
228 printf("Give vertex for arrow head: ");
229 scanf("%d", &temp1);
230 if(!isVertex(g, temp1)) {
231 printf("Vertex %d exists.\n", temp1);
232 break;
233 }
234 printf("Give vertex for arrow tail: ");
235 scanf("%d", &temp2);
236 if(!isVertex(g, temp2)) {
237 printf("Vertex %d exists.\n", temp2);
238 break;
239 }
240 addEdgeIn(&g, temp1, temp2);
241 break;
242 case 6:
243 printf("Give vertex for arrow tail: ");
244 scanf("%d", &temp1);
245 if(!isVertex(g, temp1)) {
246 printf("Vertex %d exists.\n", temp1);
247 break;
248 }
249 printf("Give vertex for arrow head: ");
250 scanf("%d", &temp2);
251 if(!isVertex(g, temp2)) {
252 printf("Vertex %d exists.\n", temp2);
253 break;
254 }
255 addEdgeIn(&g, temp1, temp2);
256 break;
257 case 7:
258 printf("Give vertex for arrow head: ");
259 scanf("%d", &temp1);
260 if(!isVertex(g, temp1)) {
261 printf("Vertex %d exists.\n", temp1);
262 break;
263 }
264 printf("Give vertex for arrow tail: ");
265 scanf("%d", &temp2);
266 if(!isVertex(g, temp2)) {
267 printf("Vertex %d exists.\n", temp2);
268 break;
269 }
270 delEdgeIn(&g, temp1, temp2);
271 break;
272 case 8:
273 printf("Give vertex for arrow tail: ");
274 scanf("%d", &temp1);
275 if(!isVertex(g, temp1)) {
276 printf("Vertex %d exists.\n", temp1);
277 break;
278 }
279 printf("Give vertex for arrow head: ");
280 scanf("%d", &temp2);
281 if(!isVertex(g, temp2)) {
282 printf("Vertex %d exists.\n", temp2);
283 break;
284 }
285 delEdgeOut(&g, temp1, temp2);
286 break;
287 case 9:
288 printf("Give vertex for arrow head: ");
289 scanf("%d", &temp1);
290 if(!isVertex(g, temp1)) {
291 printf("Vertex %d exists.\n", temp1);
292 break;
293 }
294 printf("Give vertex for arrow tail: ");
295 scanf("%d", &temp2);
296 if(!isVertex(g, temp2)) {
297 printf("Vertex %d exists.\n", temp2);
298 break;
299 }
300 isNeighborIn(g, temp1, temp2);
301 break;
302 case 10:
303 printf("Give vertex for arrow tail: ");
304 scanf("%d", &temp1);
305 if(!isVertex(g, temp1)) {
306 printf("Vertex %d exists.\n", temp1);
307 break;
308 }
309 printf("Give vertex for arrow head: ");
310 scanf("%d", &temp2);
311 if(!isVertex(g, temp2)) {
312 printf("Vertex %d exists.\n", temp2);
313 break;
314 }
315 if(isNeighborOut(g, temp1, temp2)) {
316 printf("yes, %d is outgoing neighbor of %d\n\n", temp2, temp1);
317 } else {
318 printf("oops, %d is NOT outgoing neighbor of %d\n\n", temp2, temp1);
319 }
320 break;
321 case 11:
322 printf("Number of Vertices: %d\n", getNumOfVertices(g));
323 break;
324 case 12:
325 break;
326 //----------------------------------------------------------------------------------
327 case 13:
328 if(isEmpty(g)) {
329 puts("oops, graph is empty\n");//elenxos isempty
330 } else {
331 printf("Give vertex 1: ");//eisodos prwtou vertex
332 scanf("%d", &x);
333
334 printf("Give vertex 2: ");//eisodos prwtou vertex
335 scanf("%d", &y);
336 getCommonNeighbors(g,temp1,temp2);
337 }
338 break;
339 //----------------------------------------------------------------------------------
340 case 0:
341 i=0;
342 break;
343 default:
344 break;
345 }
346 puts("----------------------------------");
347 printGraph(g);
348 puts("----------------------------------\n");
349 } while(i>0 && i<=12);
350
351 getchar();
352 return 0;
353}