Triangle Counting

[neoblizz]

[pradkrish]

Hello, can I give this a go?

An implementation with the following function signature size_t triangleCount(adjacency_list)

[neoblizz]

Hey, yes! If you want to take a stab at it, please go ahead. Here's a good reference on which we are basing some this work on: https://github.com/pnnl/NWGraph/blob/master/include/nwgraph/algorithms/triangle_count.hpp @pradkrish

[pradkrish]

Thanks, you can assign it to me. :)

[pradkrish]

I went through the implementation in nwgraph and I have a fairly good understanding of it.

In graph-v2, load_ordered_graph and load_graph are used for loading directed graphs but it is not very clear to me how to load undirected graphs, is it currently possible to load an undirected graph? I am asking this because triangle counting is typically used for undirected graphs.

[neoblizz]

I went through the implementation in nwgraph and I have a fairly good understanding of it.

In graph-v2, load_ordered_graph and load_graph are used for loading directed graphs but it is not very clear to me how to load undirected graphs, is it currently possible to load an undirected graph? I am asking this because triangle counting is typically used for undirected graphs.

@lums658 @pratzl can answer this, I feel like it is related to the MatrixMarket loader issue #47. I think what we really need for that is edge-doubling to allow any graph to be undirected.

[lums658]

Let’s have a quick call and talk about our triangle counting implementation and the matrix-market reader we have in NWGraph. In a recent benchmarking paper against the other leading graph frameworks, NWGraph had the best triangle counting performance — it’s our showcase in some sense. Bottom line — definitely possible to load undirected graph. We need an edge-list graph / edge-list concept to do this in the best way (and to convert to adjacency list, esp CSR). We have a set of utilities in NWGraph that we can use to do this. Sincerely, Andrew Lumsdaine On Dec 12, 2022, at 9:30 AM, Muhammad Osama ***@***.******@***.***>> wrote: I went through the implementation in nwgraph and I have a fairly good understanding of it. In graph-v2, load_ordered_graph and load_graph are used for loading directed graphs but it is not very clear to me how to load undirected graphs, is it currently possible to load an undirected graph? I am asking this because triangle counting is typically used for undirected graphs. @lums658<https://urldefense.com/v3/__https://github.com/lums658__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX0nxCAZbg$> @pratzl<https://urldefense.com/v3/__https://github.com/pratzl__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX2G6Uel9Q$> can answer this, I feel like it is related to the MatrixMarket loader issue #47<https://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/47__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX2KsuEgpg$>. — Reply to this email directly, view it on GitHub<https://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/15*issuecomment-1346927067__;Iw!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX21k9q-sQ$>, or unsubscribe<https://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AGKPFDIKFNG3SBXNQPKQR3TWM5OKDANCNFSM6AAAAAAROJ4IDM__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX02qUS-Qg$>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[lums658]

PS -- See the mmio functionality and build.hpp in NWGraph.

[pradkrish]

@lums658 Thanks for the input. I guess it makes sense to roughly break this down into the following steps with separate PR and tests for each.

• edge list concept and an I/O function to read edge list (directed and undirected) from a file
• Convert edge list graph to adjacency list graph
• triangle count implementation

do you think I get that right? Please correct me if I am wrong. :)