Clojurians Log v2

I hope this is the right channel. Is anyone aware of an existing implementation for enumerating cycles in an undirected graph (a triangulated planar graph, to be exact) for ubergraph? I just started to port this code from JS to CLJ https://github.com/antvis/G6/blob/24c38a2af7829f04cdc42e263541d5cb54f3affe/src/algorithm/detect-cycle.ts#L89 and was wondering if anyone already has different a solution

I don't have a solution to offer; out of curiosity, what is your objective in enumerating cycles?

As for the algorithm: it occurs to me that it might be relevant to first make a block decomposition of the graph (which is more fine-grained than a connected components decomposition), as cycles only occur within blocks. Whether that's likely to help highly depends on the distribution of the possible graphs, but my intuition is that graphs that tend to have few enough cycles to be enumerated will also tend to have many small blocks.

Yes it seems that I can work my way through it by first getting all the components and detect cycles based on them. The graphs i work with in this scenario should at most have a hundred nodes for now. Im writing an algorithm to convert triangulated graphs into path digraphs

@rob703 not sure that was clear, but I recommend dividing the problem into nonseparable components, not just connected components.

I don't know what a path digraph is, but that seems cool :)

Ohh now i get it, okay I'll look into that, thank you! 🙂 Yeah, a path digraph is just a fancy digraph, built in a special way. But I'm in way over my head right now, so take everything I say with a grain of salt please 😉

Could you clarify what you mean by triangulated graphs?

Sure, my wording was a bit sloppy. I mean a triangulated planar graph such as this one: https://mathworld.wolfram.com/TriangulatedGraph.html

So I think I should refine my question: I need to find all cyles in a triangulated planar graph

or even more exact, I "walk" along my graph from left to right and remove nodes in the process, which may lead to cycles - and I need to find and "fix" those in the process

I fail to see how removing a node would add a cycle :)

But it does seem a much more tractable problem than enumarating all possible cycles

Yes it doesn't "create" a cycle per se. It's just very difficult for me to tell you exactly what I do without spilling my companies secret sauce in this case, sorry! But I think I figured it out, writing about it ordered some thoughts in my head, so thanks again! 🙂

You're welcome 🙂

Was interesting anyway

Hope it's not for creating mass destruction weapons or something

Quite the contrary! 😂

Mass reconstruction tools then ?