dinic_algorithm.go

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	to     int
	cap    int
	reverse int
}

const inf = math.MaxInt

type Dinic struct {
	graph  map[int][]Edge
	level  []int
	edgePtr []int
}

func NewDinic() *Dinic {
	return &Dinic{
		graph:  make(map[int][]Edge),
		level:  make([]int, 0),
		edgePtr: make([]int, 0),
	}
}

func (d *Dinic) addEdge(u, v, cap int) {
	edge1 := Edge{v, cap, len(d.graph[v])}
	edge2 := Edge{u, 0, len(d.graph[u])}

	d.graph[u] = append(d.graph[u], edge1)
	d.graph[v] = append(d.graph[v], edge2)
}

func (d *Dinic) bfs(s, t int) bool {
	d.level = make([]int, len(d.graph))
	queue := make([]int, 0)
	queue = append(queue, s)
	d.level[s] = 1

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for _, e := range d.graph[u] {
			if d.level[e.to] == 0 && e.cap > 0 {
				d.level[e.to] = d.level[u] + 1
				queue = append(queue, e.to)
			}
		}
	}

	return d.level[t] > 0
}

func (d *Dinic) dfs(u, t, f int) int {
	if u == t {
		return f
	}
	for i := d.edgePtr[u]; i < len(d.graph[u]); i++ {
		d.edgePtr[u] = i
		e := &d.graph[u][i]
		if d.level[e.to] == d.level[u]+1 && e.cap > 0 {
			if df := d.dfs(e.to, t, int(math.Min(float64(f), float64(e.cap)))); df > 0 {
				e.cap -= df
				d.graph[e.to][e.reverse].cap += df
				return df
			}
		}
	}
	return 0
}

func (d *Dinic) maxFlow(s, t int) int {
	maxFlow := 0
	for d.bfs(s, t) {
		d.edgePtr = make([]int, len(d.graph))
		for {
			df := d.dfs(s, t, inf)
			if df == 0 {
				break
			}
			maxFlow += df
		}
	}
	return maxFlow
}

func main() {
	d := NewDinic()

	// Add edges and capacities to the flow network
	d.addEdge(0, 1, 10)
	d.addEdge(0, 2, 5)
	d.addEdge(1, 2, 15)
	d.addEdge(1, 3, 10)
	d.addEdge(2, 3, 10)

	source := 0
	sink := 3
	maxFlow := d.maxFlow(source, sink)
	fmt.Printf("Maximum Flow from %d to %d: %d\n", source, sink, maxFlow)
}