And this is the Graph implementation:
#include "linked_list_bag.c"
#include "out.c"
#ifndef GRAPH
#define GRAPH
typedef struct GraphStruct {
int v;
int e;
LinkedListBag *adj;
}* Graph;
Graph GraphCreateV(int v) {
Graph g = (Graph)malloc(sizeof(*g));
g->v = v;
g->e = 0;
g->adj = (LinkedListBag*)malloc(v * sizeof(LinkedListBag));
for (int i = 0; i < v; i++) { *(g->adj + i) = LinkedListBagCreate(); }
return g;
}
void GraphAddEdge(Graph g, int v, int w) {
LinkedListBagAdd(*(g->adj + v), w);
LinkedListBagAdd(*(g->adj + w), v);
g->e++;
}
int GraphNumberOfEdges(Graph g) { return g->e; }
int GraphNumberOfVertices(Graph g) { return g->v; }
Graph GraphCreate(int v, int e, int a[]) {
Graph g = GraphCreateV(v);
for (int i = 0; i < e; i++) { GraphAddEdge(g, *(a + 2 * i), *(a + 2 * i + 1)); }
return g;
}
/**
* examle:
* 3 //number of vetices
* 3 //number of edges
* 1 0
* 1 2
* 2 1
*/
Graph GraphCreateFromInput() {
int v, e, *a;
scanf("%i%i", &v, &e);
a = (int*)malloc(2 * e * sizeof(*a));
for (int i = 0; i < e; i++) { scanf("%i%i", a + 2 * i, a + 2 * i + 1); }
Graph g = GraphCreate(v, e, a);
free(a);
return g;
}
int* GraphAdjcency(Graph g, int v, int *n) { return LinkedListBagItems(g->adj[v], n); }
void GraphIterateAdjency(Graph g, int v, void(*func)(int, void*), void *context) {
int n = 0;
int *adj = GraphAdjcency(g, v, &n);
for (int i = 0; i < n; i++) { func(adj[i], context); }
if (adj != NULL) { free(adj); }
}
void GraphRelease(Graph g) {
if (g != NULL) {
for (int i = 0; i < g->v; i++) { LinkedListBagRelease(g->adj[i]); }
free(g);
}
}
void GraphPrint(Graph g) {
if (g != NULL) {
printf("%i vertices, %i edges\n", g->v, g->e);
for (int i = 0; i < g->v; i++) {
printf("%i: ", i);
int n = 0;
int *adj = LinkedListBagItems(g->adj[i], &n);
if (adj != NULL) {
printa(adj, n);
free(adj);
}
}
printf("\n");
}
}
#endif
网友评论