Algoritmer og datastrukturer

Obligatorisk oppgave 10: Topologisk sortering av grafer

I denne oppgaven skal det lages et Java-program som implementerer en klassisk grafalgoritme som heter topologisk sortering.

1 Topologisk sortering

Topologisk sortering kan bare brukes for grafer som er rettede og som ikke inneholder cykler, ellers virker ikke algoritmen. Et eksempel på en slik graf er vist denne figuren:

Denne grafen ser ut til å ha en "hovedretning" – alle veiene går fra et "øverste lag" med noder (3, 5 og 7) og nedover mot et "nederste lag" (terminalnodene 2, 9, 10). Dette er typisk for grafer som brukes i topologisk sortering.

1.1 Definisjon

En topologisk sortering av grafen består i å finne en rekkefølge/sortering av alle nodene som er slik at:

Dersom det finnes en vei i grafen fra en node a til en node b, så skal alltid b komme etter a i sorteringen.

En topologisk sortering er altså en rekkefølge av nodene som er slik at ingen node kan komme foran en en annen node som "peker" på den.

Det er viktig å merke seg at det oftest finnes flere lovlige topologiske sorteringer av en og samme graf. For grafen som er gitt i figuren ovenfor, er hver av følgende tre rekkefølger av noder en korrekt topologisk sortering av grafen:

   7 5 3 11 8 2 9 10
   7 5 11 2 3 10 8 9
   3 7 8 5 11 10 9 2

I oppgaven gitt nedenfor skal du lage et Java-program som finner en slik topologisk sortering av en graf.

1.2 Anvendelser

Topologisk sortering brukes typisk for prosesser eller prosjekter som består av deloppgaver som avhenger av hverandre. Hver node i grafen beskriver da en slik deloppgave, og de rettede kantene angir hvilke oppgaver som må gjøres før andre oppgaver.

En topologisk sortering vil gi en rekkefølge for utførelsen av deloppgavene, som gjør at ingen oppgaver vil starte før alle deloppgavene den avhenger av er ferdige.

Et eksempel på dette er grafen nedenfor, der hver node inneholder en emnekode for et kurs/emne som tilbys i et studium (emnekodene er hentet fra informatikkstudiet ved Universitetet i Oslo). Kantene/pilene angir at ett bestemt kurs må være fullført før man kan ta neste kurs.

F.eks. ser vi fra grafen at emnet INF110 (som har tre inngående kanter) krever at man har fullført emnene MA100, INF101 og INF111. Emnet IN210 krever bl.a. MA-IN118, som igjen krever fullført MA008.

En topologisk sortering av denne grafen vil angi en "lovlig" rekkefølge for å ta alle kursene, der man alltid vil oppfylle kravene for å kunne ta hvert kurs. Det finnes flere slike lovlige rekkefølger, en av dem er denne:

MA100 INF101 MA008 INF11 INF103 MA-IN118 INF102
INF110 INF212 IN211 IN210 INF310 IN395

For en grundig innføring i topologisk sortering, se f.eks. denne videoforelesningen på YouTube:

2 En algoritme for topologisk sortering

Det finnes flere algoritmer som kan brukes for å finne topologiske sorteringer. I denne oppgaven skal vi se på en relativt enkel algoritme som alltid virker så lenge grafen er rettet og uten cykler.

2.1 Inngrad

Et viktig begrep som brukes i algoritmen for topologisk sortering er inngraden til nodene i grafen:

   Inngraden til en node i en rettet graf er antall kanter inn til noden.

For "emnegrafen" gitt ovenfor er inngraden til noden INF110 lik 3, inngraden til IN395 er 1, og inngraden til MA100 er lik 0. Det betyr at en topologisk sortering f.eks. kan starte med noden MA100, siden den ikke har noen forgjengere.

2.2 Beskrivelse av algoritmen

Vi skal bruke følgende metodikk for å bestemme en topologisk sortering:

  • For hver node i grafen holder vi hele tiden rede på antallet direkte forgjengere til noden som allerede er satt inn i sorteringen.

  • I hvert hovedsteg i algoritmen velger vi en ny node som settes inn (sist) i den topologiske sorteringen.

  • Alle de direkte forgjengerne til noden som velges ut skal allerede være satt på plass i sorteringen.

Algoritmen nedenfor, som alltid starter med en node som har inngrad lik 0, vil finne og skrive ut en topologisk sortering:

  1. Gå gjennom hele grafen, beregn og ta vare på inngraden til alle noder.

  2. Legg alle noder med inngrad lik 0 i en mengde S.

  3. Så lenge det finnes noder igjen i S:

    • Ta ut en node a fra mengden S.
    • Skriv ut noden a
    • For hver av noden a sine naboer som ikke er i S:
      • Reduser inngraden til naboen med 1.
      • Hvis denne naboen nå har fått inngrad lik 0, legg den til i mengden S.

  4. Algoritmen er ferdig, hele den topologiske sorteringen er skrevet ut.

For å lagre inngradene til hver node (steg 1) kan man bruke en ekstra array. Mengden S med noder som har inngrad 0 (steg 2) kan f.eks. lagres i en kø (stack eller liste vil også fungere fint).

Merk at algoritmen vil feile hvis det er cykler i grafen.

3 Et program som finner en topologisk sortering

Det skal lages et program som gjør følgende:

  • Leser et filnavn fra bruker. Filen skal inneholde data for en rettet og uvektet graf uten cykler.

  • Leser grafen fra fil og lagrer den i en datastruktur.

  • Finner og skriver ut en topologisk sortering av grafen.

3.1 Datastruktur

Grafen som leses fra fil skal lagres i en nabomatrise. Vi antar at de n nodene i grafen er nummerert fra 0 til n-1. Dataene i hver node er bare en enkelt tekststreng.

Følgende datastruktur skal brukes:

int n;            // Antall noder i grafen
String data[];    // Array med dataene i hver node
boolean nabo[][]; // Nabomatrise med alle kantene

3.2 Input

Grafene som skal leses inn fra fil er lagret på samme måte som beskrevet i læringsmodulen om grafer. F.eks. vil datafilen for grafen i den første figuren ovenfor, der hver av de åtte nodene bare inneholder et tall som data, se slik ut:

8
0  7 2  3 4
1  5 1  3
2  3 2  4 7
3 11 3  5 6 7  
4  8 1  6
5  2 0
6  9 0
7 10 0

Her er antall noder, n=8, angitt i første linje på filen. Deretter er det en linje for hver node, som inneholder:

  • Nodenummeret
  • Dataene i noden (et heltall i dette tilfellet)
  • Antall naboer som noden har
  • Nodenummer for alle naboene

Nedenfor ser vi hvordan innholdet i datastrukturen blir etter at filen med de n=8 nodene ovenfor er lest inn. Her er arrayindekser satt inn med grå tekstfarge:

 data       nabo         
        0 1 2 3 4 5 6 7
0 "7"   T F F T T F F F
1 "5"   F T F T F F F F
2 "3"   F F T F T F F T
3 "11"  F F F T F T T T
4 "8"   F F F F T F T F
5 "2"   F F F F F T F F
6 "9"   F F F F F F T F
7 "10"  F F F F F F F T

Vi ser at nabomatrisen inneholder verdien T-true hvis to noder er naboer, og F-false ellers. En node regnes for å være nabo med seg selv, slik at alle elementer på matrisediagonalen også er lik T. Legg merke til at dataene i hver node lagres som strenger, selv om de i dette tilfellet er tall.

I Java-koden som er gitt nedenfor er innlesing av grafen fra fil allerede ferdig programmert, du trenger ikke å kode dette selv.

3.3 Et ufullstendig Java-program

Det er laget et uferdig Java-program med en klasse TopSort, som finner en topologisk sortering av en graf. Denne koden skal du laste ned og bruke som utgangspunkt for å besvare oppgaven gitt nedenfor:

   →TopSort.java

Klasen TopSort inneholder følgende:

  • Datastrukturen med nabomatrise og data-array som er beskrevet ovenfor.

  • En konstruktør:

    public TopSort(String filNavn);

    som leser en graf fra filen med navn filNavn og lagrer den i datastrukturen. Denne konstruktøren er ferdig programmert.

  • En metode:

    public void findAndPrint();

    som skal finne og skrive ut en topologisk sortering av grafen. Denne skal du programmere ferdig i oppgaven gitt nedenfor.

  • Et main()-testprogram som henter navnet på datafilen fra bruker, leser grafdataene fra fil, og kaller metoden findAndPrint() for å skrive ut sorteringen.

4 Programmeringsoppgave

Programmer ferdig metoden findAndPrint() i klassen TopSort. Metoden skal implementere algoritmen som er beskrevet i avsnitt 2.2 ovenfor.

Du kan bruke de to rettede grafene vist i figurene ovenfor til å teste programmet du har laget. Datafiler for grafene finner dere her:

Utskrift fra kjøringer av programmet kan se slik ut:

$ java TopSort 
File? topsort1.txt
7 5 3 11 8 2 10 9 

$ java TopSort 
File? topsort2.txt
MA100 INF101 MA008 INF11 INF103 MA-IN118 INF102 INF110 INF212 IN211 IN210 INF310 IN395

Hva skal du levere?

Løsningen din legges i en fil TopSort.java. Filen, som skal inneholde et komplett og fungerende Java-program, lastes opp i Canvas som svar på oppgaven.