/****************************************************************************
*
* graph-check-2col.c -- Controlla se un grafo è 2-colorabile
*
* Copyright (C) 2021, 2022 Moreno Marzolla
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*
****************************************************************************/
/***
% LabASD - Controlla se un grafo è 2-colorabile
% Moreno Marzolla
% Ultimo aggiornamento: 2022-04-04
Un grafo non orientato $G = (V, E)$ è 2-colorabile se è possibile
assegnare a ciascun nodo un colore scelto tra due possibili, in modo
che nodi adiacenti abbiano colori diversi. Formalmente, un grafo è
2-colorabile se esiste una funzione $c: V \rightarrow \{1, 2\}$ tale
che:
$$
c(u) \neq c(v)\ \mbox{per ogni arco}\ \{u,v\} \in E
$$
Ad esempio, il grafo in Figura 1(a) è 2-colorabile, mentre il grafo in
Figura 1(b) non lo è.
![Figura 1: Esempio di grafo 2-colorabile e non 2-colorabile](graph-check-2col.svg)
Scrivere un programma che, dato un grafo non orientato, determina se è
2-colorabile oppure no. **Attenzione:** il grafo potrebbe essere _non_
connesso.
## Suggerimento
È possibile risolvere questo problema applicando un algoritmo di
visita ([BFS](bfs.html) oppure [DFS](dfs.html)) al grafo $G$. La
visita inizia assegnando un colore arbitrario al primo nodo;
successivamente, i nodi adiacenti ricevono il colore opposto a quello
appena usato. Se si è costretti ad applicare un colore diverso ad un
nodo già colorato, allora il grafo non è 2-colorabile. Si presti
attenzione al fatto che il grafo $G$ non è necessariamente connesso,
quindi occorre ripetere il procedimento per ogni componente connessa.
Per compilare:
gcc -std=c90 -Wall -Wpedantic graph.c graph-check-2col.c -o graph-check-2col
> **Nota** il comando di compilazione potrebbe essere diverso se si
> decide di basare la visita sull'algoritmo [BFS](bfs.html), perché
> occorre includere e linkare l'implementazione della coda.
Per eseguire:
./graph-check-2col graph-2col-yes.in
## File
- [graph-check-2col.c](graph-check-2col.c)
- [graph.c](../solutions/graph.c)
- [graph.h](../solutions/graph.h)
- [Esempio di grafo 2-colorabile](graph-2col-yes.in) (è il grafo in Figura 1(a))
- [Esempio di grafo NON 2-colorabile](graph-2col-no.in) (è il grafo in Figura 1(b))
- [graph-2col-1.in](graph-2col-1.in)
- [graph-2col-2.in](graph-2col-2.in)
- [graph-2col-3.in](graph-2col-3.in)
- [graph-2col-4.in](graph-2col-4.in)
***/
#include
#include
#include
#include
#include "graph.h"
typedef enum { UNCOLORED, RED, BLUE } Color;
/* Ritorna true (nonzero) se è possibile colorare il grafo `g` dopo
aver assegnato il colore `c` al nodo `u`. Se il nodo `u` era già
stato colorato con un colore diverso da `c`, il grafo non è
2-colorabile e ritorna 0. */
int graph_2col_rec(const Graph *g, Color *col, int u, Color c)
{
static const Color opposite[] = {UNCOLORED, BLUE, RED};
if (col[u] == UNCOLORED) {
const Edge *e;
int colorable = 1;
col[u] = c;
for (e = graph_adj(g, u); e != NULL && colorable; e = e->next) {
colorable &= graph_2col_rec(g, col, e->dst, opposite[c]);
}
return colorable;
} else if (col[u] == c)
return 1;
else
return 0;
}
/* Ritorna true (nonzero) se e solo se g è 2-colorabile, 0
altrimenti */
int graph_2col(const Graph* g)
{
const int n = graph_n_nodes(g);
Color *col = (Color*)malloc(n * sizeof(*col));
int v, colorable;
assert( col != NULL );
for (v=0; v