I am trying to use DFS to check a graph for cycles by checking each node in the graph for a cycle.

I would like to run a goroutine for each node and terminate when the first cycle is detected or when there are no cycles.

Terminating when the first cycle is detected seems fine, but I am having trouble mixing that with when there aren't anymore nodes.

Below is an implementation that seems to work, but looks janky to me and I was looking for a better implementation. I essentially use buffered channels and increment a counter every time I don't get a cycle and terminate when the counter reaches the size of the underlying graph.

Using the counter to determine when we are done seems un-idiomatic to me. Or, rather, it'd be great to know if there is a more idiomatic way to do this in Go.

func (c *cycleDet) hasCycle() bool {
    adj := c.b // adjacency list representation of the unerlying graph
    hasCycles := make(chan bool, len(adj))

    for node := range adj {
        go func(no nodeID, co chan<- bool) {
            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(no, visited) {
                co <- true
                return
            }
            co <- false
        }(node, hasCycles)
    }

    var i int
    for {
        select {
        case v := <-hasCycles:
            if v {
                fmt.Println("got cycle")
                return true
            }
            if i == len(c.b) {
                return false
            }
            i  
        }
    }
}

I've also come across another SO post that recommended using an "observer" goroutine (although I can't find the SO post). I'm not sure what that would look like but imagine it would mix with WaitGroups like this:

func (c *cycleDet) hasCycle() bool {
    hasCycle := make(chan bool)
    done := make(chan struct{})
    var wg sync.WaitGroup

    adj := c.b // adjacency list representation of the unerlying graph
    for node := range adj {
        go func(no nodeID, co chan<- bool) {
            // Use wg to synchronize termination of read-only goroutines.
            wg.Add(1)
            defer wg.Done()

            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(no, visited) {
                co <- true
                return
            }
        }(node, hasCycle)
    }

    // Observer goroutine to notify when wg is done waiting.
    time.Sleep(100 * time.Millisecond)
    go func() {
        wg.Wait()
        done <- struct{}{}
    }()

    select {
    case <-hasCycle:
        fmt.Println("got a cycle")
        return true
    case <-done:
        fmt.Println("no cycle detected")
        return false
    }
}

However this approach worries me because I need to sleep for the observer to start waiting only after the first WaitGroup counter increments, which seems far more fragile than the first solution.

CodePudding user response：

You are correct in that WaitGroup is probably what you want. However, you're not using it correctly. First, you need to call wg.Add(1) outside of the go routine that is calling wg.Done(). Second, calling wg.Wait() blocks until all the go routines in the wait group finish execution, so you don't want it to execute concurrently.

As for short-circuiting, there's not really a good way to do that. My advice would be to use a context. One thing you'll have to do in this case is to wire the context into your calls of nodeHasCycle if you want real short-circuiting behavior.

Fixing you code, we have:

func (c *cycleDet) hasCycle() bool {
    ctx, cancel := context.WithCancel(context.Background())
    hasCycle := make(chan bool)
    var wg sync.WaitGroup

    adj := c.b // adjacency list representation of the unerlying graph
    for node := range adj {
        wg.Add(1)
        go func(ctx context.Context, no nodeID, co chan<- bool, cancel context.CancelFunc) {
            // Use wg to synchronize termination of read-only goroutines.
            defer wg.Done()

            select {
                case <-ctx.Done():
                    return
                default:
            }

            visited := make(map[nodeID]struct{})
            // c.nodeHasCycle will use a recursive implementation of DFS to
            // find out if the node no leads to a cycle.
            if c.nodeHasCycle(ctx, no, visited) {
                co <- true
                cancel()
                return
            }
        }(ctx, node, hasCycle, cancel)
    }

    // Observer goroutine to notify when wg is done waiting.
    time.Sleep(100 * time.Millisecond)
    wg.Wait()
    defer cancel()

    select {
    case <-hasCycle:
        fmt.Println("got a cycle")
        return true
    default:
        fmt.Println("no cycle detected")
        return false
    }
}

With it setup this way, you can ensure that all your calls to the go-routine will operate unless a cycle is found, in which case no additional go-routes will be called and, if you add logic to check for cancellation into nodeHasSycle, then you can stop execution on any running calls to it as well.