Fortran : Coloration de graphe

Aujourd'hui, un peu de théorie des graphes en Fortran 90 ! (Je teste la coloration avec Rubyshyne en Fortran...)

Il s'agit d'un programme de coloration de graphe. Celle-ci est utilisée dans divers domaine, par exemple pour colorer automatiquement une carte avec différentes entités (pays, régions ou autre).

Comment ?

En consultant Wikipedia, je me suis rendu compte que j'ai "refait" sans le savoir l'algorithme classique pour ce problème, à savoir l'algo de Welsh & Powell. Pour la petite info, cet algo se base en partie sur le théorème des 4 couleurs, premier théorème mathématique dont la démonstration a nécessité l'utilisation d'un ordinateur (près d'un siècle après sa première formulation !).

Entrées-Sorties :

Ce programme prend en entrée la matrice du graphe à analyser, précédée du nombre de sommets (fichier tab.dat). Exemple :

6
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 1 1 0
0 0 1 0 0 1
0 1 1 0 0 0
0 0 0 1 0 0

Ce qui donne en graphe et en "carte" (déjà colorés ici pour l'exemple) :

Le code :

PROGRAM Coloration
 IMPLICIT NONE
 integer, allocatable :: A(:,:)
 integer, allocatable :: Degree(:), AliasD(:), B(:), Color(:)
 integer :: i, n, tmp, tmpD, ii, icolor
 character(len=999) :: format_tab
 character(len=6) :: motif = 'I1,1X,'
 logical :: pas_adj
 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 ! LECTURE DU GRAPHE
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 PRINT*, '    '
 OPEN(UNIT=10, FILE='tab.dat', FORM='formatted', STATUS='OLD')
 
 READ(10,'(I6)') n
 PRINT*, 'Taille du graphe : ', n
 Print*, '    '
 ALLOCATE(A(n,n))
 ALLOCATE(Degree(n))
 ALLOCATE(AliasD(n))
 ALLOCATE(B(n))
 ALLOCATE(Color(n))
 
 Color = 0
 
 format_tab = '('
 DO i = 1, n-1
  format_tab = format_tab(1:(6*i-5))//motif
 END DO

 format_tab = format_tab(1:(6*n-5))//'I1)'
 
 PRINT*, 'Matrice du graphe : '
 DO i = 1, n
  READ(10, format_tab) A(i, 1:n)
  B(i) = i
  PRINT*, A(i, 1:n)
 END DO
 PRINT*, '    '
 
 CLOSE(10)
 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 ! TRI PAR DEGRE
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 DO i = 1, n
  Degree(i) = SUM(A(i,1:n))
 END DO
 
 AliasD = Degree
 
 ii = 1
 DO WHILE (ii < n)
  IF (AliasD(ii+1)>AliasD(ii)) THEN

   tmp = B(ii)
   tmpD = AliasD(ii)
   B(ii) = B(ii+1)
   AliasD(ii) = AliasD(ii+1)
   B(ii+1) = tmp
   AliasD(ii+1) = tmpD
   IF (ii > 1) THEN 
    ii = ii - 1
   ELSE
    ii = 1
   END IF
  ELSE

   ii = ii + 1
  END IF
 END DO
 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 ! COLORATION
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 Color(B(1)) = 1
 DO icolor = 1, 4
  ii = 2
  DO WHILE (ii < n+1)
   IF (Color(B(ii))==0) THEN

   
    pas_adj = .TRUE.
    DO i = 1, n
     IF ((Color(i)==icolor).AND.(A(B(ii),i)/=0)) THEN
      pas_adj = .FALSE.

     END IF
    END DO
    
    IF (pas_adj) THEN
     Color(B(ii)) = icolor
    END IF

    
   END IF
   ii = ii + 1
  END DO
 END DO
 
 !!!!!!!!!!!!!!!!!!!!!!!!!!

 ! RESULTATS
 !!!!!!!!!!!!!!!!!!!!!!!!!!
 PRINT*, '      '
 PRINT*, 'Coloration : '
 PRINT*, Color
 
END PROGRAM Coloration