' Juhász Tibor-Kiss Zsolt: Programozási ismeretek haladóknak
' (Műszaki Kiadó, 2012)

' A 40. lecke 5. gyakorlatának javított megoldása (Form1.vb)

' Ford-Fulkerson algoritmus, szélességi bejárással
' A forrás az 1. csúcs, a nyelő a legnagyobb sorszámú csúcs

Public Class Form1
    Dim Hálózat As THálózat
    Dim N As Integer ' a csúcsok száma

    ' A végrehajtási időt csökkentjük, ha lehetőleg minden változót modulszinten deklarálunk
    Dim Folyam(,) As Integer
    Dim Kezd, Vég, Csúcs, Előző, Min, Maradék, Sum As Integer
    Dim Temp As String
    Dim S As Queue(Of Integer)
    Dim H As HashSet(Of Integer)
    Dim Út() As Integer

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim ElérésiÚt As String
        Label1.Text = ""
        S = New Queue(Of Integer)
        H = New HashSet(Of Integer)

        ElérésiÚt = TextBox1.Text
        Hálózat.Beolvas(ElérésiÚt)
        N = Hálózat.CsúcsSzám
        ReDim Út(N)
        ReDim Folyam(N, N)

        Kezd = 1
        Vég = N

        Label1.Text &= "Javítóutak:" & vbNewLine
        FordFulkerson()

        MegoldásKiírása()

    End Sub

    Sub FordFulkerson()
        Array.Clear(Folyam, 0, Folyam.Length) ' a tömb összes elemének törlése

        Do While VanJavítóÚt(Kezd, Vég, Út)

            ' legkisebb maradék kapacitás meghatározása a javítóúton
            Csúcs = Vég
            Min = Integer.MaxValue
            Do While Csúcs <> Kezd
                Előző = Út(Csúcs)
                Maradék = Hálózat.Súly(Előző, Csúcs) - Folyam(Előző, Csúcs)
                If Maradék < Min Then
                    Min = Maradék
                End If
                Csúcs = Előző
            Loop

            ' folyamnövelés
            Csúcs = Vég
            Do While Csúcs <> Kezd
                Előző = Út(Csúcs)
                Folyam(Előző, Csúcs) += Min
                Folyam(Csúcs, Előző) = -Folyam(Előző, Csúcs)
                Csúcs = Előző
            Loop

            JavítóútKiírása() ' csak a teszteléshez kell

        Loop
    End Sub

    Function VanJavítóÚt(ByVal Kezd As Integer, ByVal Vég As Integer, ByRef Út() As Integer) As Boolean
        ' Szélességi útkeresés a Kezd és a Vég között
        ' kiegészítve az SGráf.Súly(Csúcs, I) > Folyam(Csúcs, I) feltétellel
        ' Az Út paramétert módosítja!!!
        Dim Csúcs, I As Integer
        H.Clear()
        S.Clear()
        Csúcs = Kezd
        S.Enqueue(Csúcs)
        H.Add(Csúcs)
        Út(Csúcs) = Csúcs
        Do While S.Count > 0 And Not H.Contains(Vég)
            ' ismétlés, amíg meg nem érkezünk a végpontba
            Csúcs = S.Dequeue
            For I = 1 To N ' nem használjuk a SzomszédCsúcs függvényt (így gyorsabb)
                If (Hálózat.Súly(Csúcs, I) > 0 OrElse Hálózat.Súly(I, Csúcs) > 0) AndAlso Not H.Contains(I) AndAlso Hálózat.Súly(Csúcs, I) > Folyam(Csúcs, I) Then
                    S.Enqueue(I)
                    H.Add(I)
                    Út(I) = Csúcs ' feljegyezzük, hogy honnan érkeztünk a Szomszéd pontba
                End If
            Next
        Loop
        If H.Contains(Vég) Then
            VanJavítóÚt = True
        Else
            VanJavítóÚt = False
        End If
    End Function

    Sub JavítóútKiírása()
        Temp = ""
        Csúcs = Vég
        Do While Csúcs <> Kezd
            Temp = Csúcs & " " & Temp
            Csúcs = Út(Csúcs)
        Loop
        Temp = Kezd & " " & Temp & vbNewLine
        Label1.Text &= Temp
    End Sub

    Sub MegoldásKiírása()

        ' Folyamnagyság
        Label1.Text &= vbNewLine & "Folyamnagyság: " & vbNewLine
        Label1.Text &= "   kifutó: "
        Sum = 0
        For I = 1 To N
            Sum += Folyam(1, I)
        Next
        Label1.Text &= Sum & vbNewLine
        Label1.Text &= "   befutó: "
        Sum = 0
        For I = 1 To N
            Sum += Folyam(N, I)
        Next
        Label1.Text &= -Sum & vbNewLine

        ' Folyamértékek
        Label1.Text &= vbNewLine & "Folyamértékek:" & vbNewLine
        For I = 1 To N
            For J = 1 To N
                If Folyam(I, J) > 0 Then
                    Label1.Text &= String.Format("{0} -> {1}: {2}", I, J, Folyam(I, J)) & vbNewLine
                End If
            Next
        Next

        ' Megmaradási szabály ellenőrzése
        Label1.Text &= vbNewLine & "Megmaradási szabály ellenőrzése:" & vbNewLine
        Temp = ""
        For I = 2 To N - 1
            Sum = 0
            For J = 1 To N
                Sum += Folyam(I, J)
            Next
            If Sum <> 0 Then
                Temp &= I & " "
            End If
        Next
        If Temp = "" Then
            Label1.Text &= "  minden csúcsban érvényes"
        Else
            Label1.Text &= "  megsérül a következő csúcsokban: " & Temp
        End If
    End Sub
End Class