Sist endret: 23.09.2016  
 

Praksisoppgave - Skumlehulen

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 20.11.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
skumlehulen.py, skumlehulen_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
skumlehulen.py Funksjonen antallIsolerteStier(kapasiteter, startrom utganger)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 2
input_eksempel_02.txt 2

Oppgave

I denne øvingen får du gitt en graf, et sett med startnoder, og et sett med sluttnoder. Programmet ditt skal finne ut hvor mange stier det går an å lage fra startnodene til sluttnoder uten at disse krysser. En sti fra en startnode kan gå til hvilken som helst sluttnode, men forskjellige stier kan ikke møtes i samme sluttnode. For å finne ut hvor mange stier det kan gå gjennom en graf, må du bruke maks flyt. Siden du i dette problemet har mange startnoder (sources) og mange sluttnoder (sinks), må du lage en super-source med kant til alle startnoder, og en super-sink med kant fra all sluttnodene.

To stier som er innom samme node krysser. Det vil si at du må tilordne en kapasitet til nodene. Dette kan du gjøre ved å splitte nodene. For hver node v, lager du nodene v1 og v2. Så lager du en kant fra v1 til v2. Hvis det går en kant fra u til v, lager du en kant fra u2 til v1, og hvis det går en kant fra v til w, lager du en kant fra v2 til w1. Da vil det ikke kunne gå mer enn en flyt gjennom v. Sett bort fra dette oppfører v1 og v2 seg til sammen som v gjorde i den opprinnelige grafen.

Første linje i input er antall noder, antall startnoder, og antall sluttnoder. Så kommer en linje med alle startnodene, og en linje med alle sluttnodene. Deretter kommer en nabomatrise, hvor "1" betyr at det går en kant, og "0" betyr at det ikke går en kant. Programmet ditt skal skrive ut maksimalt antall stier fra startnoder til sluttnoder uten at noen av dem møtes i noen av nodene.

Rammeverk

from sys import stdin, stderr

# Capacities is the original capacity-matrix, which contains n x n elemensts (where n is the amount of nodes)
# start_room is an array with the indexes to the nodes which corresponds to the start rooms.
# Exits is an array with the indexes to the nodes which corresponds to the exits.

def isolated_paths_count(capacities, start_rooms, exits):
    # You can use the method find_flow_path to simplify the problem
    # SKRIV DIN KODE HER

# Finds a path from the source_node to the drain_node
# with available capacity in a flow-network with flow F and capacity C.
# Returns an array where the first element is the index to omne of the start nodes,
# last element is the index to one of the exits and the elements between
# are the indexes of the nodes along the path, in the correct order.
# Example: A path from the start node 4 to node 3, node 9, node 7 and finally
# to the exit 12 will be represented as [4,3,9,7,12].


def find_flow_path(source, drain, F, C):
    n = len(F)
    discovered = [False] * n
    parent = [None] * len(F)
    queue = [source]
    while queue:
        node = queue.pop(0)
        if node == drain:
            # The drain is found, create an array of passed nodes.
            path = []
            i = node
            while True:
                path.append(i)
                if i == source:
                    break
                i = parent[i]
            path.reverse()
            return path;
        for neighbour in range(n):
            if not discovered[neighbour] and F[node][neighbour] < C[node][neighbour]:
                queue.append(neighbour);
                discovered[neighbour] = True;
                parent[neighbour] = node;
    return None

noder, _, _ = [int(x) for x in stdin.readline().split()]
start_rooms = [int(x) for x in stdin.readline().split()]
exits = [int(x) for x in stdin.readline().split()]
adjacency_matrix = []
for linje in stdin:
    naborad = [int(nabo) for nabo in linje.split()]
    adjacency_matrix.append(naborad)
print(isolated_paths_count(adjacency_matrix, start_rooms, exits))

Variabelbeskrivelse

Rammeverket i denne oppgaven gir tre variabler. 'kapasiteter' er en todimensjonal liste som representerer nabomatrisen til grafen du skal finne stier i. Tallet på posisjon [i,j] indikerer hvor stor kapasitet kanten mellom node i og j har. I denne oppgaven vil disse kun være 1 eller 0, det vil si kant eller ingen kant. For eksempelinputet vil denne matrisen være: [[0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] 'startrom' er en liste over hvilke noder som er startnoder. For eksempelinputet vil denne lista være: [0, 1] 'utganger' er en liste over hvilke noder som er sluttnoder. For eksempelinputet vil denne lista være [4,5] I tillegg gis en funksjon, 'finnFlyststi', som dere kan bruke for å finne flytforøkende stier. Denne tar følgende argumenter: kilde: Indeks til den noden som er kilde (source) i flytnettverket. sluk: Indeks til den noden som er sluk (drain) i flytnettverket. F: En matrise som indikerer flyten som går i flytnettverket. For eksempel vil verdien 2 på posisjon [i, j] si at det for øyeblikket går to flytenheter langs kanten fra i til j. C: En matrise med kapasitetene i flytnettverket. Merk at dette er total kapasitet, ikke residualkapasitet. Funksjonen returnerer en flytforøkende sti, representert som en liste med noder. Hvis en slik sti ikke finnes, returnerer den None i stedet.

Input-eksempel

6 2 2
0 1
4 5
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 0 0 0
0 0 0 0 0 0

Tilhørende output

2

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit