#ifndef GRAPH

#define GRAPH

/*

	图的邻接矩阵实现

*/

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

struct edge{

	int v;

	int w;

};

struct graph{

	int v;

	int e;

	int **adj;

};

edge EDGE(int v, int w)

{

	edge e;

	e.v = v; e.w = w;

	return e;

}

int** matrixInit(int r, int c, int val)

{

	int **t = (int**)malloc(r*sizeof(int*));

	for (int i = 0; i < r; ++i)

		t[i] = (int*)malloc(c*sizeof(int));

	for (int i = 0; i < r; ++i)

		for (int j = 0; j < c; ++j)

			t[i][j] = val;

	return t;

}

graph* graphInit(int v)

{

	graph* g = (graph*)malloc(sizeof(graph));

	g->v = v;

	g->e = 0;

	g->adj = matrixInit(v, v, 0);

	return g;

}

void graphInsert(graph* g, edge e)

{

	int v = e.v, w = e.w;

	if (g->adj[v][w] == 0) ++g->e;

	g->adj[v][w] = 1;

	g->adj[w][v] = 1;

}

void graphRemove(graph* g, edge e)

{

	int v = e.v, w = e.w;

	if (g->adj[v][w] == 1) --g->e;

	g->adj[v][w] = 0;

	g->adj[w][v] = 0;

}

int graphEdge(graph* g, edge a[])

{

	int e = 0;

	for (int v = 0; v < g->v; ++v)

		for (int w = 0; w < g->v; ++w)

			if (g->adj[v][w] == 1)

				a[e++] = EDGE(v, w);

	return e;

}

graph* graphCopy(graph* g)

{

	graph *cg = graphInit(g->v);

	cg->v = g->v;

	cg->e = g->e;

	for (int i = 0; i < g->v; ++i)

		for (int j = 0; j < g->v; ++j)

			(cg->adj)[i][j] = (g->adj)[i][j];

	return cg;

}

void graphDestroy(graph* &g)

{

	for (int i = 0; i < g->v; ++i)

		free((g->adj)[i]);

	free(g->adj);

	free(g);

}

void graphShow(graph* g)

{

	printf("%d vertices, %d edges\n", g->v, g->e);

	for (int i = 0; i < g->v; ++i){

		printf("%2d:", i);

		for (int j = 0; j < g->v; ++j)

			if ((g->adj)[i][j] == 1) printf("%2d", j);

		printf("\n");

	}

}

#endif

#include"graph.h"

int main()

{

	printf("\tgraph of matrix test:\n");

	srand(time(NULL));

	graph* g = graphInit(10);

	edge e[5];

	for (int i = 0; i < 5; ++i){

		e[i].v = rand() % 10;

		e[i].w = rand() % 10;

		graphInsert(g, e[i]);

	}

	graphShow(g);

	printf("\n");

	graph* cg = graphCopy(g);

	graphDestroy(g);

	graphRemove(cg, e[1]);

	graphShow(cg);

	printf("\n");

	for (int i = 0; i < 5; ++i)

		printf("%d: %d\n", e[i].v, e[i].w);

	printf("\n");

	edge ee[10];

	int cnt=graphEdge(cg, ee);

	for (int i = 0; i < cnt; ++i)

		printf("%d,%d\n", ee[i].v, ee[i].w);

	printf("\n");

}