TransitiveReduction intermittently fails with "transitive reduction cannot be performed on graph with cycle"

[jeremynorris]

The following code rarely completes more that 10 iterations without failing with:

transitive reduction cannot be performed on graph with cycle

Code:

package main

import (
    "fmt"
    "os"
    "testing"

    "github.com/dominikbraun/graph"
)

func TestGraphStandard(t *testing.T) {

    for i := 1; i <= 100; i++ {

        vRoot := "_root"
        vA := "A"
        vB := "B"
        vC := "C"
        vD := "D"
        vE := "E"
        vF := "F"

        g := graph.New(graph.StringHash, graph.Directed(), graph.Acyclic())

        g.AddVertex(vRoot)
        g.AddVertex(vA)
        g.AddVertex(vB)
        g.AddVertex(vC)
        g.AddVertex(vD)
        g.AddVertex(vE)
        g.AddVertex(vF)

        g.AddEdge(vRoot, vA)
        g.AddEdge(vRoot, vB)
        g.AddEdge(vRoot, vC)
        g.AddEdge(vRoot, vD)
        g.AddEdge(vRoot, vE)
        g.AddEdge(vRoot, vF)

        g.AddEdge(vE, vC)
        g.AddEdge(vF, vD)
        g.AddEdge(vF, vC)
        g.AddEdge(vF, vE)
        g.AddEdge(vC, vA)
        g.AddEdge(vC, vB)

        _, err := graph.TransitiveReduction(g)
        if err != nil {
            fmt.Println(err.Error())
            os.Exit(1)
        }

        fmt.Printf("iteration: %d\n", i)

    }
}

eg output:

Running tool: /opt/homebrew/bin/go test -timeout 30s -run ^TestGraphStandard$ bugtesting -v

=== RUN   TestGraphStandard
iteration: 1
iteration: 2
iteration: 3
iteration: 4
iteration: 5
iteration: 6
iteration: 7
transitive reduction cannot be performed on graph with cycle
FAIL    bugtesting  1.079s

Version: v0.16.0 Go version: 1.20.1 (macOS 12.6.3 homebrew default)

[jeremynorris]

It works in v0.13.0 (and starts failing in v0.14.0).

Attached are both graph renderings above (initial and reduction) just for quick visualization.

[dominikbraun]

Thanks for reporting this! I've fixed TransitiveReduction - or, at least made your example work - and probably will rewrite the entire function in a future release. I'm not entirely sure what constellation in your graph causes the bug.

[dominikbraun]

The fix has been released in graph v0.16.1.

[jeremynorris]

Verified, thanks!