"; exit; } print "
Dimacs graph url : $url
";
$fp = fopen("$url", "r");
$content = "";
while(!feof($fp)) $content .= fread($fp, "4096");
fclose($fp);
$table = explode("\n",$content);
}
function zero_matrice($taille)
{
global $matrice;
for ($i=0;$i<$taille;$i++)
for ($j=0;$j<$taille;$j++)
$matrice[$i][$j]=0;$matrice[$j][$i]=0;
}
function init_matrice()
{
global $matrice, $table, $N, $M;
$lg=sizeof($table);
for($i=0;$i<$lg;$i++) {
$ligne = explode(" ",$table[$i]);
switch ($ligne[0]):
case "p":
$N=$ligne[2];$M=$ligne[3];
zero_matrice($N);
break;
case "e":
$i1=$ligne[1];$j1=$ligne[2];
$matrice[$i1][$j1]=1;$matrice[$j1][$i1]=1;
break;
default:
break;
endswitch;
}
}// function
/*-----------------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------------*/
/* initialisation du vecteur de la coloration des sommets*/
function init()
{
global $N,$colorsommet,$matrice,$DSAT;
for ($i = 1; $i <= $N; $i++) $colorsommet[$i]=-1;
for ($i = 1; $i <= $N; $i++) {
$somme=0;
for ($j = 1; $j <= $N; $j++) $somme=$somme+$matrice[$i][$j];
$DSAT[$i]=$somme;
}
}// fin init
/*-----------------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------------*/
/*recherche du sommet de dsat max*/
function recherchesommet()
{
global $N,$DSAT,$s;
$eps=0;
for ($j = 1; $j <= $N; $j++) {
if ($DSAT[$j] > $eps) {
$eps=$DSAT[$j];
$s=$j;
}
}
}
/*----------------------------------------------------------------------------------*/
/* fonction remplicolor :donne un vecteur indice par les couleurs avec 0 ou 1 dedans*/
/*----------------------------------------------------------------------------------*/
function remplicolor ($sommet_a_etudier)
{
global $N,$matrice,$colorsommet;
for ($i = 1; $i <= $N; $i++) $used_color[$i]=0;
for ($i = 1; $i <= $N; $i++)
if ($matrice[$sommet_a_etudier][$i]==1)
if ($colorsommet[$i] != -1) {
$used_color[$colorsommet[$i]]=1;
//print "
remplicolor: sommet s=$s voisin=$i couleur($i)=$colorsommet[$i] ";
}
return $used_color;
}
/*----------------------------------------------------------------------------------*/
/* recherche de la couleur minimum pour la coloration du sommet */
/*----------------------------------------------------------------------------------*/
function recherchecouleurmin($vecteur_color)
{
global $color,$colorsommet,$s;
$i = 0;
while ($vecteur_color[$i] != 0){
$i++;
}
$colorsommet[$s]=$i;
//print "
recherchecouleurmin : sommet s=$s avec couleur $i ";
}
/*----------------------------------------------------------------------------------*/
/* mise jour de DSAT */
/*----------------------------------------------------------------------------------*/
function majDSAT()
{
global $matrice,$N,$DSAT,$colorsommet,$s;
for ($j = 1; $j <= $N; $j++)
{
if ($matrice[$s][$j]==1)
{
if ($colorsommet[$j]==-1)
{
$used_color=remplicolor($j);
$nbrecouleur=0;
for ($k = 0; $k < $N; $k++)
{
$nbrecouleur=$nbrecouleur+$used_color[$k];
}
$DSAT[$j]=$nbrecouleur;
}
}
}
$DSAT[$s]=0;
}
/*-----------------------------------------------------------------------------------*/
/* VERIF COLOR */
/*-----------------------------------------------------------------------------------*/
function verif_color()
{
global $matrice, $colorsommet, $N;
print "
---------------
COLOR VERIFICATION:";
for ($i=1;$i<=$N;$i++){
for ($j=1;$j<=$N;$j++){
if (($matrice[$i][$j]>0)&&($colorsommet[$j]==$colorsommet[$i])){
print "
!!! Color conflit... ($i)c=$colorsommet[$i]----($j)c=$colorsommet[$j]
";
$bad=3;
}
}
}
if ($bad==3)
print "
===> Wrong coloration !!!!
";
else
print " OK.
";
}
/*-----------------------------------------------------------------------------------*/
/* DISPLAY */
/*-----------------------------------------------------------------------------------*/
function display_color_des_sommets()
{
global $colorsommet, $N;
print "
---------------
DISPLAY COLOR :
";
for ($i=1;$i<=$N;$i++){
print "\n
Vertex $i : color=$colorsommet[$i] \n";
}
}
/*-----------------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------------*/
function display_matrice(){
global $matrice, $N, $M;
print "
---------------
MATRICE N=$N M=$M
";
for ($i=1;$i<=$N;$i++){
print "\n
row $i: \n";
for ($j=1;$j <= $N; $j++) {
$val = $matrice[$i][$j];
print " $val ";
}
}
}
//--------------------------------------------------//
//--------------------------------------------------//
// MAIN //
//--------------------------------------------------//
//--------------------------------------------------//
print "