Tratei Dijkstra, agora vamos de max-flow. Basicamente esse artigo vai ser uma adaptação do artigo anterior, mas para o problema de max-flow. Então, para não me repetir, vai lá ler sobre o algoritmo de Dijkstra e o porquê de eu achar que ele não é difícil!

Esse artigo lida um pouco com a questão do max-flow e depois entra fortemente no processo de aprendizado e erro de utilizar go para implementar os algoritmos necessários.

O problema do fluxo de caminho único

Temos um ponto com uma fonte e um ponto que é o sorvedouro. Preciso do caminho que me dê o maior fluxo possível entre esses dois pontos.

Diferente de problemas de distância, o que interessa nas arestas são suas capacidades. Uma analogia a isso seria tubulação, que tem um fluxo máximo nele. Eu não posso exceder a capacidade de fluxo das minhas arestas, isso seria desastroso (afinal, é a capacidade da aresta, ela não suporta mais do que isso).

Um exemplo: eu tenho um grafo com 4 vértices, $A$ , $B$ , $C$ e $D$ . As capacidades das arestas são:

$\begin{array}{lcl} \overline{AB} & = & 7\\ \overrightarrow{BC} & = & 5\\ \overrightarrow{AC} & = & 2\\ \overrightarrow{BD} & = & 4\\ \overrightarrow{CD} & = & 7\\ \end{array}$

O caminho de maior fluxo $\overrightarrow{AC}$ é o que passa pelo caminho $A,B,C$ e consegue ter um valor máximo de 5 (de $\overrightarrow{AB}$ é 7, já de $\overrightarrow{BC}$ é 5). Se fosse o fluxo em $\overrightarrow{AD}$ , o caminho seria $A, B, C, D$ , adicionndo a aresta $\overrightarrow{CD}$ (que tem capacidadem 7) ao caminho $A, B, C$ , com fluxo máximo de 5 (aresta $\overline{BC}$ ).

Utilizando go

Nessa seção teremos as aventuras e desventuras de alguém aprendendo Go. Basicamente tudo aqui é focado na linguagem em si. Se isso não é de seu interesse, pode pular para a próxima seção.

Bootstrapping do projeto

Por motivos, resolvi usar Go lang para esse exercício. Para começar, separar bem a função de busca de outros aspectos, criei o arquivo main.go:

package main

import "fmt"

func main() {
	fmt.Print("olá, mundo\n")
}

E para executar:

$ go run main.go

Note que o pacote para executar precisa ser o main. Se tentar passar outro pacote o go chama essa mensagem de erro:

$ go run maxflow/busca.go
package command-line-arguments is not a main package

Então, começou a necessidade de mexer com algo separado. Quis fazer em um pacote bonitinho. Criei o arquivo busca.go, nomeei o pacote de maxflow:

.
├── main.go
└── maxflow
    └── busca.go

Ok, vamos criar uma função que retorne uma bobeirinha. Começar com uma função em branco:

package maxflow

func busca() {

}

Daqui coloquei o retorno "abc". Imediatamente o compilador reclamou, e eu percebi que foi porque estava faltando o tipo do retorno. Vamos botar para retornar string:

package maxflow

func busca() string {
	return "abc"
}

E me deparei com este warning:

busca não é utilizada

Agora, sabe o porquê disso? Pois bem, elementos (removendo os mais básicos como string e int) públicos precisam ter a primeira letra maiúscula. Eu deveria ter exposto a função:

package maxflow

func Busca() string {
	return "abc"
}

Ok, hora de importar o módulo maxflow no meu arquivo main.go. Primeira tentativa:

package main

import (
	"fmt"

	"maxflow"
)

func main() {
	fmt.Println(maxflow.Busca())
	fmt.Print("olá, mundo\n")
}

Mas ele diz o seguinte:

go/main.go:6:2: package maxflow is not in std

Ao tentar fazer importação a partir de caminho relativo:

package main

import (
	"fmt"

	"./maxflow"
)

func main() {
	fmt.Println(maxflow.Busca())
	fmt.Print("olá, mundo\n")
}

go/main.go:6:2: “./maxflow” is relative, but relative import paths are not supported in module mode

Bem, aparentemente agora eu tenho duas opções (mantendo a estrutura de diretórios):

usar módulos
indicar pro go que não estou usando módulo

Resolvi usar módulos.

$ go mod init computaria/graphs

Isso criou o arquivo go.mod desse jeito:

module computaria/graphs

go 1.22.1

E a estrutura de arquivos ficou assim:

.
├── go.mod
├── main.go
└── maxflow
    └── busca.go

Então, como estou usando o módulo computaria/graphs, ajustei o import de main.go:

package main

import (
	"fmt"

	"computaria/graphs/maxflow"
)

func main() {
	fmt.Println(maxflow.Busca())
	fmt.Print("olá, mundo\n")
}

E tudo funcionou!!!

$ go run main.go
abc
olá, mundo

Estruturas e interfaces e casts

Ok, estou satisfeito. Vamos fazer o algoritmo de busca? Por hora sem peso. Eu preciso criar a estrutura de dados que irá receber os próximos vértices. Para focar no aprendizado de Go em si.

Por uma questão simples de conveniência, a função de busca vai receber uma função que devolve os vizinhos de um nó. Por hora, enquanto evoluímos, vamos retornar apenas os índices do vizinho. Resgatando aqui a busca geral:

def busca(origem, destino):
    estrutura_dados = EstruturaDados()
    estrutura_dados.push((origem, 0))
    jah_visitados = set()

    while not estrutura_dados.empty():
        sendo_visitado, distancia = estrutura_dados.pop()
        if sendo_visitado == destino:
            return distancia
        if not sendo_visitado in jah_visitados:
            jah_visitados.add(sendo_visitado)

            for v,d in sendo_visitado.vizinhos():
                if not v in jah_visitados:
                    estrutura_dados.push((v, distancia + d))
    return None

Vamos pegar essa ideia e implementar aos poucos. Primeiro, passando a função como argumento. Fica assim a declaração da função:

func Busca(origem int, destino int, vizinho func (int) []int) int

Como seria isso em go? Bem, vamos supor que eu tenha um tipo que satisfaz a seguinte interface:

type SearchDataType interface {
	Push(int)
	Pop() int
	Vazia() bool
}

Com isso eu consigo começar o esboço da função:

func Busca(origem int, destino int, vizinho func(int) []int) int {
	estruturaDados := /* detalhes */
	estruturaDados.Push(origem)

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado)
	}
	return -1
}

Ok, vamos implementar uma estratégia para essa estrutura de dados. Minha primeira parada foi na declaração de variável. Eu quero que ela seja do tipo adequado. Para isso, para não depender do tipo recebido na hora da atribuição, usei um construto que o go entende como sendo “declaração old way”:

var estruturaDados sdt.SearchDataType

Nessa sintaxe, estou dizendo que ali haverá uma variável, ela se chamará estruturaDado e é do tipo sdt.SearchDataType. De onde vem esse sdt. antes do nome do tipo? Bem, vem da importação. Em go, você pode importar um pacote e usar ele no namespace do pacote ou nomear para outro conforme você queira:

import (
	sdt "computaria/graphs/maxflow/searchdatatype"
	"fmt"
)

Aqui, as coisas do pacote fmt estão disponíveis dentro do pacote de mesmo nome, como fmt.Println. Já as coisas do pacote computaria/graphs/maxflow/searchdatatype estão disponíveis localmente no namespace sdt. Se não tivesse sido nomeado, estaria disponível sob searchdatatype:

import (
	"computaria/graphs/maxflow/searchdatatype"
	"fmt"
)

Essa importação especificando o namespace é algo parecido com o import nomeado do python:

import pandas as pd

Ok. Declarar a variável tipada explicitamente vai me ajudar a detectar onde estou falhando no código. Bem, vamos fazer uma estrutura de dados para a busca em profundidade? Inserir no final e remover do final.

E vamos fazer com que essa coisa que criamos seja compatível com a interface!

Para adicionar “métodos” em objetos (sem que tais métodos façam parte do objeto como atributos), go permite isso indicando no começo da função de qual tipo ela pertence.

Para ilustrar, criei aqui uma struct só para refletir isso, ela tem um valor inteiro interno a ela. Também tem um método para somar 7 a esse valor e retornar (sem efeitos colaterais):

type marmota struct {
	x int
}

func (m marmota) mais_sete() int {
	return m.x + 7
}

func teste() {
	m := marmota{3}
	fmt.Printf("x %d, x + 7 %d\n", m.x, m.mais_sete())
}

Pois bem, e para atender uma interface? Basta que o tipo de manuseio tenha os métodos suficientes para aquela interface! Por exemplo, interface somase_sete! Refazendo o código com uma pequena mudança: garantir que a variávek interna ao método teste seja do tipo somase_sete, não uma variável de tipo inferido:

type marmota struct {
	x int
}

type somase_sete interface {
	mais_sete() int
}

func (m marmota) mais_sete() int {
	return m.x + 7
}

func teste() {
	var m somase_sete = marmota{3}
	fmt.Printf("x %d, x + 7 %d\n", m.x, m.mais_sete())
}

Até agora tranquilo. O objeto do tipo marmota é compatível com a interface somase_sete. Mas e se eu tiver um método chamado inc()? Ele precisa incrementar o valor internao. Ou seja, gera efeito colateral.

Fazer o seguinte já tá erro de compilação, pois o tipo marmota deixa de ser compatível com interface:

type somase_sete interface {
	mais_sete() int
	inc()
}

Pois bem, definamos o valor de inc() para o tipo marmota:

func (m marmota) inc() {
	m.x += 1
}

A compilação deixa de quberar, em compensação já recebo um warning no VSCode:

ineffective assignment to field marmota.x

Mas, por que disso? Bem, porque estamos usando variáveis como valores, não como referências. Então, precisamos mudar para inc() ser em cima de (m *marmota):

func (m *marmota) inc() {
	m.x += 1
}

Mas agora quebrou a compilação porque o método inc() não está em marmota, mas sim em *marmota. Então que tal transformar m em uma variável do tipo ponteiro? Pois bem, uma maneira que encontrei foi criar a variável estaticamente e pedir o endereço dela:

func teste() {
	x := marmota{3}
	var m somase_sete = &x
	fmt.Printf("x + 7 %d\n", m.mais_sete())
	x.inc()
	fmt.Printf("x + 7 %d\n", m.mais_sete())
}

O compilador aceitou e imprimiu os resultados corretos para o cenário (10 e 11). isso signifca que o tipo *marmota é compatível com a interface somase_sete.

Posso simplificar mais essa declaração. Pelo que andei lendo em go, se você deixar escapar a referência de um objeto, então go entende que esse objeto não é de escopo local e vai alocar ele fora da stack. Então isso aqui não me geraria custos:

func teste() {
	x := marmota{3}
	var m somase_sete = &x
	fmt.Printf("x + 7 %d\n", m.mais_sete())
	x.inc()
	fmt.Printf("x + 7 %d\n", m.mais_sete())
}

Go dá seus pulos para permitir magias interessantes com ponteiros. Por exemplo, se é desejável retornar o endereço da variável, o Go entende que aquele objeto é uma estrutura digna de heap, não da stack. Então o Go vai fazer a magia pra você se focar no que importa. Por exemplo retornar o objeto recém criado:

func marmotaNova(v int) somase_sete {
	return &marmota{v}
}

func teste() {
	x := marmota{3}
	var m somase_sete = marmotaNova(3)
	fmt.Printf("x + 7 %d\n", m.mais_sete())
	x.inc()
	fmt.Printf("x + 7 %d\n", m.mais_sete())
}

Também podemos fazer instanciação direta também. Mas sem a variável intermediária de tipo marmota não conseguimos chamar a função (*marmota) inc(). Podemos fazer um cast para isso:

func Teste() {
	var m somase_sete = &marmota{3}
	// var m somase_sete = &marmota{3}
	fmt.Printf("x + 7 %d\n", m.mais_sete())
	m.(*marmota).inc()
	fmt.Printf("x + 7 %d\n", m.mais_sete())
}

Outra alternativa com cast:

func marmotaNova(v int) somase_sete {
	return &marmota{v}
}

func teste() {
	m := marmotaNova(3)
	fmt.Printf("x + 7 %d\n", m.mais_sete())
	m.(*marmota).inc()
	fmt.Printf("x + 7 %d\n", m.mais_sete())
}

Terminando a iteração central

Retomando aqui o modo geral de uma busca que começou a ser desenhado:

func Busca(origem int, destino int, vizinho func(int) []int) int {
	estruturaDados := /* detalhes */
	estruturaDados.Push(origem)

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado)
	}
	return -1
}

Bem, mantendo ainda o tipo escondido atrás de detalhes, vamos preenchendo com outras informações. Ali em vizinho eu obtenho os nós a partir do identificador do nó atual, porém para o problema em questão (o fluxo máximo de caminho único) eu preciso também da capacidade da aresta. Então, preciso alterar um pouquinho a coisa:

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) int {
	estruturaDados := /* detalhes */
	estruturaDados.Push(origem)

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado)
	}
	return -1
}

Só que para a estrutura de dados também preciso de algo semelhante a aresta. No caso, vou armazenar pontos de armazenamento com id e peso:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) int {
	estruturaDados := /* detalhes */
	estruturaDados.Push(NodoArmazenamento{ Id: origem, Peso: 0})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
	}
	return -1
}

Bem, estou acumulando dados em um float64, não em um int, então preciso adequar o retorno:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	estruturaDados.Push(NodoArmazenamento{ Id: origem, Peso: 0})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
	}
	return -1
}

Ok, mas como a questão é max-flow, ao ir de um caminho com capacidade x e passar por uma aresta com capacidade y, a capacidade resultante é min(x, y). Começar com 0 ali então significa não conseguir passar com nada. Eu poderia começar com infinito positivo, mas não sei codificar isso em go. Outra alterativa seria começar com a capacidade máxima entre todos os vizinhos do vértice de origem:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for /* iteração mágica sobre `vizinhosLocais` com a representando a aresta */ {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
	}
	return -1
}

A iteração em cima de um array ou slice em go se dá através do range. No caso, podemos usar o range de alguns modos diferentes. Pra começar, tal qual em python:

for i in range(3):
	print(i)

for i := range 3 {
	fmt.Println(i)
}

Ou então pedindo para ele listar os elementos de um array/slice:

arestas := [2]Aresta{{Destino: 0, Peso: 1}, {Destino: 1, Peso: 2}}
for i, a := range arestas {
	fmt.Printf("i %d, (%d, %f)\n", i, a.Destino, a.Peso)
}

O único catch aqui é que range sobre arrays/slices retorna na primeira posição o índice, e na segunda posição retorna o elemento em si. Se quiser ignorar o índice:

arestas := [2]Aresta{{Destino: 0, Peso: 1}, {Destino: 1, Peso: 2}}
for _, a := range arestas {
	fmt.Printf("(%d, %f)\n", a.Destino, a.Peso)
}

Se quiser ignorar o elemento:

arestas := [2]Aresta{{Destino: 0, Peso: 1}, {Destino: 1, Peso: 2}}
for i := range arestas {
	a := arestas[i]
	fmt.Printf("(%d, %f)\n", a.Destino, a.Peso)
}

Ou então:

arestas := [2]Aresta{{Destino: 0, Peso: 1}, {Destino: 1, Peso: 2}}
for i, _ := range arestas {
	a := arestas[i]
	fmt.Printf("(%d, %f)\n", a.Destino, a.Peso)
}

Nota de edição: foi bem chato fazer aparecer corretamente o código acima, pois ele continha dois { seguidos e o erro que o Jekyll apontava não era claro o suficiente. Ele mencionava o problema de uma tag Liquid não fechada corretamente, o que realmente era o problema, mas por algum motivo encrencou em uma linha arbitrária. Eu cheguei a remover completamente a linha que ele apitava mas mesmo assim não obtive sucesso. Só depois que eu percebi que estava faltando tratativa de {% raw %} em um lugar mais a frente.

Mas o primeiro jeito funciona e é mais simples. range também funciona em cima de map, onde no lado esquerdo fica a chave e do lado direito o valor.

Posso pegar um slice do array:

arestas := [4]maxflow.Aresta{{Destino: 0, Peso: 1}, {Destino: 1, Peso: 2}, {Destino: 0, Peso: 3}, {Destino: 1, Peso: 4}}
for i, a := range arestas[1:3] {
	fmt.Printf("%d (%d, %f)\n", i, a.Destino, a.Peso)
}

Isso imprime:

0 (1, 2.000000)
1 (0, 3.000000)

Posso deixar os qualquer parte do intervalo aberta, seja a esquerda (range arestas[:3]):

0 (0, 1.000000)
1 (1, 2.000000)
2 (0, 3.000000)

seja a direita (range arestas[1:]):

0 (1, 2.000000)
1 (0, 3.000000)
2 (1, 4.000000)

Assim sendo, a iteração mágica pode ser resolvida correndo sobre os elementos do slice:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
	}
	return -1
}

Ok, agora preciso garantir o que tem dentro da iteração de uma busca genérica. Nesse caso, vamos começar pelo caso base: achei o meu destino, retorno o peso atual:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
	}
	return -1
}

Até o momento, tudo tranquilo. O próximo passo é verificar se já passou pelo elemento. Por uma questão de simplicidade, que tal fazer um slice booleano marcando os elementos já visitados?

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	jahVisitados := make([]bool, origem + 1)

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
		if jahVisitados[sendoVisitado.Id] {
			continue
		}
		jahVisitados[sendoVisitado.Id] = true
	}
	return -1
}

Isso dá certo, porém tem um problema: e se algum elemento intermediário tiver Id maior do que o jahVisitados consegue suportar? Bem, aqui eu adiciono uma função para garantir o bom funcionamento disso, a garanteTamanho. Ela basicamente recebe o vetor original, o id que eu quero garantir que seja armazenado e devolve um vetor que tenho no mínimo a capacidade de armazenar até o id passado, garantindo que caso seja necessário fazer uma expansão do alice até acomodar o id passado que todos os elementos sejam false.

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	// ...
}

A primeira coisa a perceber é que, para acessar o elemento 2, preciso alocar no mínimo 3 casas, pois indexa-se a partir do zero:

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	// ...
}

Para garantir no caso inicial, tratemos o nil, garantindo que todos os valores sejam false:

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	if jahVisitados == nil {
		r := make([]bool, tamanhoDesejadoMinimo)
		for i := range tamanhoDesejadoMinimo {
			r[i] = false
		}
		return r
	}
	// ...
}

O próximo passo é o caso em que não precisa fazer expansão:

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	if jahVisitados == nil {
		r := make([]bool, tamanhoDesejadoMinimo)
		for i := range tamanhoDesejadoMinimo {
			r[i] = false
		}
		return r
	}
	tamanhoAtual := len(jahVisitados)
	if tamanhoAtual >= tamanhoDesejadoMinimo {
		return jahVisitados
	}
	// ...
}

Ok, agora o final… colocar uma ruma de append no final. Eu poderia por em laço algo assim:

for /* condições malucas */ {
	jahVisitados = append(jahVisitados, false)
}

Mas isso não me pareceu adequadamente bom. Bem, e se eu pudesse concatenar dois vetores? Aí eu poderia simplesmente povoar um vetor com valores false e concatenar ao atual:

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	if jahVisitados == nil {
		r := make([]bool, tamanhoDesejadoMinimo)
		for i := range tamanhoDesejadoMinimo {
			r[i] = false
		}
		return r
	}
	tamanhoAtual := len(jahVisitados)
	if tamanhoAtual >= tamanhoDesejadoMinimo {
		return jahVisitados
	}
	delta := tamanhoDesejadoMinimo - tamanhoAtual
	r := make([]bool, delta)
	for i := range delta {
		r[i] = false
	}
	// retorno concatenando
}

Pois bem, append aceita elementos (no plural) do tipo adequado como argumento variádico. Para tal, precisa desestruturar o slice usando o ...r spread operator:

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	if jahVisitados == nil {
		r := make([]bool, tamanhoDesejadoMinimo)
		for i := range tamanhoDesejadoMinimo {
			r[i] = false
		}
		return r
	}
	tamanhoAtual := len(jahVisitados)
	if tamanhoAtual >= tamanhoDesejadoMinimo {
		return jahVisitados
	}
	delta := tamanhoDesejadoMinimo - tamanhoAtual
	r := make([]bool, delta)
	for i := range delta {
		r[i] = false
	}
	return append(jahVisitados, r...)
}

Nota: apesar de parecer que r devesse ser um vetor, go não deixa eu criar r como um vetor, porque eu desejo que o tamanho seja delta, e para go o vetor precisa ter um tamanho constante não negativo. Como delta não é uma constante, então o compilador rejeita. Não consigo fazer r := [delta]bool.

Com o garanteTamanho em mãos:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	jahVisitados := make([]bool, origem + 1)

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
		jahVisitados = garanteTamanho(jahVisitados, sendoVisitado.Id)
		if jahVisitados[sendoVisitado.Id] {
			continue
		}
		jahVisitados[sendoVisitado.Id] = true
	}
	return -1
}

Ok, agora preciso garantir que vou passear pelos vizinhos para depois tomar alguma decisão:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	jahVisitados := make([]bool, origem + 1)

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
		jahVisitados = garanteTamanho(jahVisitados, sendoVisitado.Id)
		if jahVisitados[sendoVisitado.Id] {
			continue
		}
		jahVisitados[sendoVisitado.Id] = true

		for _, aresta := range vizinho(sendoVisitado.Id) {
		}
	}
	return -1
}

No caso, a decisão é enxertar na estrutura de dados o fluxo máximo atual seguindo aquela aresta específica:

// em breve essa struct vai sair daqui
type NodoArmazenamento struct {
	Id   int
	Peso float64
}

type Aresta struct {
	Destino int
	Peso    float64
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	jahVisitados := make([]bool, origem + 1)

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		visitado := estruturaDados.Pop()
		fmt.Printf("elemento visitado? %d\n", visitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
		jahVisitados = garanteTamanho(jahVisitados, sendoVisitado.Id)
		if jahVisitados[sendoVisitado.Id] {
			continue
		}
		jahVisitados[sendoVisitado.Id] = true

		for _, aresta := range vizinho(sendoVisitado.Id) {
			d := aresta.Destino
			p := aresta.Peso
			estruturaDados.Push(NodoArmazenado{Id: d, Peso: min(p, sendoVisitado.Peso)})
		}
	}
	return -1
}

E pronto, só falta a estrutura de dados. Vamos só organizar um pouquinho a casa? Vamos jogar os detalhes da estrutura de dados em um subpacote chamado searchdatatype, no caso vamos definir logo a interface que vai ser usada dentro de um arquivo muito criativamente chamado de interface.go:

package searchdatatype

type NodoArmazenado struct {
	Id   int
	Peso float64
}

type SearchDataType interface {
	Push(NodoArmazenado)
	Pop() NodoArmazenado
	Vazia() bool
}

A estrutura do projeto ficou:

.
├── go.mod
├── main.go
└── maxflow
    ├── busca.go
    └── searchdatatype
        └── interface.go

E o conteúdo de busca.go por hora está:

package maxflow

import (
	"computaria/graphs/maxflow/searchdatatype"
)

type Aresta struct {
	Destino int
	Peso    float64
}

func garanteTamanho(jahVisitados []bool, idDesejadoMinimo int) []bool {
	tamanhoDesejadoMinimo := idDesejadoMinimo + 1
	if jahVisitados == nil {
		r := make([]bool, tamanhoDesejadoMinimo)
		for i := range tamanhoDesejadoMinimo {
			r[i] = false
		}
		return r
	}
	tamanhoAtual := len(jahVisitados)
	if tamanhoAtual >= tamanhoDesejadoMinimo {
		return jahVisitados
	}
	delta := tamanhoDesejadoMinimo - tamanhoAtual
	r := make([]bool, delta)
	for i := range delta {
		r[i] = false
	}
	return append(jahVisitados, r...)
}

func Busca(origem int, destino int, vizinho func(int) []Aresta) float64 {
	estruturaDados := /* detalhes */
	jahVisitados := make([]bool, max(origem, destino)+1)

	vizinhosLocais := vizinho(origem)
	maxLocal := vizinhosLocais[0].Peso
	for _, a := range vizinhosLocais {
		if a.Peso > maxLocal {
			maxLocal = a.Peso
		}
	}

	estruturaDados.Push(searchdatatype.NodoArmazenado{Id: origem, Peso: maxLocal})

	for !estruturaDados.Vazia() {
		sendoVisitado := estruturaDados.Pop()
		fmt.Printf("elemento sendo visitado? %d\n", sendoVisitado.Id)
		if sendoVisitado.Id == destino {
			return sendoVisitado.Peso
		}
		jahVisitados = garanteTamanho(jahVisitados, sendoVisitado.Id)
		if jahVisitados[sendoVisitado.Id] {
			continue
		}
		jahVisitados[sendoVisitado.Id] = true

		for _, aresta := range vizinho(sendoVisitado.Id) {
			d := aresta.Destino
			p := aresta.Peso
			estruturaDados.Push(searchdatatype.NodoArmazenado{Id: d, Peso: min(p, sendoVisitado.Peso)})
		}
	}
	return -1
}

Estrutura para grafo

Seguindo claramente a estrutura feita para representar grafo no post sobre Dijkstra. Eu tenho um grafo que claramente não expõe nada para o mundo externo:

type Grafo struct {
	pesos [][]Aresta
}

Para criar o grafo, exponho o seguinte:

func CriaGrafo(vertices int) *Grafo {
	g := Grafo{make([][]Aresta, vertices)}

	for i := range vertices {
		g.pesos[i] = make([]Aresta, 0)
	}
	return &g
}

Então, para resgatar valores:

func (g *Grafo) AdicionaAresta(origem int, destino int, peso float64) {
	g.pesos[origem] = append(g.pesos[origem], Aresta{destino, peso})
}

func (g *Grafo) AdicionaArestaBi(a int, b int, peso float64) {
	g.AdicionaAresta(a, b, peso)
	g.AdicionaAresta(b, a, peso)
}

func (g *Grafo) Vizinhos(a int) []Aresta {
	return g.pesos[a]
}

Eu poderia ser neurótico com cópia para evitar escrita indevida ao resgatar os Vizinhos:

func (g *Grafo) Vizinhos(a int) []Aresta {
	v := g.pesos[a]
	copia := make([]Aresta, len(v))

	for i, a := range v {
		copia[i] = a
	}
	return copia
}

Mas aí recebo o seguinte warning:

should use copy(to, from) instead of a loop (S1001)

Então, adequando o código:

func (g *Grafo) Vizinhos(a int) []Aresta {
	v := g.pesos[a]
	copia := make([]Aresta, len(v))
	copy(copia, v)
	return copia
}

A main e um pouco de HOF

Vou pegar um grafo muito similar a o que foi usado de exemplo no post sobre Dijkstra. Aqui, a main vai ser montar o grafo e chamar o algoritmo de busca do maxflow:

package main

import (
	"computaria/graphs/maxflow"
	"fmt"
)

func main() {
	g := maxflow.CriaGrafo(5)
	g.AdicionaArestaBi(0, 1, 2.0)
	g.AdicionaArestaBi(0, 2, 4.0)
	g.AdicionaArestaBi(0, 3, 7.0)
	g.AdicionaArestaBi(1, 2, 1.0)
	g.AdicionaArestaBi(1, 3, 7.0)

	g.AdicionaArestaBi(2, 3, 2.0)
	g.AdicionaArestaBi(2, 4, 10.0)
	g.AdicionaArestaBi(3, 4, 2.0)

	fmt.Println(maxflow.Busca(1, 2, g.Vizinhos))
}

Note como está sendo passada a função para resgatar as arestas vizinhas de um vértice: g.Vizinhos. No final, é o equivalente disso:

fmt.Println(maxflow.Busca(1, 2, func (id int) []maxflow.Aresta { return g.Vizinhos(id) }))

Porém mais direto ao assunto.

Experimentando um pouquinho mais no assunto, resolvi testar como seria para fazer currying com go. Criei o seguinte código válido:

nTimes := func(n int) func(int) int {
	return func(x int) int {
		return n * x
	}
}
dobra := func(x int) int {
	return 2 * x
}
triplica := nTimes(3)

sextupica := func(x int) int {
	return dobra(triplica(x))
}

fmt.Println(sextupica(6)) // 36
fmt.Println(nTimes(6)(7)) // 42

Note que a resolução de funções que retornam funções é algo bem direto ao ponto: nTimes(6)(7). Note também como ficou engraçada a função que retorna uma função:

func(n int) func(int) int {
	/* ... */
}

Eu poderia fazer uma função que receba uma função e crie uma nova função, decorando o resultado somando 1 a ele:

inc := func(base func(int) int) func(int) int {
	return func(x int) int {
		return base(x) + 1
	}
}
fmt.Println(inc(dobra)(6)) // 13

Eu posso simplificar a escrita desse tipo de função usando tipos explícitos. Por exemplo, posso dizer que funções que mapeiam de um inteiro para um outro inteiro sejam chamadas pelo tipo i2i:

type i2i func(int) int

var dobrar i2i
dobrar = func(a int) int {
	return a * 2
}

nTimes := func(n int) i2i {
	return func(x int) int {
		return n * x
	}
}

inc := func(base i2i) i2i {
	return func (x int) int {
		return base(x) + 1
	}
}

fmt.Println(inc(nTimes(3))(2)) // 7

Estrutura de dados básica: pilha

Antes de obter o valor máximo, que tal uma busca simples que traz o flow de um caminho? Basicamente vamos precisar de um mecanismo para colocar os elementos em uma pilha e buscar dela (busca em profundidade).

Eu preciso expor algo da interface SearchDataType, portanto o elemento que vou retornar preciso alterar ele no futuro. Então, para atender a interface, vou devolver o ponteiro da pilha.

Por uma questão de simplicidade, vou fazer uma pilha simples que apenas cresce, com uma espécie de ponteiro para indicar onde está o topo da pilha dentro de um slice. Para isso, a estrutura basta ter esses dois dados:

type Pilha struct {
	interno []NodoArmazenado
	topo    int
}

Para saber se a pilha está vazia, basta procurar pelo topo dela, se é 0:

func (p *Pilha) Vazia() bool {
	return p.topo == 0
}

Bem, se isso é o vazio, criar uma pilha é ter um slice de tamanho arbitrário (pode ser 0) e o topo na posição 0:

func CriaPilha() SearchDataType {
	return &Pilha{make([]NodoArmazenado, 0), 0}
}

Para buscar um elemento do topo, o caso padrão é pegar o último elemento do slice e reduzir em 1 o topo:

func (p *Pilha) Pop() NodoArmazenado {
	p.topo -= 1
	r := p.interno[p.topo]
	return r
}

Porém, para evitar maiores problemas, posso retornar um valor inválido/placeholder:

func (p *Pilha) Pop() NodoArmazenado {
	if p.topo == 0 {
		return NodoArmazenado{Id: -1, Peso: -1}
	}
	p.topo -= 1
	r := p.interno[p.topo]
	return r
}

Para fazer a pilha crescer, vamos primeiro imaginar o caso em que o slice vai ter espaço o suficiente para poder armazenar o objeto. Então, basta inserir na posição do topo o novo elemento, e incrementar o campo topo:

func (p *Pilha) Push(v NodoArmazenado) {
	ogTopo := p.topo
	p.topo += 1
	p.interno[ogTopo] = v
}

Mas, como faz para detectar se tá no tamanho limite? Basicamente se o topo for igual ao tamanho do slice:

func (p *Pilha) Push(v NodoArmazenado) {
	ogTopo := p.topo
	p.topo += 1

	if ogTopo == len(p.interno) {
		// faz algo
	}
	p.interno[ogTopo] = v
}

Nessa situação de limite, basta fazer um append com o novo valor:

func (p *Pilha) Push(v NodoArmazenado) {
	ogTopo := p.topo
	p.topo += 1

	if ogTopo == len(p.interno) {
		p.interno = append(p.interno, v)
		return
	}
	p.interno[ogTopo] = v
}

E com isso conseguimos fazer uma busca em profundidade no grafo.

Resolvendo o problema do maxflow com a estrutura adequada

Agora, vamos fazer a estrutura que retorna o elemento com máxima prioridade? Não vou fazer nada fancy aqui, como heap nem nada. Então só vou mudar a questão de como dá o resgate do próximo elemento. Logo, Vazio e Push são idênticos:

type PriorityMax struct {
	interno []NodoArmazenado
	topo    int
}

func CriaPriority() SearchDataType {
	return &PriorityMax{make([]NodoArmazenado, 0), 0}
}

func (p *PriorityMax) Vazia() bool {
	return p.topo == 0
}

func (p *PriorityMax) Push(v NodoArmazenado) {
	ogTopo := p.topo
	p.topo += 1

	if ogTopo == len(p.interno) {
		p.interno = append(p.interno, v)
		return
	}
	p.interno[ogTopo] = v
}

Para pegar o máximo, usei a seguinte estratégia:

peguei o último elemento e separei ele e o índice
itera por todos os elementos
se achar algum elemento maior, separa esse elemento e seu índice
se ao final da iteração o índice for difernete do primeiro reservado
(o do último elemento), escreve o último elemento nessa posição
decrementa o tamanho total da lista
retorna o valor reservado

func (p *PriorityMax) Pop() NodoArmazenado {
	if p.topo == 0 {
		return NodoArmazenado{Id: -1, Peso: -1}
	}

	maxPriority, maxPriorityIndex := p.interno[p.topo-1], p.topo-1

	last := maxPriority
	p.topo -= 1
	for i, node := range p.interno[:p.topo] {
		if node.Peso > maxPriority.Peso {
			maxPriority = node
			maxPriorityIndex = i
		}
	}
	if maxPriorityIndex < p.topo {
		p.interno[maxPriorityIndex] = last
	}
	return maxPriority
}

A estrutura final ficou assim:

.
├── go.mod
├── main.go
└── maxflow
    ├── busca.go
    ├── grafo.go
    └── searchdatatype
        ├── interface.go
        ├── pilha.go
        └── priority.go

Você pode conferir no repositório.

Algoritmos gulosos e busca estilo Dijkstra

Dijkstra e a variação que fizemos aqui são exemplos de algoritmos gulosos. No caso, além de gulosos, eles também são ótimos. Mas, por que isso?

Bem, eles são algoritmos de busca, que trabalham em cima de um caminho. Ou seja, o que o algoritmo disse para chegar em $P = \overrightarrow{A...B}$ é ótimo, então se tiver um caminho no futuro que parta de $A$ e passe por $B$ , necessariamente para ser ótimo o subcaminho encontrado pelo algoritmo será $P$ , seguido de alguns elementos a mais.

Uma característica essencial para esses algoritmos funcionarem é que $w(P) \leq w(P\cdot C)$ , sendo $w$ a função de peso que queremos otimizar (menor é melhor). Outra coisa importante é que $w(P'\cdot \overrightarrow{BC}) - w(P\cdot \overrightarrow{BC}) = w(P'\cdot B) - w(P\cdot B)$ , ou seja, o peso que tem de adicionar um vértice ao caminho só depende do último vértice do caminho, não depende da trajetória até então.

Como temos aqui que aumentar um passo necessariamente vai fazer o resultado ficar pior, o que acontece com o caminho $P\cdot \overrightarrow{BC}$ contra o caminho $P\cdot \overrightarrow{XC}$ ?

Vamos supor que o melhor caminho apontado seja $P\cdot \overrightarrow{XC}$ , porém o caminho $P\cdot X$ sendo não ótimo. Se esse caminho é não ótimo, enão existe um outro caminho $P' \neq P$ tal que $w(P'\cdot X) \lt w(P\cdot X)$ . Se isso é verdade, então adicionar um elemento elemento novo essa diferença deveria se manter: $w(P'\cdot \overrightarrow{XC}) \lt w(P\cdot \overrightarrow{XC})$ . Então, com isso podemos demonstrar que $P\cdot \overrightarrow{XC}$ não é o caminho ótimo. Se tem um caminho ótimo que chega em $C$ , necessariamente todos os passos dele serão ótimos.

Mas mesmo assim, sendo $P\cdot B$ ótimo, será que $P\cdot \overrightarrow{BC}$ é também o ótimo? Bem, na real não, mas pra isso precisa investigar. Por isso que na busca sempre se pega o elemento com menor peso até então, pois isso garante que até aquele momento aquele elemento é o ótimo, e se no caso for $B$ , sabemos apenas que o melhor caminho para $B$ é aquele. Então, a partir de $B$ , todos os elementos próximos dele serão adicionados na fila de prioridade do algoritmo de busca. Até terminar de adicionar todos os elementos à fila de prioridade, não podemos ter certeza de qual será o próximo elemento a ser sacado, mas depois de visitar o ponto $B$ , o próximo saque válido será o melhor até aquele momento.