Add call to cliquer with custom cliques sizes #29269

Fightlapa · 2020-03-02T20:23:38Z

Currently only maximum/maximal cliques can be obtained by calling cliquer functions. With this change custom cliques can be obtained with cliquer.

Component: graph theory

Keywords: cliquer

Author: Jakub Jabłoński, Jonathan Kliem

Branch/Commit: e1774f7

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/29269

The text was updated successfully, but these errors were encountered:

Fightlapa · 2020-03-02T20:31:56Z

Changed author from Fightlapa to Jakub Jabłoński

Fightlapa · 2020-03-03T19:16:18Z

Changed branch from cliquer_custom_size to public/cliquer_custom_size

sagetrac-git · 2020-03-03T19:16:37Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f085c77`	`Added new function to get induced cliques of custom size in graph`

sagetrac-git · 2020-03-03T19:16:37Z

Commit: f085c77

Fightlapa · 2020-03-03T19:18:35Z

comment:4

Code could be reused, as this is almost copy-paste of another function. But if it will be fine, will do that and push "clean" version.

dcoudert · 2020-03-03T23:45:31Z

comment:5

Welcome to Sagemath.

You could add tests of corner cases, like small graphs (empty, 1 or 2 vertices), disconnected graphs and graphs with multiple edges.

Have you tested the code on a large graph to see what it supports ?

Also, you will have to improve the coding style (see https://www.python.org/dev/peps/pep-0008/) and ensure that comments are formatted in 80 columns mode.

Fightlapa · 2020-03-05T16:05:28Z

comment:6

I'm still testing it. I see already one wrong result. I'm investigating it now.

sagetrac-git · 2020-03-05T17:06:24Z

Changed commit from f085c77 to 78d65d0

sagetrac-git · 2020-03-05T17:06:24Z

Branch pushed to git repo; I updated commit sha1. New commits:

`78d65d0`	`Fixed array size in cliquer. Added doctests`

dcoudert · 2020-03-06T08:18:47Z

comment:9

a few comments

first line of method all_cliques

+    Return the vertex sets of *ALL* the complete subgraphs.
+    Returns the vertex sets of *ALL* the complete subgraphs.

add an INPUT block with the description of input parameters
if not graph.order(): -> if not graph:
I don't understand this case if min_size == 0 and max_size > 0:. Not documented
I suggest to free the graph right after the sig_off
Could you improve the presentation of the code in cl.c and add some documentation.

I don't know if it is possible, but it would be much better if we could turn this method into an iterator. If the number of cliques to report is large, we may have a segfault. Not clear if the design of cliquer allows that.

dcoudert · 2020-03-07T10:22:25Z

comment:10

According the documentation of cliquer (https://users.aalto.fi/~pat/cliquer.html), it seems possible to avoid storing all cliques (re-entrant methods). So it seems possible to make an iterator, but I don't know how complex it is to do so.

sagetrac-git · 2020-03-07T11:17:20Z

Changed commit from 78d65d0 to f70a90d

sagetrac-git · 2020-03-07T11:17:20Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f70a90d`	`Added input description and made minor refactoring`

sagetrac-git · 2020-03-07T11:19:43Z

Changed commit from f70a90d to 60a8166

sagetrac-git · 2020-03-07T11:19:43Z

Branch pushed to git repo; I updated commit sha1. New commits:

`60a8166`	`Added missing characters in input description`

Fightlapa · 2020-03-07T11:24:01Z

comment:13

Sorry for those messy commits. Anyway, it's my first time with Cython, I'm not also that familiar with c++. I think I'm not capable of making iterator out of it.

dcoudert · 2020-03-08T13:45:30Z

comment:14

The documentation is unclear on whether you search for cliques with number of vertices or edges between min and max, or if you consider the weight of the cliques. Please clarify
if the default value of min_size is 0, it must be set if the input, that is def all_cliques(graph, min_size=0, max_size=0):
alignement (and text) of input parameters

-    - ``min_size`` -- Search for cliques with weight at least N. If N=0,
-                      searches for maximum weight clique (default).
+    - ``min_size`` -- integer (default: 0); minimum size of the cliques to report.
+      When set to 0 (default), searched for a maximum weight clique.

add doctests for the default case of the parameters
don't sorted cliques at the end
also, could change the branch name to something like public/graphs/29269_all_cliques (i.e., use in a new branch). When the branch is in public/, I can push review commit, which is usually faster for me.
concerning the iterator, for the moment you can at least make method all_cliques yield cliques instead of returning a full list. Then we will have to find a way to make method sage_find_all_clique re-entrant, and so avoid to store all cliques.

Fightlapa · 2020-03-10T11:57:21Z

Changed commit from 60a8166 to none

Fightlapa · 2020-03-10T11:57:21Z

Changed branch from public/cliquer_custom_size to public/graphs/29269_all_cliques

sagetrac-git · 2020-03-10T12:00:21Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f085c77`	`Added new function to get induced cliques of custom size in graph`
`78d65d0`	`Fixed array size in cliquer. Added doctests`
`f70a90d`	`Added input description and made minor refactoring`
`60a8166`	`Added missing characters in input description`
`d39990d`	`Changed all_cliques to iterator`

sagetrac-git · 2020-03-10T12:00:21Z

Commit: d39990d

sagetrac-git · 2020-03-10T14:59:41Z

Changed commit from d39990d to 2859b26

sagetrac-git · 2020-03-10T14:59:41Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a7559be`	`trac #: Merged with 9.1.beta7`
`2859b26`	`trac #29269: review commit`

dcoudert · 2020-03-26T12:11:05Z

Reviewer: David Coudert

dcoudert · 2020-03-26T12:11:05Z

comment:42

a small review commit to avoid using variable size uninitialized.

If OK for you, you can set this ticket to positive review on my behalf. Don't forget to add your name as co-author.

kliem · 2020-03-26T12:13:29Z

Changed author from Jakub Jabłoński to Jakub Jabłoński, Jonathan Kliem

vbraun · 2020-04-16T22:35:28Z

comment:44

The "Dependencies" field must be a list of trac tickets

kliem · 2020-04-17T05:59:38Z

Changed dependencies from cliquer to none

kliem · 2020-04-17T05:59:38Z

comment:45

Sorry, missed that. That's obsolete as cliquer is a standard package.

vbraun · 2020-04-18T08:41:44Z

comment:46

Merge conflict, please fix

dcoudert · 2020-04-18T09:55:56Z

comment:47

this might be due to #29518. So let's wait for next release to see what's the conflict.

kliem · 2020-04-25T20:43:36Z

Changed branch from public/graphs/29269_all_cliques to public/29269_reb

kliem · 2020-04-25T20:43:36Z

Changed commit from bf4e52d to none

kliem · 2020-04-25T20:44:32Z

comment:49

Replying to @dcoudert:

this might be due to #29518. So let's wait for next release to see what's the conflict.

That's exactly the problem. Doesn't make sense to add a function to a lazy import that will be removed soon. And it should be a method of a graph, this is where it belongs.

kliem · 2020-04-25T20:44:59Z

Commit: e1774f7

kliem · 2020-04-25T20:44:59Z

Changed branch from public/29269_reb to public/29269-reb

kliem · 2020-04-25T20:44:59Z

New commits:

`a3a61cb`	`Added new function to get induced cliques of custom size in graph`
`2d5c2e8`	`Fixed array size in cliquer. Added doctests`
`c0532ce`	`Added input description and made minor refactoring`
`f0f1bcc`	`Added missing characters in input description`
`029814e`	`Changed all_cliques to iterator`
`7b1e302`	`trac #29269: review commit`
`ac66919`	`Exposed all_cliques in graphs.py`
`732fbaf`	`moving deallocations to finally blocks`
`e1774f7`	`trac #29269: review commit`

dcoudert · 2020-04-26T12:56:31Z

comment:52

LGTM.

vbraun · 2020-05-02T21:57:59Z

Changed branch from public/29269-reb to e1774f7

Fightlapa mannequin added this to the sage-9.2 milestone Mar 2, 2020

Fightlapa mannequin added c: graph theory labels Mar 2, 2020

dcoudert modified the milestones: sage-9.2, sage-9.1 Mar 3, 2020

Fightlapa mannequin added the s: needs review label Mar 5, 2020

kliem added s: positive review and removed s: needs review labels Mar 26, 2020

vbraun added s: needs info and removed s: positive review labels Apr 16, 2020

kliem added s: positive review and removed s: needs info labels Apr 17, 2020

vbraun added s: needs work and removed s: positive review labels Apr 18, 2020

kliem added s: needs review and removed s: needs work labels Apr 25, 2020

dcoudert added s: positive review and removed s: needs review labels Apr 26, 2020

vbraun removed the s: positive review label May 2, 2020

vbraun closed this as completed in 1302e46 May 2, 2020

Add call to cliquer with custom cliques sizes #29269

Add call to cliquer with custom cliques sizes #29269

Comments

Fightlapa mannequin commented Mar 2, 2020

Fightlapa mannequin commented Mar 2, 2020

Fightlapa mannequin commented Mar 3, 2020

sagetrac-git mannequin commented Mar 3, 2020

sagetrac-git mannequin commented Mar 3, 2020

Fightlapa mannequin commented Mar 3, 2020

dcoudert commented Mar 3, 2020

Fightlapa mannequin commented Mar 5, 2020

sagetrac-git mannequin commented Mar 5, 2020

sagetrac-git mannequin commented Mar 5, 2020

dcoudert commented Mar 6, 2020

dcoudert commented Mar 7, 2020

sagetrac-git mannequin commented Mar 7, 2020

sagetrac-git mannequin commented Mar 7, 2020

sagetrac-git mannequin commented Mar 7, 2020

sagetrac-git mannequin commented Mar 7, 2020

Fightlapa mannequin commented Mar 7, 2020

dcoudert commented Mar 8, 2020

Fightlapa mannequin commented Mar 10, 2020

Fightlapa mannequin commented Mar 10, 2020

sagetrac-git mannequin commented Mar 10, 2020

sagetrac-git mannequin commented Mar 10, 2020

sagetrac-git mannequin commented Mar 10, 2020

sagetrac-git mannequin commented Mar 10, 2020

dcoudert commented Mar 26, 2020

dcoudert commented Mar 26, 2020

kliem commented Mar 26, 2020

vbraun commented Apr 16, 2020

kliem commented Apr 17, 2020

kliem commented Apr 17, 2020

vbraun commented Apr 18, 2020

dcoudert commented Apr 18, 2020

kliem commented Apr 25, 2020

kliem commented Apr 25, 2020

kliem commented Apr 25, 2020

kliem commented Apr 25, 2020

kliem commented Apr 25, 2020

kliem commented Apr 25, 2020

dcoudert commented Apr 26, 2020

vbraun commented May 2, 2020