Täydennyspolut

Tehtäväsi on rakentaa suunnattu verkko, jonka solmut ovat 1,2,\dots,100 ja jossa kurssimateriaalin algoritmi muodostaa tasan x täydennyspolkua, kun lasketaan maksimivirtaus solmusta 1 solmuun 100.

Saat päättää itse, montako kaarta verkossa on. Jokaisen kaaren painon tulee olla positiivinen kokonaisluku. Verkossa ei saa olla kahta kaarta, joissa on sama lähtösolmu ja sama kohdesolmu. Lisäksi verkossa ei saa olla kaarta, jonka lähtösolmu ja kohdesolmu on sama.

Toteuta tiedostoon augmenting.py funktio create_edges, joka muodostaa halutunlaisen verkon. Funktion tulee palauttaa listana verkon kaaret.

Esimerkiksi lista [(1, 2, 5), (1, 3, 1)] tarkoittaisi, että verkossa on kaksi kaarta. Ensimmäinen kaari kulkee solmusta 1 solmuun 2 ja sen paino on 5. Toinen kaari kulkee solmusta 1 solmuun 3 ja sen paino on 1.

Voit muodostaa minkä tahansa verkon, jolla on halutut ominaisuudet. Funktiota testataan parametreilla 1 \le x \le 100.

# hieman muutettu versio kurssimateriaalin luokasta
class MaximumFlow:
    # ...

    def construct(self, source, sink):
        self.flow = self.graph.copy()
        total = 0
        self.path_count = 0
        while True:
            self.seen = set()
            add = self.add_flow(source, sink, float("inf"))
            if add == 0:
                break
            total += add
            self.path_count += 1
        return total

def create_edges(x):
    # TODO

if __name__ == "__main__":
    edges = create_edges(42)

    maximum_flow = MaximumFlow(range(1, 100 + 1))

    for edge in edges:
        maximum_flow.add_edge(edge[0], edge[1], edge[2])

    maximum_flow.construct(1, 100)
    print(maximum_flow.path_count) # 42