stdgraph
Triangle Counting
Hello, can I give this a go?
An implementation with the following function signature size_t triangleCount(adjacency_list)
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
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.
I went through the implementation in nwgraph and I have a fairly good understanding of it.
In graph-v2,
load_ordered_graphandload_graphare 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.
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.
@lums658https://urldefense.com/v3/__https://github.com/lums658__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX0nxCAZbg$ @pratzlhttps://urldefense.com/v3/__https://github.com/pratzl__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX2G6Uel9Q$ can answer this, I feel like it is related to the MatrixMarket loader issue #47https://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/47__;!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX2KsuEgpg$.
— Reply to this email directly, view it on GitHubhttps://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/15*issuecomment-1346927067__;Iw!!K-Hz7m0Vt54!gsrsLJM7QMyyAZk7Oy89WrogfoltwRR85OvhuEs0Q9uqEIb1PA8C4s1OOBGsOCnWBPOXt8zr2OphKX21k9q-sQ$, or unsubscribehttps://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 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. :)
There are more aspects to triangle counting that we also need functionality for. Namely, the graph needs to be sorted by degree and relabeled and triangularized. The sorting + relabeling + triangularization can make multiple orders of magnitude difference in performance for power-law / social network graphs. See: https://ieeexplore.ieee.org/document/9286220 (if you aren’t able to access the pdf at that site, let me know I can send you an author’s copy in DM). These steps are not necessarily in the algorithm per se, rather they can be considered as preprocessing. We could instead put them in the algorithm, but either way, we need the sort, relabel, triangularize functionality.
I would recommend looking at how all of these steps are realized in NWGraph. Our triangle-counting driver is here: https://github.com/pnnl/NWGraph/blob/master/bench/tc.cpp — relabeling functionality is in include/nwgraph/build.hpp , the edge list implementation is in include/nwgraph/edge_list.hpp , and the matrix market reader is in include/nwgraph/io/mmio.hpp . And the algorithm itself is in include/nwgraph/algorithms/triangle_count.hpp . There is a sequential and a parallel version in there (the algorithms are only a few lines long). There are also alternative implementations in include/nwgraph/experimental.
Regards, Andrew Lumsdaine
On Dec 13, 2022, at 1:46 PM, Pradeep Krishnamurthy @.@.>> wrote:
@lums658https://urldefense.com/v3/__https://github.com/lums658__;!!K-Hz7m0Vt54!kcZHW55sfQB1sQHPuWnAjRHV62Rr5n1ejm-i8bLFArTU5zSVnchtpJozPo4MxaLwovOAiRy60Tm0kx3ODcBvKw$ 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. :)
— Reply to this email directly, view it on GitHubhttps://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/issues/15*issuecomment-1349793435__;Iw!!K-Hz7m0Vt54!kcZHW55sfQB1sQHPuWnAjRHV62Rr5n1ejm-i8bLFArTU5zSVnchtpJozPo4MxaLwovOAiRy60Tm0kx39KNkCrQ$, or unsubscribehttps://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AGKPFDMAML2H3QOCCX6MJHDWNDVEXANCNFSM6AAAAAAROJ4IDM__;!!K-Hz7m0Vt54!kcZHW55sfQB1sQHPuWnAjRHV62Rr5n1ejm-i8bLFArTU5zSVnchtpJozPo4MxaLwovOAiRy60Tm0kx1ukl-ykQ$. You are receiving this because you were mentioned.Message ID: @.***>
It's possible to load directed or undirected. If you want to load a directed graph with edges reversed you'll need to create the reversed edges outside the graph.
Andrew has some ideas of how that should be done. I'd started doing that as an open in the function (and constructor) but then he has another idea I don't recall.
Sent from Outlookhttp://aka.ms/weboutlook From: Muhammad Osama @.> Sent: Monday, December 12, 2022 12:30 PM To: stdgraph/graph-v2 @.> Cc: Phil Ratzloff @.>; Mention @.> Subject: Re: [stdgraph/graph-v2] Triangle Counting (Issue #15)
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.
@lums658https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Flums658&data=05%7C01%7C%7Cfc8f16fe764d455c0e4a08dadc6684f0%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638064630113926189%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=tfEbnf95XSydxbJF%2BgRVMn1uNVBZ6o1j%2F4iQ9gUGGWE%3D&reserved=0 @pratzlhttps://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fpratzl&data=05%7C01%7C%7Cfc8f16fe764d455c0e4a08dadc6684f0%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638064630114082416%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=gXmjCxix8SllPxKEmHhhTf3ehmAcOVLINkCcEk6n4l4%3D&reserved=0 can answer this, I feel like it is related to the MatrixMarket loader issue #47https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fstdgraph%2Fgraph-v2%2Fissues%2F47&data=05%7C01%7C%7Cfc8f16fe764d455c0e4a08dadc6684f0%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638064630114082416%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=087NrH%2Bq1nzpHGCzogTZxtyL4G0nQ8oNnoeDxBgJVwQ%3D&reserved=0.
Reply to this email directly, view it on GitHubhttps://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fstdgraph%2Fgraph-v2%2Fissues%2F15%23issuecomment-1346927067&data=05%7C01%7C%7Cfc8f16fe764d455c0e4a08dadc6684f0%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638064630114082416%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=y17WYIsvtGe23JkcidbNJUB%2FMPBCPfJGuBGsEQUUCXk%3D&reserved=0, or unsubscribehttps://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAB7NKET6UXN7QQ44M3W7ICLWM5OKDANCNFSM6AAAAAAROJ4IDM&data=05%7C01%7C%7Cfc8f16fe764d455c0e4a08dadc6684f0%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638064630114082416%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=tm1zd8uamvkhGo8Tf%2F3zI7vWx9pbs7zR8qn6w0QeY14%3D&reserved=0. You are receiving this because you were mentioned.Message ID: @.***>
