2 ms·
Ah yeah, if you're not trying to identify all loops but just check if some loops exist then that works. I think you can dispense with the "walking around taking
by eigenket 2y ago
Ah yeah, if you're not trying to identify all loops but just check if some loops exist then that works. I think you can dispense with the "walking around taking clockwise/anticlockwise edges" part though. If you repeatedly do the "remove all nodes with only 1 edge going to them" step then you've already identified whether or not at least one loop exists.
- vouwfietsman 2y agoRepeatedly removing those edges would help indeed! I am interested in finding the loops, but in the example provided the "dead end" edges do not contribute to the loop. Officially a loop is not allowed to contain the same vertex twice (besides start/end), otherwise any sequence of vertices could be considered a loop just by repeating them in reverse order. However, indeed it remains true that it does not find all loops, only the smallest set of loops that cover all edges.