Finding wrong cliques (?)

[levnikmyskin]

Hi,
sorry to bother you guys again. I compiled your code and ran some tests on a toy network (you can find the .nde file and a screenshot at the end of this issue). However, I'm seeing weird outputs:

./build/text_ui -enumerator=sequential -system=clique -print test_g.nde

Output:

0 5 
5 6 7 
6 7 8 
1 2 
1 6 
2 7 8 
3 4 
3 8 
4 5 7 
Reading time: 0 ms
Setup time: 0 ms
Run time: 0 ms
Solutions found: 9
Computational tree size: 9
Solutions per ms: inf

As you can see, it says that 0-5 is a clique, but there is no edge between them. Am I doing something wrong?

test_g.nde:

9
0 3
1 4
2 2
3 3
4 5
5 4
6 4
7 1
8 2
0 1
0 4
0 8
1 2
1 4
1 5
2 3
3 4
3 6
4 5
4 6
5 6
6 7
8 5

[veluca93]

@Pronte can you confirm the NDE file is correct?

[Pronte]

Hi all, The graph seems to be ok, and I get that same output both with -system=clique and -system=d2kplex -k=1, furthermore the clique size distribution seems correct compared to the graph (4 triangles and 5 edges). My guess is the code is listing the cliques correctly, but printing an internal re-labelling of the nodes instead of the original names. Luca can you point me to where the original names are kept so that I can update the print function? Il giorno ven 22 ott 2021 alle ore 18:02 Luca Versari < ***@***.***> ha scritto:

…

@Pronte <https://github.com/Pronte> can you confirm the NDE file is correct? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#9 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AALMRDG42GL5QCVSHZZSDCTUIGDIVANCNFSM5GQ34VCQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[veluca93]

The graph is permuted here

parallel_enum/enumerable/clique.hpp

Line 32 in 75bf111

graph->Permute(DegeneracyOrder(*graph))

- I believe you can keep around a copy of the inverse permutation and then apply it here

parallel_enum/enumerable/clique.hpp

Line 115 in 75bf111

return node.first;

[levnikmyskin]

Just FYI, I edited the code as suggested and it is indeed working as expected (for k-plexes, you need to edit diam2kplex.hpp as well though).

[veluca93]

Would you be willing to make a PR for that too? :)

[Pronte]

Seconding what Luca said! Otherwise If you're willing to share your fix with me directly i can adapt it to be system independent and conditional on the print flag before updating (I'd mention you in the commit ofc)

…

On Sat, Oct 23, 2021, 17:29 Luca Versari ***@***.***> wrote: Would you be willing to make a PR for that too? :) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#9 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AALMRDGIMAU4PTFUEOBQF2LUILIGRANCNFSM5GQ34VCQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[levnikmyskin]

Opened the PR! Please check the code fits your standards, since my C++ is more than rusty