Opened 9 months ago

Last modified 4 weeks ago

#27424 needs_review enhancement

enumeration of minimal dominating sets

Reported by: gh-jfraymond Owned by:
Priority: major Milestone: sage-9.0
Component: graph theory Keywords: enumeration, dominating set
Cc: Merged in:
Authors: Jean-Florent Raymond Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: public/graphs/27424_domination (Commits) Commit: 4454cc06c324f027de63e0c59244688af4d37552
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 (44)

comment:1 Changed 9 months ago by gh-jfraymond

  • Branch set to u/gh-jfraymond/enumeration_of_minimal_dominating_sets

comment:2 Changed 9 months ago by gh-jfraymond

  • Commit set to a8a37b07f325e5d4a7bf7971f8367e607e51c69d

(work in progress)

comment:3 Changed 9 months ago by chapoton

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 9 months ago by dcoudert

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 8 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 8 months ago by git

  • Commit changed from a8a37b07f325e5d4a7bf7971f8367e607e51c69d to 822cefab865af3ae49f1956d4deb32a2c580d9a0

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

a2e8bffMinor fixes in the docstrings + moved some neighbors iterator to `generic_graph` + using `vertex_boundary` instead of `neighbors_of_a_set`
e3f50feMoved `is_dominating` and `is_redundant` to `generic_graph`.
26fa01fminor changes + removed the `import all` statement
822cefaminor doctstr changes

comment:7 Changed 8 months ago by gh-jfraymond

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 8 months ago by gh-jfraymond

  • Authors set to Jean-Florent Raymond

comment:9 Changed 8 months ago by dcoudert

method _peel

  • as you mix sets and lists in the output. Use sets only
  • instead of set(G.vertices()), use set(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 8 months ago by mantepse

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 8 months ago by gh-jfraymond

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 8 months ago by dcoudert

Right, it's working in Cython, but not in Python 2, a pity :(

comment:13 Changed 8 months ago by git

  • Commit changed from 822cefab865af3ae49f1956d4deb32a2c580d9a0 to 7a3a79a162c0f8cfbf8e89ed1593ce6794acd9d4

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

f66030cadded a parameter 'closed' to neighbor_iterator to get rid of closed_neighborhood_iterator + fixed my own failing doctests + simplified is_dominating
b41b8e9addressed the comments about _peel + fixed a bug I introduced in neighbor_iterator
0cfa03creplaced calls to the function `closed_vertex_boundary` by direct calculations in order to removed the code of this function
05861f0fixed minor bugs in my doctests or typos
7a3a79asome polishing. The minimal_dominating_set function now returns wrong results, which I will investigate later.

comment:14 Changed 7 months ago by dcoudert

May be we should make a specific ticket for the neighbor iterators. If you agree, I can do it.

comment:15 Changed 7 months ago by gh-jfraymond

Indeed, I did not think of that. Thanks for offering! Feel free to do it.

comment:16 Changed 7 months ago by git

  • Commit changed from 7a3a79a162c0f8cfbf8e89ed1593ce6794acd9d4 to 0b59e7895311ee6c06d325ec32621b481686e3f6

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

ffbb1adtypos
4353445Major changes (mostly in cand_ext_enum) resulting in code that seems to work now. Positively tested on all graphs up to 8 vertices.
6d07f4cRemoved the doctest with findstat as it seems currently incompatible with py3.
f4f2513tree_search: docstring + removed debug asserts
951ee4dsimplified peelings as some data they contained (the last cell) was not useful
8cee876tree_seach: docstring + cut long comments
710dd5fsimplified the parameters used by cand_ext_enum
0b59e78examples + improved doctests

comment:17 Changed 7 months ago by git

  • Commit changed from 0b59e7895311ee6c06d325ec32621b481686e3f6 to 41b349ef9c1b90714623c23099a920efab2a18f1

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

e4bb218Polishing docstrings + added bibliography and examples
41b349eimplemented the suggested fix to deal with graphs whose vertices cannot be sorted

comment:18 Changed 7 months ago by git

  • Commit changed from 41b349ef9c1b90714623c23099a920efab2a18f1 to 7597f8835d21288c11e996c2fa032a6ea389e0ce

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

7597f88pep8

comment:19 Changed 7 months ago by gh-jfraymond

I created the ticket #27647 for the changes in neighbor_iterator.

comment:20 Changed 7 months ago by gh-jfraymond

Is the correct procedure now to merge #27647 in this branch?

comment:21 Changed 7 months ago by dcoudert

yes, you should rebase your branch on top of #27647, and add it to the dependencies field

comment:22 Changed 7 months ago by git

  • Commit changed from 7597f8835d21288c11e996c2fa032a6ea389e0ce to 2665f39f48556168c97a8c25d6585aef89847309

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

41f91d0tree_search: docstring + removed debug asserts
662f1e9simplified peelings as some data they contained (the last cell) was not useful
ee4b43atree_seach: docstring + cut long comments
fb54bcdsimplified the parameters used by cand_ext_enum
b09036aexamples + improved doctests
740cef4Polishing docstrings + added bibliography and examples
734af0fimplemented the suggested fix to deal with graphs whose vertices cannot be sorted
8f94cd4pep8
90e7765Merge branch 'u/gh-jfraymond/enumeration_of_minimal_dominating_sets' of git://trac.sagemath.org/sage into t/27424/enumeration_of_minimal_dominating_sets
2665f39docstrings and comments polish

comment:23 Changed 7 months ago by gh-jfraymond

  • Dependencies set to 27647

Not sure what happened with the rebase (some commit messages have be re-displayed by trac), but it seems fine.

comment:24 Changed 7 months ago by dcoudert

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 7 months ago by git

  • Commit changed from 2665f39f48556168c97a8c25d6585aef89847309 to 646c0e79bd2b1d63d6f40ae510f3a71f0d5cfa43

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

646c0e7moved domination functions to graph.py

comment:26 Changed 7 months ago by gh-jfraymond

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 6 months ago by git

  • Commit changed from 646c0e79bd2b1d63d6f40ae510f3a71f0d5cfa43 to 09a398d5781c444a575b5d0d8d64bb1540d44bce

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

c5a890dSmall changes in is_dominating
09a398dSimplifying is_redundant

comment:28 Changed 6 months ago by git

  • Commit changed from 09a398d5781c444a575b5d0d8d64bb1540d44bce to 34b8a3e539b240b11f82cece1db3ef7bf58875e2

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

34b8a3eOne more test

comment:29 Changed 6 months ago by gh-jfraymond

  • Status changed from new to needs_review

comment:30 Changed 6 months ago by chapoton

  • Dependencies changed from 27647 to #27647

comment:31 Changed 6 months ago by chapoton

  • Dependencies #27647 deleted

doc does not build

comment:32 Changed 6 months ago by dcoudert

  • why adding lazy_import("sage.graphs.domination", "minimal_dominating_sets") in src/sage/graphs/all.py ? I think that minimal_dominating_sets should be a method of Graph.
  • 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 of to_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 of self. For instance
    Check 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 and p_dominates.

  • in is_redundant, you should define has_private as a set, and add it dominator[v][1] in the for v in focus loop. Then, you just have to check if has_private != dom.

comment:33 Changed 6 months ago by git

  • Commit changed from 34b8a3e539b240b11f82cece1db3ef7bf58875e2 to 8859913851952374f53afeae4e25836d1f41b187

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

7986e84apparently fixed the problem with the doc not building...
a980172manually reverted my changes in generic_graph
0971d45improved docstring of minimal_dominating_sets
8859913fixed docstring of is_dominating

comment:34 Changed 6 months ago by git

  • Commit changed from 8859913851952374f53afeae4e25836d1f41b187 to 23145b0b776d90953ed7186e32f0789148792d89

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

dc8296fdocstring polishing + variable names uniformization
235657bupdated is_redundant as suggested + minor docstring fix
7cb2fc1now minimal_dominating_set is a method of Graph
23145b0doc polish

comment:35 Changed 6 months ago by git

  • Commit changed from 23145b0b776d90953ed7186e32f0789148792d89 to 544504d939afb64f0b3cf52ab7b0ca76b7f320c8

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

544504dremoved mistakedly introduced trailing white spaces

comment:36 Changed 6 months ago by gh-jfraymond

Thanks for the comments! I addressed them all.

comment:37 Changed 6 months ago by git

  • Commit changed from 544504d939afb64f0b3cf52ab7b0ca76b7f320c8 to a07f8c56d99f57b261cff3affd55fbf9b5f9122a

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

a07f8c5fixed doctests after moving minimal_dominating_sets to Graph + one extra test in an auxiliary function

comment:38 Changed 6 months ago by git

  • Commit changed from a07f8c56d99f57b261cff3affd55fbf9b5f9122a to 900ebf0d38983cf821c93e54cb9adda0a8e71a45

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

900ebf0attempt to solve encoding problems that some patchbots have

comment:39 Changed 5 months ago by dcoudert

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 a set. The test v 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 5 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.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 4 months ago by dcoudert

There is a merge conflict with last beta.

comment:42 Changed 4 months ago by chapoton

  • Status changed from needs_review to needs_work

comment:43 Changed 6 weeks ago by dcoudert

  • Milestone changed from sage-8.9 to sage-9.0

I can help solving the merge conflicts if needed

comment:44 Changed 4 weeks ago by dcoudert

  • Branch changed from u/gh-jfraymond/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:

a61547ctrac #27424: fix merge conflict with 9.0.beta1
c937e57trac #27424: review ticket
4454cc0trac #27424: move dominating_set to domination.py
Note: See TracTickets for help on using tickets.