Labb 3

Flöden och matchningar

Om du redovisar labben senast den 8 november får du en bonuspoäng på tentan. På övningen 10 oktober har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus. 
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/adk13/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/adk13/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/adk13/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/adk13/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/adk13/labb3/combine java MatchReduce \; /info/adk13/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/adk13/labb3/bipgen 5000 5000 10000 > graffil 
    minlabb < graffil > matchfil 
    cat graffil matchfil | /info/adk13/labb3/matchtest

  • Bra testfall att testa de tre stegen med finns på /info/adk13/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!

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 18 October 2013

Vi får NullPointerExeption på testfall 27 på "Reduktion av bipartit matchning till flöde". Något tips om vad som kan vara felet här? Vi har testat med kantmängder som 0 och hörnmängder som 0. Dessutom skapar vi inga objekt, så vi känner oss lite lost.

Tacksam för svar.

Teacher commented 19 October 2013

Testfall 27 är en stor graf. Det är nog interaktionen med domaren som ger upphov till felet. Se till att in- och utmatningen använder Kattio och att ni gör flush efter att flödesinstansen skrivits ut, så att domaren kan lösa instansen och skriva ut en flödeslösning innan programmet läser den.

commented 19 October 2013

Ah det löste sig. Bytte ut allt mot Kattio istället så fungerade samma kod :)

Men en anna sak. Om kattis har accepterat din lösning av "den svarta lådan" i steg två, och sen får du time limit exceeded på steg 3 när man lägger ihop allting, kan man förutsätta att den svarta lådan är bra, och man borde snabba på reduktionen, eller finns det en möjlighet att även flödesproblemet löses för långsamt, även om steg 2 är passerat?

Teacher commented 23 October 2013

Steg 2 testar flödesalgoritmen på många olika typer av flödesgrafer. I steg 3 kommer flödesalgoritmen bara att testas med instanser som kommer från reduktionen av bipartit matchning, och dessa har ett speciellt utseende. Därför kan det ibland hända att flödesalgoritmer som klarar steg 2 tar lite för lång tid på steg 3, även om detta inte är avsikten.

commented 23 October 2013

Tack. Kom på lite fler optimeringar man kunde göra, så löste det sig fint.

commented 28 October 2013

Vi får felet "Försöker trycka mer flöde genom kant än den har kapacitet" på första testfallet i labbdel 2 på Kattis. Vi har testat med alla tesfall i kursmappen och allt ser korrekt ut, vi lyckas inte få något likande fel alls med någon testkörning utan allt verkar fungera. När vi skriver ut värdet för flödet för varje kant har vi till och med en koll att den inte är högre än kapaciteten. Några idéer? Hur kan graferna se ut, finns dubbelkanter, lömska grafer eller s och t som inte finns, osv? Hur stora värden på flödet kan det vara, så stora att de inte får plats i en short?

commented 28 October 2013

Varför köra short? Int fungerar väl bra?

Teacher commented 29 October 2013

Om man får felet "Försöker trycka mer flöde genom kant än den har kapacitet" beror det ofta på att man fått flöde i en bakåtkant som har kapaciteten noll. Algoritmen ska klara alla sorters grafer som uppfyller indatakraven, även såna som inte har någon förbindelse mellan källan och utloppet. Inga dubbelkanter. Kapaciteterna ryms i en int (och kanske också i en short).

commented 29 October 2013

Testar kattis med flöden som är över 1 i storlek i första uppgiften?

Teacher commented 29 October 2013

Kattis testar med bipartita grafer, inte med flödesgrafer, i första uppgiften. Flödesgrafen ska ert program generera i reduktionen.

commented 29 October 2013

Okej, men kan en kantvikt i den bipartita grafen ha ett värde över 1?

För jag printar ut:  io.println(a + " " + b + " " + 1); vid en kant och tar ingen hänsyn till kantvikten

Teacher commented 29 October 2013

I reduktionen av problemet bipartit matchning till flödesproblemet så ska alla kanter i flödesgrafen ha kapaciteten 1. Varje kant har flera värden så det är oklart vad du menar med "kantvikten".

commented 30 October 2013

Lite osäker på varför jag får wrong answer isf, men det blir ett trevligt problem för dagen...
Som tur är så har jag en till fråga!

I ett av exemplen ovan så är indata:

4
1 4
5
1 2 1
1 3 2<----
2 4 2<----
3 2 2<----
3 4 1

När kattis testar programmet kommer indatan att kunna se ut såhär, för jag har valt att inte läsa av värdet i sista kolumnen då jag antar att i vårt problem kommer den alltid att vara 1!

Men det kan vara så att ni vill ha en generell lösning till ett flödesproblem, stämmer detta?

Teacher commented 30 October 2013

I uppgift 2 ska ett program som löser flödesproblemet för generella flödesgrafer konstrueras. Det betyder att kapaciteterna inte behöver vara bara 1. Detta framgår av uppgiftslydelsen och exemplen som getts.

commented 30 October 2013

Vi har också problem med just uppgift 2 där Kattis anser att vi har "Wrong Answer" men vi kan inte finna var felet ligger, vi passerar aldrig case 1.
Vi har dessutom genererat flertalet grafer med programmet flowgen och jämfört vårt resultat med det som programmet maxflow visar och ser ingen skillnad.

Här är en körning med exemplet som nämndes ovan från io (fet-stil output):

4
1 4
5
1 2 1
1 3 2
2 4 2
3 2 2
3 4 1
4
1 4 3
5
1 2 1
1 3 2
2 4 2
3 2 1
3 4 1
commented 30 October 2013

Vi har också problem med wrong answer i uppgift 2. Vi har byggt 3 separata program i java som alla klarar våra testfall utanför kattis. Men i kattis får vi endast "Försöker ta ut mer flöde än vad som trycks in i nod skiljd från källan" samt "Försöker trycka ut mer flöde genom kant än den har kapacitet". Vad kan vara fel? Vi har hittat på så många specialfall vi kan men programmet fungerar för alla.

Assistant commented 30 October 2013

Tänk på att bakåtkanterna ska ha "initialkapacitet" 0! (Det är inte förrän man har ett flöde genom kanten e som det kan bli aktuellt att minska det flödet. Restkapaciteten på en bakåtkant talar ju om hur mycket man kan minska flödet längs den kanten.)

commented 30 October 2013

Ahhh.. sant :) Hade missade de, nu till att optimera koden så att den klarar case 27 :)

Tack Emma! :)

Tonima Afroze removed his/her comment
commented 31 October 2013

Är cykler tillåtna i uppgift 2?

Teacher commented 31 October 2013

Flödesgrafen är en generell riktad graf och kan innehålla cykler. Men ett flöde i grafen kan förstås aldrig gå i en cykel.

Robin Engström removed his/her comment
commented 31 October 2013

Vi får Time limit exceeded på testfall 28, är det något speciellt med den grafen eller är den bara väldigt stor?

Assistant commented 31 October 2013

28 är ungefär lika stort som 27 (nära maxstorleken) och jag har ingen lathund som berättar vad varje testfall är till för...

Teacher commented 31 October 2013

Det finns ingen dokumentation av vilket testfall som testar vad i Kattis. Labbuppgiften är att skriva ett program som är korrekt och tillräckligt snabbt, och det visas genom att det klarar alla testfall. Om man kör fast på ett specifikt testfall kan man fråga en labbhandledare på nästa labbtillfälle och då kan labbhandledaren (om ni har gått med i adk13 i Kattis) kolla i Kattis på just det testfallet och kanske ge en ledtråd till varför programmet fastnar på det.

commented 6 November 2013

Vår algoritm får problem när flowgen ger oss kanter både mellan a och b och mellan b och a. Dvs det finns kanter vars bakåtkant inte har kapacitet 0 i början. Är denna typ av indata korrekt?

Assistant commented 6 November 2013

Ja, en riktad graf kan ha kanter både från a till b och från b till a. Bakåtkanterna ni lägger till hör till restflödesgrafen som behövs i lösningsmetoden ni använder (Ford-Fulkerson/Edmond-Karp), och är ett sätt att representera att man kan minska flödet längs en kant som redan har flöde. 

Eric Molin removed his/her comment
Eric Molin removed his/her comment
commented 7 November 2013

Vi klarar alla testfall i del 1, och del 3, men i del 2 får vi time limit exceeded på testfall 27. Finns det nån förklaring till detta? Känns oerhört konstigt. Vi har exakt samma maxflödesalgoritm.

commented 7 November 2013

Vi klarar i uppgift 2 galant upp till 26, men i uppgift 27 får vi plötsligt "Utdatafilen inte fullständig, saknades kanter". Att felsöka detta testfall är extremt svårt då vi inte kan hitta några testfall där detta gäller. Hjälp?

commented 7 November 2013

Vi får time limit exceeded på testfall 26 i steg 2. Vi kommer inte på fler sätt att göra programmet snabbare, och vi har gjort alla uppenbara optimeringar. Är det något speciallfall som vi kan ha missat?

commented 7 November 2013

På uppgift 2 säger Kattis "Memory limit exceeded" på testfall 2. Hur begränsat är minnesutrymmet?

commented 7 November 2013

Minnesutrymmet är 64 MB. Det kan man se om man tittar i Kattis på problemsidan. Där ser man dessutom tidsgräns.

Assistant commented 7 November 2013

Till er som undrar om TLE i steg 3: Det är inte meningen att man ska ha större problem i uppgift 3 än i uppgift 2 med tiden, men det kan ju vara gränsfall. Om ni inte använder Kattio, och skriver i Java, kan ni eventuellt snabba upp IO med att använda Kattio.

Titta i övrigt på vilka datastrukturer ni använder, och att de är tillräckligt snabba, inte innebär en massa indirekta ominstansieringar osv.

Den som använder DFS kan skissa på ett testfall som triggar värstafallskomplexiteten, och se att det kan vara värt att byta till BFS.

Assistant commented 7 November 2013

För alla som undrar över "Wrong answer" för steg 2, fundera på om er algoritm gör rätt på ett testfall med exempelvis s=1, t=7 och kanterna 

1 2 10, 1 3 11, 2 4 8, 2 5 2, 2 6 11, 3 4 11, 4 2 3, 4 7 8, 5 7 2, 6 7 11,

där det inte ska spela någon roll i vilken ordning stigarna hittas. Det här är ett exempel jag gav till någon som frågade mig tidigare.

Eric, det fel som rapporteras som att det saknades kanter i utdatafilen, är att ni inte skriver ut en så stor utdatainstans som ni påstår i början. Jag vet inte om det är relaterat till andra testfallet ovan.

commented 7 November 2013

Vad jag har märkt så verkar trean alltid ta längre tid än tvåan, om man använder samma kod från tvåan i trean.

Assistant commented 7 November 2013

Marcus: Specialfall i för testfall 26 i adkmaxflow känner jag inte till något om. Jag har bara samma tips som för steg 3 i labben: kontrollera om det finns snabbare datastrukturer eller standardmetoder för det ni vill göra, se till att in- och utläsning är effektiv!

Assistant commented 7 November 2013

Emil: tack för iakttagelsen!

Den som vill utsätta sitt program för lite tuffare tester kan skicka in koden till problemet maxflow. Formatet för de första raderna av in- och utdata behöver ändras då, men algoritmen ska vara densamma.

commented 7 November 2013

Ni som kör Java och får Time Limit Exceeded, här är några optimeringstips:

1. Använd inte LinkedList. Kör istället ArrayList alternativt ArrayDeque (för kö-funktionalitet).

2. För att iterera över en ArrayList, använd inte inbyggda iteratorer utan gör det manuellt, dvs. skriv inte for(Obj obj : list) { ... } utan skriv for(int i=0; i<list.size(); i++) { Obj obj = list.get(i); ... }

I i alla fall uppgift 3 verkar man kunna spara ca 1.5 sekunder på att göra detta enligt mina tester.

För att få ännu bättre tid bör man givetvis köra C++ ;)

commented 15 November 2013

Hej!
Jag får felet: "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2.
Någon som vet vad jag gör för fel?

Teacher commented 16 November 2013

Meddelandet "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2 betyder att programmet inte matade ut något som kunde tolkas som en  "svarsgraf", alltså ett flöde. Det kan till exempel bero på att det inträffat ett särfall (exception) som programmet fångat och skrivit ut istället för att skriva ut ett flöde.

commented 16 November 2013

Fast exceptions brukar väl skrivas ut till stderr och inte stdout? Vad jag vet så ignorerar Kattis allting som kommer på stderr.

Assistant commented 18 November 2013

Det stämmer att Kattis ignorerar stderr, och att det därför är lämpligt att göra sina debug-utskrifter där (även om det har hänt en gång att väldigt frekventa debug-utskrifter gjort att ett program tagit för lång tid).

Feedback News