Opened 6 years ago
Closed 6 years ago
#17905 closed defect (fixed)
Dominating set in directed Graphs not correct
Reported by:  Mantis  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  graph theory  Keywords:  dominating_set, Graphs, Directed Graphs 
Cc:  Merged in:  
Authors:  Sergios Lenis  Reviewers:  David Coudert, Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  c7b5c24 (Commits, GitHub, GitLab)  Commit:  c7b5c2461f16bc76ff8de8e0738d3d391c13c2aa 
Dependencies:  Stopgaps: 
Description
It seems that the dominating_set() operation is not working correctly for the directed graphs. For example if the graph is a>b>c<d the dominating_set will give b,c which is not true.
The dominating set of a undirected graph is computed correctly.
I suppose a stopgap should be filled also.
Change History (26)
comment:1 Changed 6 years ago by
 Branch set to u/Mantis/dominating_set_in_directed_graphs_not_correct
comment:2 Changed 6 years ago by
 Commit set to fe80386f9fcc211d80ae24dad472da5ec5cf1229
comment:3 Changed 6 years ago by
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Commit changed from fe80386f9fcc211d80ae24dad472da5ec5cf1229 to 3ff2fcfc5d6ebf92b553c5222383c2b139df64e6
Branch pushed to git repo; I updated commit sha1. New commits:
3ff2fcf  Add doctest for the ticket

comment:5 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
What you propose is correct. However, I would prefer this formulation.
# For any vertex v, one of its neighbors or v itself is in # the minimum dominating set. If g is a DiGraph, we use the # inneighborhood of v instead. neighbor_iterator = g.neighbor_in_iterator if g.is_directed() else g.neighbor_iterator for v in g.vertex_iterator(): p.add_constraint(int(not total)*b[v]+p.sum([b[u] for u in neighbor_iterator(v)]), min=1)
For the doc test, you can add a reference to this ticket as follows. Also, you should add an empty line before the sage:
lines. So this could be:
The dominating set of a DiGraph is different from the dominating set of its underlying Graph (modification introduced in :trac:`17905`) :: sage: g = digraphs.Path(3) sage: len(g.dominating_set()) 2 sage: gg = Graph(g) sage: gg.is_isomorphic(graphs.PathGraph(3)) True sage: len(gg.dominating_set()) 1
David.
comment:6 Changed 6 years ago by
Hellooooooo,
To complete David's answer: the empty line after "sage:" is a requirement of sphinx, the software that is being used to turn Sage's documentation into a html page.
In order to check that your documentation is compiled properly, you should run:
sage b && sage docbuild reference/graphs html
More details there: http://www.sagemath.org/doc/developer/sage_manuals.html
It is also preferable, as he advises, to use digraphs.Path
and graphs.PathGraph
instead of building the graphs yourself :)
For that, see: http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html
Good luck,
Nathann
comment:7 followup: ↓ 8 Changed 6 years ago by
Hi,
Thank you for the help and responses. It is great that i have the feedback to learn the contribution process and the coding preferences of the project.
I will make changes in my code when I will be in my home.
I have tested my doctest with
./sage t src/sage/graphs/generic_graph.py
that I got from the http://www.sagemath.org/doc/developer/doctesting.html and I didn't have any complain but I will try yours also when I can.
Cheers Sergios
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Hello,
I will make changes in my code when I will be in my home.
Okayyyyyyyyyyy !
I have tested my doctest with
./sage t src/sage/graphs/generic_graph.pythat I got from the http://www.sagemath.org/doc/developer/doctesting.html and I didn't have any complain but I will try yours also when I can.
You did well, and the two must be run, though they have different purposes:
1) With your command, you tested that all examples of code
contained in the docstring (they usually appear after a double column, i.e. '::') return what they are expected to return. It tests the actual code that you write.
2) With the other command, you build the html documentation. This
ignores the code but only reads the doc, and tests that the ".. NOTE" environments are displayed properly, it compiles the LaTeX code that the doc can possibly contains, creates links from one function to another... Things like that.
Nathann
comment:9 Changed 6 years ago by
 Commit changed from 3ff2fcfc5d6ebf92b553c5222383c2b139df64e6 to c33efac6a6846ce26d671cfeccdb621dc2c43784
Branch pushed to git repo; I updated commit sha1. New commits:
c33efac  Change isinstance with is_directed and fix the doctest

comment:10 Changed 6 years ago by
 Commit changed from c33efac6a6846ce26d671cfeccdb621dc2c43784 to 7d0c749b1eb9d1b208f53c9b3a99ecaec16ee1bb
Branch pushed to git repo; I updated commit sha1. New commits:
7d0c749  Change isinstance with is_directed and fix the doctest

comment:11 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:12 followup: ↓ 13 Changed 6 years ago by
Hellooooooo!
Your branch looks good, and almost ready to go. I just had a look at it, and made two modifications:
1) One line of documentation was very long (we try to keep lines to max 80 characters unless it makes it harder to read: that's a Python standard) so I wrapped it around.
2) Your if/else can be written in one line
 if g.is_directed():  neighbors_iter=g.neighbor_in_iterator  else:  neighbors_iter=g.neighbor_iterator + neighbors_iter=g.neighbor_in_iterator if g.is_directed() else g.neighbor_iterator
I added a small commit on top of your branch. That new branch is named public/17905.
As I reviewed your changes and added a commit, you have to review mine before this ticket can be merged. Of course, tell me if there is anything that you do not like, and we will discuss it.
Cheers,
Nathann
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 6 years ago by
Replying to ncohen: Hello
1) One line of documentation was very long (we try to keep lines to max 80 characters unless it makes it harder to read: that's a Python standard) so I wrapped it around.
I will keep that in mind
2) Your if/else can be written in one line
It is fine with me. I am used of writing the if  else in more lines to be easier to read but if the source has that format I will use that format also.
About your commit, I didn't find how to pull your commit. Can you show me the way?
Cheers Sergios
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 6 years ago by
Hello !
About your commit, I didn't find how to pull your commit. Can you show me the way?
Well, in my case I have to run git pull trac public/17905
but if you use the 'git trac' command then I am at a loss.
You could try this, see if it works. If it does not, could you send an email to sagedevel to ask? Such documentation has to be written eventually.
Nathann
comment:15 in reply to: ↑ 14 Changed 6 years ago by
Replying to ncohen: Hi
Well, in my case I have to run
git pull trac public/17905
but if you use the 'git trac' command then I am at a loss.
Yes I was using the git trac
You could try this, see if it works. If it does not, could you send an email to sagedevel to ask? Such documentation has to be written eventually.
It works I now have your commit. But now I am lost. How I review it?
Sergios
comment:16 Changed 6 years ago by
You have to check that it is working correctly, that the doc is properly built, etc.
one space in missing between graphs and ( in:
The dominating set is calculated for both the directed and undirected graphs(modification introduced in :trac:`17905`)::
David.
comment:17 followup: ↓ 18 Changed 6 years ago by
Hello again,
That part was not the problem. What I wanted to say is now the changes are in public/17905
. I should merge with my branch and commit that to git trac? Or it's not required. That is the part I don't understand. Sorry if I'm asking alot of question's.
Sergios
comment:18 in reply to: ↑ 17 Changed 6 years ago by
 Reviewers set to David Coudert, Nathann Cohen
Hello !
That part was not the problem. What I wanted to say is now the changes are in
public/17905
. I should merge with my branch and commit that to git trac? Or it's not required. That is the part I don't understand. Sorry if I'm asking alot of question's.
Oh. Well, you can do that (merge with your branch) or you can just change the branch's name in the ticket's description. Much easier, and totally equivalent :)
Nathann
comment:19 Changed 6 years ago by
 Branch changed from u/Mantis/dominating_set_in_directed_graphs_not_correct to public/17905
 Commit changed from 7d0c749b1eb9d1b208f53c9b3a99ecaec16ee1bb to 5e2de2d29888559935c58a4b48db89e5c3fcba6f
Hello,
It seems my first walkthrough is near the end. I agree with David that a space is missing between graphs and (.
It's better like this:
The dominating set is calculated for both the directed and undirected graphs (modification introduced in :trac:`17905`)::
Sergios
New commits:
5e2de2d  trac #17905: Small simplification

comment:20 Changed 6 years ago by
 Commit changed from 5e2de2d29888559935c58a4b48db89e5c3fcba6f to c7b5c2461f16bc76ff8de8e0738d3d391c13c2aa
Branch pushed to git repo; I updated commit sha1. New commits:
c7b5c24  trac #17905: Typo

comment:21 Changed 6 years ago by
Yo guys. The typo is fixed. Is there anything else ?...
Nathann
comment:22 followup: ↓ 23 Changed 6 years ago by
Hellow Nathann From my point everything is done. Should I change the ticket? Sergios
comment:23 in reply to: ↑ 22 Changed 6 years ago by
From my point everything is done. Should I change the ticket?
Yes, if you do not see anything else that needs to be changed.
All commits must be reviewed and I added a commit to the branch, so even if it is a bit trivial somebody has to 'review' them. Even the original author can do that, and then set the ticket to positive review (given that we reviewed your changes already, and agree with them).
Nathann
comment:25 Changed 6 years ago by
Thanks !
Now that it is in positive_review
we can forget about it. In some time the release manager (Volker Braun) will come and close the ticket, and it will be available in the next release.
Nathann
comment:26 Changed 6 years ago by
 Branch changed from public/17905 to c7b5c2461f16bc76ff8de8e0738d3d391c13c2aa
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Correction of dominating_set for DiGraph