Has anyone come across any heuristic/algorithm related to "cycle-density", defined as:Take the vertices of the cycle. Find the number of edges among them and divide by C(num_vertices, 2)[10:20 PM] Shashwat Goel: Could be maximum cycle density, sum of cycle densitites over all cycles modulo prime, etc. etc.pkman630 just landed.Last Friday at 12:11 PM[4:37 PM] Siddharth Bhat: Nice, I haven't seen "you may construct additional pylons" before. That's a cool message[4:40 PM] Siddharth Bhat: @Shashwat Goel regarding cycle density, doesn't nC2 seem like overkill? Like, you're expecting "fully connected cycles"? What's the setting? My intuition for a reasonable definition of cycle density would have been to measure how far away a graph is from chordal, so I would have taken a cycle and computed (#of cycles induced by vertices in C) / (|C| - 3)[4:41 PM] Siddharth Bhat: (I chose chordal because it's the only class of graphs I know that have extremely nice cycles, perhaps there are other classes...). I'm interested to understand what your conjecture is :D[5:49 PM] Shashwat Goel: @Siddharth Bhat Is number of induced cycles easier to calculate? Plus your formula doesn't really give an output b/w 0 and 1 by itself right?[5:50 PM] Siddharth Bhat: @Shashwat Goel oh yeah, I had a particular model in mind; I'll fix the counting, but, like, what are you trying to measure? :slight_smile:[6:04 PM] Shashwat Goel: https://www.aclweb.org/anthology/L16-1140.pdf - The paper I'm trying to build on.[6:05 PM] Shashwat Goel: They use cycle density, so I was quite sure at one point more optimized methods to compute cycle density exist, however when I began looking for literature couldn't find any.[6:05 PM] Shashwat Goel: It's quite an interesting application[6:07 PM] Shashwat Goel: And even if there are alternate ways to measure 'density' of a cycle different from the edge ratio to completeness, I found this interesting none the less. How to count fast how many chords a cycle has[6:10 PM] Shashwat Goel: Also in your formula, why |C| - 3? Why not a different denominator.[12:55 AM] Siddharth Bhat: Hm, because I was thinking of a chordal graph, where you've "triangulated" every cycle so speak, so you have |C| - 3 cycles, I think[12:55 AM] Siddharth Bhat: well, "fundamental cycle" / "generator of the cycle space"[12:57 AM] Siddharth Bhat: anyway, I don't know much any graph theory. I know of chordal indirectly since you can color it in polytime, and that's useful because register allocation 'is the same as' (in theory) graph coloring[12:59 AM] Shashwat Goel: Wait, then what is |C|[1:00 AM] Siddharth Bhat: |C| is the number of elements in the cycle?[1:00 AM] Siddharth Bhat: in a chordal graph, every cycle larger than a 3-cycle has  a smaller cycle inside it[1:00 AM] Siddharth Bhat: so your graph has essentially "triangulated" all the cycles[1:01 AM] Siddharth Bhat: like, if you take a square, and ask it to be chordal, it will force you to join the diagonal, thereby giving you 2 "small" cycles[1:01 AM] Siddharth Bhat: and the large cycle (the square) is the sum of the two cycles in cycle space[1:02 AM] Siddharth Bhat: (I really hope I'm not fucking up, anyone who actually knows graph theory plz step in)[1:07 AM] Siddharth Bhat: @Shashwat Goel does that..help?[2:08 AM] Shashwat Goel: no. of elements being no. of vertices?[2:09 AM] Shashwat Goel: or no. of triangles[2:09 AM] Shashwat Goel: ig triangles, it makes sense that way.[2:13 AM] Shashwat Goel: but then, isnt calculating no. of cycles induced cycles kind of equivalent to calculating number of edges among the cycle vertices[2:22 AM] Siddharth Bhat: mm, I think of it more as counting fundamental cycles in cycle space[2:22 AM] Siddharth Bhat: which was why the (n 2) count had me surprised[12:41 PM] Shashwat Goel: Okay, irrespective of the denominator. Any ideas on counting induced cycles/edges within the cycle nodes[11:36 PM] Siddharth Bhat: what kind of ideas are you looking for?[11:36 PM] Siddharth Bhat: I don't think I understand your question well[11:37 PM] Siddharth Bhat: ah, I see, you want an efficient algorithm[11:47 PM] Siddharth Bhat: for the thing that  I was interested in counting, I believe you can find a basis for the cycle space by computing a spanning tree. then every edge you can add into the spanning tree provides a base cycle. We will represent each base cycle as a vector in Z/2Z^E. Each edge E is given a coefficient 1 or 0. It is 1 if it occurs in the cycle, and 0 if not.Let us call the basic cycles B_i \in Z/2Z^|E|Now, from the [cycle space theory](https://en.wikipedia.org/wiki/Cycle_basis), we know that we can write any cycle in the graph as a linear combination (over Z/2Z) of the basic cycles B_i. That is, given a cycle C \in Z/2Z^|E|, we decompose it as  C = \sum_i c_i B_i. You can solve for the c_i \in Z/2Z using gaussian elimination, I guess.  Then, the number of "smaller cycles" inside your large cycle C is 2^{number of nonzero c_i}: any "smaller cycle" inside the cycle C can be made by putting together elements of the cycle basis B_i which contribute to C.Was this like what you were looking for, or did I totally miss the mark? :slight_smile: - A link: https://www.codeproject.com/Articles/1158232/Enumerating-All-Cycles-in-an-Undirected-GraphEnumerating All Cycles in an Undirected GraphFinding a fundamental Cycle Set forming a complete basis to enumerate all cycles of a given undirected graph[4:35 AM] Shashwat Goel: I like the approach/perspective a lot. However, just counting edges between cycle nodes is O(N^2) and that is enough to know the number of induced cycles I believe (2*Num_cross_edges + 1?). I believe the gaussian elimination step will be slower here?[4:36 AM] Shashwat Goel: In any case, this seems to be a nice way of counting once you iterate over all cycles. However the number of cycles can be quite large. I was wondering if there are faster ways to find the most dense cycle through some heuristic, without having to go through all the cycles.[5:08 AM] Siddharth Bhat: @Shashwat Goel I'm unconvinced that gaussian elimination will be actually slow in practice --- how large are your graphs?[5:08 AM] Siddharth Bhat: I mean, it might be fun to find the cheapest algorithm, but people have spend quite a lot of time optimising gaussian elimination. It's even cheaper over 0/1 matrices AFAIK[10:17 AM] Shashwat Goel: Having something fast inside is necessary because remember that there is an outerloop that is quite heavy which justs selects every cycle for counting. The gaussian elimination step takes something ~O(M^3) whereas as I said a 4 line edge counting takes O(N^2logM). Ofc I don't know if implementations make it work faster in practice. I can try checking that.In any case, a density formula that allows me to prune the cycles, i.e. not compute for every cycle would help cut down the outer loop which is heavier. If I have a step like gaussian elimination inside, I don't find it intuitive enough to find a heuristic to skip cycles from outside. Perhaps I would find it easier with just #no. of edges, and maybe that's just me being a noob.[10:20 AM] Shashwat Goel: Also, I'm pretty sure speed matters because it takes a noticeable amount of time on toy graphs with ~150 nodes and 500 edges right now. I have to eventually run it for upto 1e4 nodes and 5e4 edges and I wouldn't want each run to take a day[10:22 AM] Siddharth Bhat: so correct me if I am wrong, but we want to solve for coeff in Cvec = \sum_i coeff_i Bvec_i , or Cvec = coeff Bmat, where Cvec, coeff are 1xn and Bmat is nxn. So, coeff = Cvec Bmat^-1. We only need to invert Bmat once? after which it's's a matmul. But it's really not a matmul, since CVec contains entries that are {0, 1}, so it's really a gather rows of BVec and XOR the bit-vectors, which should be  N^2 in the worst case? It should be something like N^2/4 because you have vector instructions that let you perform 4-8 of the same operations in the same clock cycle, even more if you have a GPU.[10:24 AM] Siddharth Bhat: and really, it's bitwise XOR, not even add, which ought to be ~2-4x faster than the usual arithmetic stuff thanks to vector instructions?[10:29 AM] Siddharth Bhat: what am I missing? xD[10:31 AM] Shashwat Goel: Perhaps you're right. I can't say because this is the first time I'm seeing the cycle space thing :P[10:31 AM] Siddharth Bhat: ah :slight_smile: