Eliminazione di un vertice

/*
**	elimina_vertice.c
**
**	Dato un grafo orientato G=(V,E) lo si rappresenti mediante
**	una matrice di adiacenza. Dato un vertice v verificare che
**	v abbia in G un unico predecessore. In tal caso costruire
**	il grafo G' ottenuto da G eliminando v e collegando il
**	predecessore di v a tutti i successori di v.
**
**	Marco Liverani (liverani@mat.uniroma3.it) - Febbraio 1999
*/

#include <stdlib.h>
#include <stdio.h>

#define MAX 50

struct nodo {
	int info;
	struct nodo *next;
};


/*
**	leggi_grafo
**
**	per ogni vertice v di G legge i vertici u adiacenti
**	e pone m[v][u] = 1. Restituisce il numero di vertici di G.
*/

int leggi_grafo(int *m) {
	int i, j, n;

	printf("Numero di vertici: ");
	scanf("%d", &n);

	for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			*(m+i*MAX+j) = 0;
		}
	}

	for (i=0; i<n; i++) {
		printf("Vertici adiacenti a %d (-1 per terminare): ", i);
		scanf("%d", &j);
		while (j != -1) {
			*(m+i*MAX+j) = 1;
			scanf("%d", &j);
		}
	}

	return(n);
}

/*
**	stampa_grafo
**
**	stampa le liste di adiacenza di G.
*/

void stampa_grafo(struct nodo **l, int n) {
	int i;
	struct nodo *p;

	for (i=0; i<n; i++) {
		p = *(l+i);
		printf("%d: ", i);
		while (p != NULL) {
			printf("%d -> ", p->info);
			p = p->next;
		}
		printf("NULL\n");
	}
	return;
}


/*
**	verifica
**
**	per ogni vertice i di G diverso da v verifica se
**	esiste uno spigolo (i,v) entrante in v e conta il
**	numero di predecessori di v. Se v ha un unico
**	predecessore restituisce il numero di tale vertice,
**	altrimenti restituisce -1.
*/

int verifica(int *m, int n, int v) {
	int i, predecessore, npred;

	npred = 0;
	predecessore = -1;

	for (i=0; i<n; i++) {
		if (i != v && *(m+i*MAX+v) == 1) {
			predecessore = i;
			npred++;
		}
	}

	if (npred == 1)
		return(predecessore);
	else
		return(-1);
}


/*
**	elimina_vertice
**
**	elimina dal grafo il vertice v, collegando il predecessore
**	 di v a tutti i vertici di G successori di v.
*/

void elimina_vertice(int predecessore, int v, int *m, int n) {
	int i;

	for (i=0; i<n; i++) {
		if (*(m + v*MAX + i) == 1) {
			*(m + predecessore*MAX + i) = 1;
			*(m + v*MAX + i) = 0;
		}
	}
	*(m + predecessore*MAX + v) = 0;

	return;
}


/*
**	nuovo_grafo;
**
**	costruisce le liste di adiacenza del grafo G, privato
**	del vertice v.
*/

void nuovo_grafo(int *m, struct nodo **l, int n) {
	int i, j;
	struct nodo *p;

	for (i=0; i<n; i++) {
		*(l+i) = NULL;
		for (j=0; j<n; j++) {
			if (*(m + i*MAX + j) == 1) {
				p = malloc(sizeof(struct nodo));
				p->info = j;
				p->next = *(l+i);
				*(l+i) = p;
			}
		}
	}
	return;
}


/*
**	main
**
**	funzione principale che richiama tutte le altre
*/

int main(void) {
	int m[MAX][MAX], n, v, pred;
	struct nodo *lista[MAX];

	n = leggi_grafo(&m[0][0]);

	printf("Inserisci il vertice v: ");
	scanf("%d", &v);

	pred = verifica(&m[0][0], n, v);

	if (pred >= 0) {
		elimina_vertice(pred, v, &m[0][0], n);
		nuovo_grafo(&m[0][0], &lista[0], n);
		stampa_grafo(&lista[0], n);
	} else {
		printf("Il predecessore di %d non e` unico.\n");
	}

	return(1);
}