Opened 3 years ago
Closed 22 months ago
#27424 closed enhancement (fixed)
enumeration of minimal dominating sets
Reported by:  ghjfraymond  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  graph theory  Keywords:  enumeration, dominating set 
Cc:  Merged in:  
Authors:  JeanFlorent Raymond  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  054a7bd (Commits, GitHub, GitLab)  Commit:  054a7bd1836699c2693d7beeaf3c5f9c5ca65f5b 
Dependencies:  Stopgaps: 
Description
Goal: implement an algorithm enumerating the minimal dominating sets of a graph as described in https://arxiv.org/abs/1810.00789 .
Change History (50)
comment:1 Changed 3 years ago by
 Branch set to u/ghjfraymond/enumeration_of_minimal_dominating_sets
comment:2 Changed 3 years ago by
 Commit set to a8a37b07f325e5d4a7bf7971f8367e607e51c69d
comment:3 Changed 3 years ago by
just some comments
 Please avoid that :
+from sage.all import *
 use the arxiv role for arxiv links
:arxiv:`2022.01243`
 one blank line after INPUT:
comment:4 Changed 3 years ago by
I don't think it's a good idea to define new neighbor iterators in this file.
It might be better to properly extend the functionalities of neighbors
and neighbor_iterator
.
Also, your method neighbors_of_a_set
do the same as .vertex_boundary()
, except that it returns a set instead of a list.
comment:5 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:6 Changed 3 years ago by
 Commit changed from a8a37b07f325e5d4a7bf7971f8367e607e51c69d to 822cefab865af3ae49f1956d4deb32a2c580d9a0
Branch pushed to git repo; I updated commit sha1. New commits:
a2e8bff  Minor fixes in the docstrings + moved some neighbors iterator to `generic_graph` + using `vertex_boundary` instead of `neighbors_of_a_set`

e3f50fe  Moved `is_dominating` and `is_redundant` to `generic_graph`.

26fa01f  minor changes + removed the `import all` statement

822cefa  minor doctstr changes

comment:7 Changed 3 years ago by
Thanks for the comments.
Currently I assume that the vertices of the input graph are sortable, in order for some procedure to have deterministic output, which is required for the correctness of the algorithm. The procedure removes vertices one by one in increasing order until a property is met.
Is there a fast and easy way to sort the vertices in any case, for instance using some integer used internally to represent a vertex? Otherwise I could define an arbitrary order at the beginning, but that looks cumbersome.
Or can I assume that .vertices()
always returns the vertices in the same order? (I guess not.)
comment:8 Changed 3 years ago by
comment:9 Changed 3 years ago by
method _peel
 as you mix sets and lists in the output. Use sets only
 instead of
set(G.vertices())
, useset(G)
. No need to sort here peeling = [(None, G.vertices())]
should be(None, set(G))]
, right ?while H.order() > 0:
>while H:
Some parts can be simplified like:
 for L in tree_search(H, plng, dom, i + 1):  yield L + yield from tree_search(H, plng, dom, i + 1)
I'm really not in favor of adding new vertex iterators methods. Instead, you could add parameter closed=True/False
to neighbor_iterator
and vertex_boundary
.
Now, concerning the sorting, and in view of your code, you could relabel your graph and use the mapping before returning the result. Then, you can sort integers safely if needed.
int_to_vertex = list(G) vertex_to_int = {u: i for i, u in enumerate(int_to_vertex)} G = G.relabel(perm=vertex_to_int) ... for dom in tree_search(G, peeling, set(), 0): # we generate the leaves of the search tree that are descendant of (empty set, 0) yield dom[0], {int_to_vertex[i] for i in dom[1]}
comment:10 Changed 3 years ago by
If you want to, you could add the following sanity check:
sage: findstat([(G, sum(1 for _ in minimal_dominating_sets(G))) for n in range(6) for G in graphs(n)], depth=0) # optional  internet 0: (St001302: The number of minimally dominating sets of vertices of a graph., [], 52)
or, taking a bit longer,
sage: findstat("Graphs", lambda G: sum(1 for _ in minimal_dominating_sets(G)), depth=0) # optional  internet 0: (St001302: The number of minimally dominating sets of vertices of a graph., [], 1000)
comment:11 Changed 3 years ago by
Thanks!
@dcoudert: as far as I know using yield from
would make the code non compatible with python 2. Can we assume that everybody uses python 3 now?
comment:12 Changed 3 years ago by
Right, it's working in Cython, but not in Python 2, a pity :(
comment:13 Changed 3 years ago by
 Commit changed from 822cefab865af3ae49f1956d4deb32a2c580d9a0 to 7a3a79a162c0f8cfbf8e89ed1593ce6794acd9d4
Branch pushed to git repo; I updated commit sha1. New commits:
f66030c  added a parameter 'closed' to neighbor_iterator to get rid of closed_neighborhood_iterator + fixed my own failing doctests + simplified is_dominating

b41b8e9  addressed the comments about _peel + fixed a bug I introduced in neighbor_iterator

0cfa03c  replaced calls to the function `closed_vertex_boundary` by direct calculations in order to removed the code of this function

05861f0  fixed minor bugs in my doctests or typos

7a3a79a  some polishing. The minimal_dominating_set function now returns wrong results, which I will investigate later.

comment:14 Changed 3 years ago by
May be we should make a specific ticket for the neighbor iterators. If you agree, I can do it.
comment:15 Changed 3 years ago by
Indeed, I did not think of that. Thanks for offering! Feel free to do it.
comment:16 Changed 3 years ago by
 Commit changed from 7a3a79a162c0f8cfbf8e89ed1593ce6794acd9d4 to 0b59e7895311ee6c06d325ec32621b481686e3f6
Branch pushed to git repo; I updated commit sha1. New commits:
ffbb1ad  typos

4353445  Major changes (mostly in cand_ext_enum) resulting in code that seems to work now. Positively tested on all graphs up to 8 vertices.

6d07f4c  Removed the doctest with findstat as it seems currently incompatible with py3.

f4f2513  tree_search: docstring + removed debug asserts

951ee4d  simplified peelings as some data they contained (the last cell) was not useful

8cee876  tree_seach: docstring + cut long comments

710dd5f  simplified the parameters used by cand_ext_enum

0b59e78  examples + improved doctests

comment:17 Changed 3 years ago by
 Commit changed from 0b59e7895311ee6c06d325ec32621b481686e3f6 to 41b349ef9c1b90714623c23099a920efab2a18f1
comment:18 Changed 3 years ago by
 Commit changed from 41b349ef9c1b90714623c23099a920efab2a18f1 to 7597f8835d21288c11e996c2fa032a6ea389e0ce
Branch pushed to git repo; I updated commit sha1. New commits:
7597f88  pep8

comment:19 Changed 3 years ago by
I created the ticket #27647 for the changes in neighbor_iterator.
comment:20 Changed 3 years ago by
Is the correct procedure now to merge #27647 in this branch?
comment:21 Changed 3 years ago by
yes, you should rebase your branch on top of #27647, and add it to the dependencies field
comment:22 Changed 3 years ago by
 Commit changed from 7597f8835d21288c11e996c2fa032a6ea389e0ce to 2665f39f48556168c97a8c25d6585aef89847309
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
41f91d0  tree_search: docstring + removed debug asserts

662f1e9  simplified peelings as some data they contained (the last cell) was not useful

ee4b43a  tree_seach: docstring + cut long comments

fb54bcd  simplified the parameters used by cand_ext_enum

b09036a  examples + improved doctests

740cef4  Polishing docstrings + added bibliography and examples

734af0f  implemented the suggested fix to deal with graphs whose vertices cannot be sorted

8f94cd4  pep8

90e7765  Merge branch 'u/ghjfraymond/enumeration_of_minimal_dominating_sets' of git://trac.sagemath.org/sage into t/27424/enumeration_of_minimal_dominating_sets

2665f39  docstrings and comments polish

comment:23 Changed 3 years ago by
 Dependencies set to 27647
Not sure what happened with the rebase (some commit messages have be redisplayed by trac), but it seems fine.
comment:24 Changed 3 years ago by
should be ok.
are methods private_neighbors
, is_dominating
, is_redundant
valid for graphs and digraphs ? if not, then these methods should be in graph.py
or in domination.py
.
comment:25 Changed 3 years ago by
 Commit changed from 2665f39f48556168c97a8c25d6585aef89847309 to 646c0e79bd2b1d63d6f40ae510f3a71f0d5cfa43
Branch pushed to git repo; I updated commit sha1. New commits:
646c0e7  moved domination functions to graph.py

comment:26 Changed 3 years ago by
The methods could easily be extended to digraphs but it would require to define closed neighborhoods for the _backend.iterator_out_nbrs
method (and also update my previous changes to neighbor_iterator
) or to define an out_neighbors_iterator
method in generic_graph.py
with a closed
parameter. As I do not have much time now, I just moved the functions to graph.py
.
I will now make a last pass on the code before I ask for a review.
comment:27 Changed 2 years ago by
 Commit changed from 646c0e79bd2b1d63d6f40ae510f3a71f0d5cfa43 to 09a398d5781c444a575b5d0d8d64bb1540d44bce
comment:28 Changed 2 years ago by
 Commit changed from 09a398d5781c444a575b5d0d8d64bb1540d44bce to 34b8a3e539b240b11f82cece1db3ef7bf58875e2
Branch pushed to git repo; I updated commit sha1. New commits:
34b8a3e  One more test

comment:29 Changed 2 years ago by
 Status changed from new to needs_review
comment:30 Changed 2 years ago by
 Dependencies changed from 27647 to #27647
comment:32 Changed 2 years ago by
 why adding
lazy_import("sage.graphs.domination", "minimal_dominating_sets")
insrc/sage/graphs/all.py
? I think thatminimal_dominating_sets
should be a method ofGraph
.
 a possible error that prevent to build the doc
 r''' + r"""
and of course the block ends with """
and not '''
.
 In
minimal_dominating_sets
, please document more precisely the input parameters. What's the goal ofto_dominate
?work_on_copy
?
 please revert modifications in
src/sage/graphs/generic_graph.py
. These modifications introduce trailing white spaces...
 in
is_dominating
input parameters and documented parameters are not the same. Futhermore, you should be more explicit that by default we want to dominate the vertices ofself
. For instanceCheck whether ``p_dominating`` is a dominating set of ``self``. When ``p_dominates`` is specified, check instead if ``p_dominating`` dominates the vertices in ``p_dominates``.
I'm not convince by the choice of the names
p_dominating
andp_dominates
.
 in
is_redundant
, you should definehas_private
as a set, and add itdominator[v][1]
in thefor v in focus
loop. Then, you just have to check ifhas_private != dom
.
comment:33 Changed 2 years ago by
 Commit changed from 34b8a3e539b240b11f82cece1db3ef7bf58875e2 to 8859913851952374f53afeae4e25836d1f41b187
comment:34 Changed 2 years ago by
 Commit changed from 8859913851952374f53afeae4e25836d1f41b187 to 23145b0b776d90953ed7186e32f0789148792d89
comment:35 Changed 2 years ago by
 Commit changed from 23145b0b776d90953ed7186e32f0789148792d89 to 544504d939afb64f0b3cf52ab7b0ca76b7f320c8
Branch pushed to git repo; I updated commit sha1. New commits:
544504d  removed mistakedly introduced trailing white spaces

comment:36 Changed 2 years ago by
Thanks for the comments! I addressed them all.
comment:37 Changed 2 years ago by
 Commit changed from 544504d939afb64f0b3cf52ab7b0ca76b7f320c8 to a07f8c56d99f57b261cff3affd55fbf9b5f9122a
Branch pushed to git repo; I updated commit sha1. New commits:
a07f8c5  fixed doctests after moving minimal_dominating_sets to Graph + one extra test in an auxiliary function

comment:38 Changed 2 years ago by
 Commit changed from a07f8c56d99f57b261cff3affd55fbf9b5f9122a to 900ebf0d38983cf821c93e54cb9adda0a8e71a45
Branch pushed to git repo; I updated commit sha1. New commits:
900ebf0  attempt to solve encoding problems that some patchbots have

comment:39 Changed 2 years ago by
The code has been greatly improved but I still have some comments. Sorry for that.
 We can improve the readability
 def _aux_with_rep(H, to_dom, u_next):  # Auxilliary routine.  # Return the minimal dominating sets of to_dom, with the  # assumption that u_next dominates to_som.  # WARNING: the same output may be output several times  # (up to H times).  #  # In order to later remove duplicates, we here output pairs  # (ext,i) where ext is the output candidate extension and i  # counts how many elements have already been output. + def _aux_with_rep(H, to_dom, u_next): + """ + Return the minimal dominating sets of to_dom, with the + assumption that u_next dominates to_som. + + WARNING: the same output may be output several times + (up to H times). + + In order to later remove duplicates, we here output pairs + (ext,i) where ext is the output candidate extension and i + counts how many elements have already been output. + """
 in
is_dominating
: Check if a set is a dominating set. + Check whether ``dom`` is a dominating set of ``self``.
and you can remove that sentence from the output block. Actually, the output block is not necessary, and you could just say in the description of the method that this method can be used to check whether dom
dominates a subset of vertices of the graph.
 you can simply do
 return to_dom == set() + return not to_dom
 since you assume that
focus
has no repeated verices, you should better use aset
. The testv in focus
will be faster`.
 a simpler version
 dominator = dict()  for v in focus:  dominator[v] = (0, None) # Initialization + # Initialization + dominator = {v: (0, None) for v in focus}
 I suggest the following simplification (the text can be improved)
 # Now we can compute with_private, the set of vertices of dom  # that have a private neighbor in focus  with_private = set()  for v in focus:  # Here we do care neither about vertices dominated by more  # than one vertex of dom (they are not private neighbor of  # anybody) nor about vertices not dominated by dom (idem).  if dominator[v][0] == 1:  # If v is dominated only by one vertex x,  # then v is a private neighbor of x  with_private.add(dominator[v][1]) + # We now compute the subset of vertices of dom that have a + # private neighbor in focus. A vertex v in dom has a private + # neighbor in focus if it is dominated by a unique vertex, + # that is if dominator[v][0] == 1 + with_private = {dominator[v][1] for v in focus is dominator[v][0] == 1}
 why not doing this:
 return (neighbor  for neighbor in self.neighbor_iterator(vertex, closed=True)  if neighbor not in closed_neighborhood_vs) + return set(self.neighbors(vertex, closed=True)).difference(closed_neighborhood_vs)
comment:40 Changed 2 years ago by
 Milestone changed from sage8.8 to sage8.9
Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).
comment:41 Changed 2 years ago by
There is a merge conflict with last beta.
comment:42 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:43 Changed 2 years ago by
 Milestone changed from sage8.9 to sage9.0
I can help solving the merge conflicts if needed
comment:44 Changed 2 years ago by
 Branch changed from u/ghjfraymond/enumeration_of_minimal_dominating_sets to public/graphs/27424_domination
 Commit changed from 900ebf0d38983cf821c93e54cb9adda0a8e71a45 to 4454cc06c324f027de63e0c59244688af4d37552
 Reviewers set to David Coudert
 Status changed from needs_work to needs_review
I fixed the merge conflicts, applied the modifications proposed in #comment:39, and move all methods related to domination to the file domination.py
. I pushed everything to a new branch in public so that you can modify it if needed.
Do you agree with these changes ?
New commits:
a61547c  trac #27424: fix merge conflict with 9.0.beta1

c937e57  trac #27424: review ticket

4454cc0  trac #27424: move dominating_set to domination.py

comment:45 Changed 22 months ago by
 Commit changed from 4454cc06c324f027de63e0c59244688af4d37552 to 4294f7d8c149958b222c08c45065d79e23d7bd1f
Branch pushed to git repo; I updated commit sha1. New commits:
4294f7d  minor changes in docstrings + added one example of dominating_set

comment:46 Changed 22 months ago by
 Commit changed from 4294f7d8c149958b222c08c45065d79e23d7bd1f to 054a7bd1836699c2693d7beeaf3c5f9c5ca65f5b
Branch pushed to git repo; I updated commit sha1. New commits:
054a7bd  updated copyright info for the dominating_set function

comment:47 Changed 22 months ago by
Thanks for the changes! (And sorry for the late relpy!) I agree with all of them. I made some minor changes in the docstrings.
comment:50 Changed 22 months ago by
 Branch changed from public/graphs/27424_domination to 054a7bd1836699c2693d7beeaf3c5f9c5ca65f5b
 Resolution set to fixed
 Status changed from positive_review to closed
(work in progress)