Skip to content

Add SimpleCycles function #39

@dominikbraun

Description

@dominikbraun

There should be a SimpleCycles standalone function that detects all simple cycles in a given graph.

Analogous to functions like StronglyConnectedComponents, SimpleCycles should store the hashes of the vertices that form a cycle as a []K and return all of them as a slice, so that the return type is[][]K.

Example

In the graph shown above, there are two cycles: 1-2-4 and 2-3-5. This is how SimpleCycle should look and work like:

g := graph.New(graph.IntHash)

// Add vertices and edges ...

cycles, _ := graph.SimpleCycles(g)

fmt.Println(cycles)
[[1 2 4] [2 3 5]]

The function signature should be SimpleCycles[K comparable, T any](g Graph[K, T]) ([][]K, error).

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requesthelp wantedExtra attention is needed

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions