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 https://github.com/veluca93/parallel_enum/issues/9#issuecomment-949761736, 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 https://github.com/veluca93/parallel_enum/blob/75bf111a4691cada9a3650fdd439b01c8db0c5f4/enumerable/clique.hpp#L32 - I believe you can keep around a copy of the inverse permutation and then apply it here https://github.com/veluca93/parallel_enum/blob/75bf111a4691cada9a3650fdd439b01c8db0c5f4/enumerable/clique.hpp#L115

[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 https://github.com/veluca93/parallel_enum/issues/9#issuecomment-950168809, 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