/* programma per costruire una partizione del grafo in insiemi stabili (almeno uno massimale) */
#include <stdio.h>
#include <stdlib.h>
/********************/
/* definizione tipi */
/********************/
/* implementazione di insiemi disgiunti con liste */
typedef struct lnode {
int id;
struct lnode* next;
struct lnode* rap;
} lnode;
/* implementazione di insiemi disgiunti con foreste */
typedef struct fnode {
int id;
struct fnode* parent;
} fnode;
/*********************/
/* variabili globali */
/*********************/
/* matrice di adiacenza per la rappresentazione del grafo */
short **AdjMatrix;
/* array che implementa la collezione di insiemi disgiunti (liste) */
lnode **ListColl;
/* array che implementa la collezione di insiemi disgiunti (foreste) */
fnode **ForestColl;
/* array che memorizza i puntatori alle strutture lnode */
lnode **LNodes;
/* array che memorizza i puntatori alle strutture fnode */
fnode **FNodes;
/* numero di nodi del grafo */
int NumNodes;
/* numero di archi del grafo */
int NumEdges;
/* rappresentazione del grafo [1=liste, 2=foreste] */
char GraphRapType;
/*********************/
/* funzioni */
/*********************/
/* legge il grafo in input come matrice di adiacenza */
void ReadGraph() {
/* identifichiamo i nodi con interi da 0 a NumNodes-1 */
/* legge il numero di nodi del grafo */
printf("\n numero di nodi: ");
scanf("%d, &NumNodes");
/* alloca memoria e inizializza la matrice di adiacenza */
AdjMatrix = (short**)malloc(NumNodes * sizeof(short*));
for (int i=0; i<NumNodes; i++)
AdjMatrix[i] = (short*)malloc(NumNodes * sizeof(short));
for (i=0; i<NumNodes; i++)
for (int j=0; j<NumNodes; j++) AdjMatrix[i][j] = 0;
/* legge il tipo di rappresentazione per la collezione di insiemi disgiunti */
printf("\n rappresentazione degli insiemi disgiunti [1=liste, 2=foreste]: ");
do
scanf("%d", &GraphRapType);
while ((GraphRapType != 1) && (GraphRapType != 2));
/* alloca memoria e inizializza la collezione */
if (GraphRapType == 1) {
ListColl = (lnode**)malloc(NumNodes * sizeof(lnode*));
for (i=0; i<NumNodes; i++)
1
ListColl[i] = NULL;
LNodes = (lnode**)malloc(NumNodes * sizeof(lnode*));
} else {
ForestColl = (fnode**)malloc(NumNodes * sizeof(fnode*));
for (i=0; i<NumNodes; i++) ForestColl[i] = NULL;
FNodes = (fnode**)malloc(NumNodes * sizeof(fnode*));
}
/* legge gli archi del grafo */
printf("\n numero di archi: ");
scanf("%d, &NumEdges");
for (i=0; i<NumEdges; i++) {
int a, b;
printf("\n arco %d-esimo: ");
scanf("%d %d", &a, &b);
AdjMatrix[a][b] = 1;
AdjMatrix[a][b] = 1;
} }
/* stampa il risultato */
void PrintStableSets()
{ /* stampa gli insiemi stabili risultanti */
printf("\nInsiemi Stabili:");
if (GraphRapType == 1)
for (int i=0; i<NumNodes; i++) {
if (ListColl[i] != NULL) {
lnode* pn = ListColl[i];
while (pn != NULL)
printf("%d ", pn->id);
printf("\n");
} } else {
for (int i=0; i<NumNodes; i++) {
fnode* fp = FNodes[i];
do {
printf("%d ", fp->id);
fp = fp->parent;
}
while (fp != fp->parent);
printf("%d", fp->id);
printf("\n");
} } }
/* crea un insieme disgiunto con un solo elemento */
void MakeSet(short n) {
if (GraphRapType == 1) {
lnode* pn = (lnode*)malloc(sizeof(lnode));
pn->id = n;
pn->next = NULL;
pn->rap = pn;
ListColl[n] = pn;
LNodes[n] = pn;
} else {
fnode* pn = (fnode*)malloc(sizeof(fnode));
pn->id = n;
pn->parent = pn;
ForestColl[n] = pn;
2
FNodes[n] = pn;
} }
/* trova il rappresentante dell'insieme che contiene a (liste) */
lnode* LFindSet(int n) {
return LNodes[n]->rap;
}
/* trova il rappresentante dell'insieme che contiene a (foreste) */
fnode* FFindSet(int n) { fnode* pn = FNodes[n];
while (pn != pn->parent) pn = pn->parent;
return pn;
}
/* unisce gli insiemi disgiunti che contengono a e b */
void Union(int a, int b) {
if (GraphRapType == 1) {
lnode* pn1, *pn2, *pn3;
pn1=LFindSet(a);
pn2=LFindSet(b);
if (pn1 != pn2) {
/* trova l'ultimo elemento dell'insieme che contiene b */
pn3 = pn2;
while (pn3->next != NULL) pn3 = pn3->next;
/* aggiorna tutti gli elementi dell'insieme che contiene a */
while (pn1 != NULL) {
pn1->rap = pn2;
pn1 = pn1->next;
}
ListColl[a] = NULL;
} } else {
fnode* pn1, *pn2;
pn1=FFindSet(a);
pn2=FFindSet(b);
if (pn1 != pn2) {
pn1->parent = pn2;
ForestColl[a] = NULL;
} } }
/* controlla la presenza di un ciclo */
char TryUnion(int a, int b) {
if (GraphRapType == 1) {
lnode* pa = ListColl[a];
lnode* pb = ListColl[b];
while (pa != NULL) {
while (pb != NULL) {
if (pa->id == pb->id) return 1;
else
pb = pb->next;
}
pa = pa->next;
}
3
return 0;
} else {
fnode* fp1 = FFindSet(a);
fnode* fp2 = FFindSet(b);
for (int i=0; i<NumNodes; i++) for (int j=0; j<NumNodes; j++)
if ((i != j) && (FFindSet(i) == fp1) && (FFindSet(j) == fp2)) if (AdjMatrix[i][j])
return 1;
return 0;
} }
/* main */
void main() {
/* legge il grafo e inizalizza le strutture */
ReadGraph();
/* costruisci insiemi stabili iniziali con un solo elemento */
for (int i=0; i<NumNodes; i++) MakeSet(i);
/* ingrandisci gli insiemi */
char end=0;
while (!end) {
for (i=0; i<NumNodes-1; i++)
for (int j=i+1; j<NumNodes; i++) {
/* prova ad unire gli insiemi in posizione i e j */
end = TryUnion(i, j);
if (!end) Union(i,j);
} }
/* stampa risultato */
PrintStableSets();
}
4
