Labb 3

Flöden och matchningar

Om du redovisar labben senast den 4 november får du en bonuspoäng på tentan. Labbteoriuppgifterna nedan kan redovisas för en bonuspoäng till tentan, och detta görs på övningen den 7 oktober (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

Du ska i tre steg skriva ett program som får en bipartit graf som indata och producerar en matchning av maximal storlek som utdata genom att reducera (transformera) matchningsproblemet till flödesproblemet. Korrekthet och effektivitet testas genom att lösningarna på de tre stegen skickas till Kattis. För att klara labben ska du bli godkänd av Kattis på de tre stegen samt redovisa labben för en handledare. Kattis kontrollerar både att programmet gör rätt och att det löser problemet tillräckligt snabbt. Kattis klarar av programspråken Java, C, C++ och Python, men tidskraven i denna labb gör att vi avråder från Python.

Steg 1: Reducera problemet till flödesproblemet
Du ska skriva ett program som löser matchningsproblemet med hjälp av en svart låda som löser flödesproblemet. Programmet ska fungera enligt denna översiktliga programstruktur:

  • Läs indata för matchningsproblemet från standard input.
  • Översätt matchningsinstansen till en flödesinstans.
  • Skriv indata för flödesproblemet till standard output (se till att utdata flushas).
  • Den svarta lådan löser flödesproblemet.
  • Läs utdata för flödesproblemet från standard input.
  • Översätt lösningen på flödesproblemet till en lösning på matchningsproblemet.
  • Skriv utdata för matchningsproblemet till standard output.

Se nedan hur in- och utdataformaten för matchnings- och flödesproblemen ser ut.

Ditt program ska lösa problemet effektivt. Kattis kommer att provköra programmet på bipartita grafer på upp till (5000+5000) hörn och upp till 10000 kanter. Kattis känner till problemet som oldkattis.adkreducetoflow. Det finns ett programskelett för steg 1 i några olika språk på katalogen /info/adk16/labb3/exempelprogram

Steg 2: Lös flödesproblemet
Nu ska du skriva ett program som löser flödesproblemet. Programmet ska läsa indata från standard input och skriva lösningen till standard output. Se nedan hur in- och utdataformaten för flödesproblemet ser ut.

Ditt program ska lösa problemet effektivt. Kattis kommer att provköra programmet på generella flödesgrafer på upp till 2000 hörn och 10000 kanter. Kattis känner till problemet som oldkattis.adkmaxflow.

Steg 3: Kombinera steg 1 & 2
I steg 1 löste du matchningsproblemet med hjälp av en lösning till flödesproblemet. I steg 2 löste du flödesproblemet. Nu ska du kombinera dessa lösningar till ett enda program genom att byta ut kommunikationen av flödesinstansen över standard input och standard output till ett funktionsanrop. Programmet ska fortfarande läsa indata från standard input och skriva lösningen till standard output.

Ditt program ska lösa problemet effektivt. Kattis kommer att provköra programmet på bipartita grafer på upp till (5000+5000) hörn och upp till 10000 kanter. Kattis känner till problemet som oldkattis.adkbipmatch.

Matchningsproblemet
Givet en bipartit graf G = (X,Y,E) finn en maximal matchning.

Indata
Den första raden består av två heltal som anger antalet hörn i X respektive Y.
Den andra raden består av ett tal som anger |E|, det vill säga antalet kanter i grafen.
De följande |E| raderna består var och en av två heltal som svarar mot en kant.

Hörnen numreras från 1 och uppåt. Om man angett a hörn i X och b hörn i Y så låter vi X = {1, 2,..., a} och Y = {a+1, a+2,..., a+b}. En kant anges med ändpunkterna (först X-hörnet och sedan Y-hörnet).

Exempel: En graf kan till exempel kodas så här.

2 3
4
1 3
1 4
2 3
2 5

Denna graf har alltså X = {1, 2} och Y = {3, 4, 5}. Kantmängden E innehåller kanterna (1, 3), (1, 4), (2, 3) och (2, 5).

Utdata
Först skrivs en rad som är densamma som den första i indata, och därefter en rad med ett heltal som anger antalet kanter i den funna matchningen. Därefter skrivs en rad för varje kant som ingår i matchningen. Kanten beskrivs av ett talpar på samma sätt som i indata.

Exempel: Om vi har grafen ovan som indata så kan utdata se ut så här.

2 3
2
1 3
2 5

Flödesproblemet
Givet en flödesgraf G = (V,E) finn ett maximalt flöde. Lös flödesproblemet med Edmonds-Karps algoritm, det vill säga Ford-Fulkersons algoritm där den kortaste stigen hittas med breddenförstsökning.

Ford-Fulkersons algoritm i pseudokod

c[u,v] är kapaciteten från u till v, f[u,v] är flödet, cf[u,v] är restkapaciteten.

for varje kant (u,v) i grafen do 
    f[u,v]:=0; f[v,u]:=0 
    cf[u,v]:=c[u,v]; cf[v,u]:=c[v,u
while det finns en stig p från s till t i restflödesgrafen do 
    r:=min(cf[u,v]: (u,v) ingår i p
    for varje kant (u,v) i p do 
         f[u,v]:=f[u,v]+r; f[v,u]:= -f[u,v
         cf[u,v]:=c[u,v] - f[u,v]; cf[v,u]:=c[v,u] - f[v,u]

Indata
Den första raden består av ett heltal som anger antalet hörn i V.
Den andra raden består av två heltal s och t som anger vilka hörn som är källa respektive utlopp.
Den tredje raden består av ett tal som anger |E|, det vill säga antalet kanter i grafen.
De följande |E| raderna består var och en av tre heltal som svarar mot en kant.

Hörnen numreras från 1 och uppåt. Om man angett a hörn i V så låter vi V = {1, 2,..., a}. En kant anges med ändpunkterna (först från-hörnet och sedan till-hörnet) följt av dess kapacitet.

Exempel: En graf kan till exempel kodas så här.

4
1 4
5
1 2 1
1 3 2
2 4 2
3 2 2
3 4 1

Utdata
Den första raden består av ett heltal som anger antalet hörn i V.
Den andra raden består av tre heltal s,t, samt flödet från s till t.
Den tredje raden består av ett heltal som anger antalet kanter med positivt flöde.
Därefter skrivs en rad för varje sådan kant. Kanten beskrivs av tre tal på liknande sätt som i indata, men i stället för kapacitet har vi nu flöde.

Exempel: Om vi har grafen ovan som indata så kan utdata se ut så här.

4
1 4 3
5
1 2 1
1 3 2
2 4 2
3 2 1
3 4 1

Testning
I katalogen /info/adk16/labb3 ligger programmen bipgen, flowgen, maxflow, combine och matchtest som du kan köra för att testa dina program.

  • Programmet bipgen genererar en slumpvis vald bipartit graf. Grafen skrivs på standard output på ovan angivet format för indata till matchningsprogrammet. 

    /info/adk16/labb3/bipgen x y e 

    ger en graf med x hörn i Xy hörn i Y och e kanter.

  • Programmet flowgen genererar en slumpvis vald flödesgraf. Grafen skrivs på standard output på ovan angivet format för indata till flödesprogrammet. 

    /info/adk16/labb3/flowgen v e c 

    ger en graf med v hörn och e kanter vars kapaciteter är positiva heltal inte större än c.

  • Programmet maxflow löser flödesproblemet och kan användas som svart låda i steg 1. maxflow tar en flödesgraf på standard input och skriver ut ett maximalt flöde på standard output.

  • Programmet combine är ett hjälpprogram som du kan använda dig av i steg 1 för att få ditt program att prata med den svarta lådan. 

    /info/adk16/labb3/combine java MatchReduce \; /info/adk16/labb3/maxflow < graffil > matchfil 

    kommer att köra java MatchReduce som lösning på steg 1, och använda kursens maxflow-program som svart låda. Indatagrafen tas från filen graffil och utdata skickas till filen matchfil.
  • Programmet matchtest läser en graf följt av utdata från ett matchningsprogram (alltså, först grafen och sedan matchningen) och kontrollerar att matchningen är maximalt stor. Utdata skrivs på standard outputoch kan vara Matchning av maximal storlekMatchning av mindre än maximal storlek eller Ingen matchning.

    Så här kan du använda bipgen och matchtest för att testa din lösning på steg 3 (minlabb).

    /info/adk16/labb3/bipgen 5000 5000 10000 > graffil 
    minlabb < graffil > matchfil 
    cat graffil matchfil | /info/adk16/labb3/matchtest

  • Bra testfall att testa de tre stegen med finns på /info/adk16/labb3/testfall/

Om du inte vet vad tecknen >, < och | betyder i exemplen ovan så kan du titta i Unixhäftet eller fråga en labbhandledare. För att kolla hur lång tid ditt program kör på dina egna testfall kan du använda kommandot time och titta på user time.

Teoriuppgifter

  1. Jämför tidskomplexiteten för algoritmen då grafen implementeras som en grannmatris och då den implementeras med grannlistor. (För att satsen f[v,u]:= -f[u,v] ska kunna implementeras effektivt måste grannlisteimplementationen utökas så att varje kant har en pekare till den omvända kanten.)

    Uttryck tidskomplexiteten i n och m där n är totala antalet hörn och m antalet kanter i den bipartita grafen. Välj sedan den implementation som är snabbast då m=O(n), alltså då grafen är gles.

  2. Kalle menar att om vi börjar med en bipartit graf G och gör om den till en flödesgraf H med ny källa s och nytt utlopp t så kommer avståndet från s till t att vara 3.

    Kalle tycker därför att BFS-steget alltid kommer att hitta en stig av längd 3 i restflödesgrafen (om det finns någon stig).

    Det första påståendet är sant, men inte det andra. Varför har stigarna som BFS hittar i restflödesgrafen inte nödvändigtvis längd 3? Hur långa kan de bli?

  3. Anledningen till att bipartit matchning kan reduceras till flöde är att en lösning till flödesproblemet kan tolkas som en lösning till matchningsproblemet. Detta gäller bara om det flöde som algoritmen ger är ett heltalsflöde (flödet i varje kant är ett heltal), vilket i detta fall innebär att flödet längs en kant antingen är 0 eller 1. Som tur är så är det på det sättet.
    • Bevisa att Ford-Fulkerson alltid genererar heltalsflöden om kantkapaciteterna är heltal!
    • Vad händer med lösningarna som flödesalgoritmen ger om man ändrar i reduktionen så att kantkapaciteterna sätts till 2 istället för 1? 

Viggo Kann created page 19 August 2016

Teacher Viggo Kann changed the permissions 19 August 2016

Kan därmed läsas av lärare och ändras av lärare.

Teacher Viggo Kann changed the permissions 16 September 2016

Kan därmed läsas av alla och ändras av lärare.
commented 28 September 2016

Vilken algoritm syftar första teoriuppgiften till? "Jämför tidskomplexiteten för algoritmen då grafen implementeras som en grannmatris och då den implementeras med grannlistor."

Teacher commented 28 September 2016

Albin, det syftar på algoritmen för att hitta bästa bipartita matchningen, vilket man kan förstå av meningen "Uttryck tidskomplexiteten i n och m där n är totala antalet hörn och m antalet kanter i den bipartita grafen."

commented 28 September 2016

Vad är relationen mellan c[u,v] och c[v,u]? I indatan får man t.ex. att c[1,2] = 1, men det står ingenting om c[2,1] för kapaciteten går väl bara åt ett håll.

Teacher commented 28 September 2016

Abdallah, det kan finnas kapaciteter (som är olika) i båda riktningarna mellan två hörn, se föreläsningen eller boken för exempel. Om en kapacitet inte omnämns i indata så är den noll.

commented 30 September 2016

Länken till Unixhäftet funkar inte, skulle det gå att fixa?

Tack på förhand!

Teacher commented 30 September 2016

Johan, jag har uppdaterat länken, men det hjälper inte just nu eftersom det är något fel på själva PDF-dokumentet. Jag har felanmält till IT-avdelningen. Tills vidare kan du kolla på den här sidan.

One user removed his/her comment
commented 25 October 2016

Hej!

I testfallen i Kattis, i del 2 av denna labb - kan flödesgrafens kapaciteter vara större än 1? För att lösa matchningsproblemet i hela labben använder man ju annars bara ett flöde av max 1.

Teacher commented 25 October 2016

Anna-Karin, i flödesgraferna som Kattis testar i del 2 kan kapaciteterna vara större än 1.

commented 27 October 2016

I första slingan i Ford-Fulkersons algoritm, om exempelvis c(1,2) = 16, vad är då c(2,1)? Är den -16? 0?

Teacher commented 27 October 2016

c[1,2] är kapaciteten från hörn 1 till hörn 2. c[2,1] är kapaciteten från hörn 2 till hörn 1. Dessa är oberoende av varandra.

One user removed his/her comment
One user removed his/her comment
commented 2 November 2016

Hur skall man kunna introducera ett flöde mellan kanterna?

Teacher commented 3 November 2016

Jonathan, flödet går längs kanterna i flödesgrafen. I pseudokoden för Ford-Fulkerson ovan ökas flödet längs en kant på den näst sista raden (i den inre for-slingan).

commented 4 November 2016

Vilken tid öppnas queue för labben?

Vissa har seminarium i Vettig mellan 14 och 15 vilket innebär att det skulle vara trevligt att kunna redovisa inom intervallet 13-14. Märkte att kön är stängd (är förvisso ute i kanske lite väl god tid) så tänkte höra när den öppnar?

One user removed his/her comment
Teacher commented 4 November 2016

Patrick, labbkön öppnas cirka kl 11.30 idag. Men på grund av en krockande programmeringstävling så har vi färre handledare än normalt, så redovisningarna måste spridas ut ganska jämnt över hela labbtiden 13-17. Den som har krockande undervisning 14-15 rekommenderas att redovisa efter kl 15 istället.

Sylwester, matchtest ger felutskrifter om beskrivningen av den bipartita grafen inte uppfyller kraven på indata i uppgiftslydelsen: Hörnen numreras från 1 och uppåt. Om man angett a hörn i X och b hörn i Y så låter vi X = {1, 2,..., a} och Y = {a+1, a+2,..., a+b}. Y är alltså den högra partitionen.

Feedback News