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: sage-6.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:

Status badges

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 Mantis

  • Branch set to u/Mantis/dominating_set_in_directed_graphs_not_correct

comment:2 Changed 6 years ago by git

  • Commit set to fe80386f9fcc211d80ae24dad472da5ec5cf1229

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

fe80386Correction of dominating_set for DiGraph

comment:3 Changed 6 years ago by Mantis

  • Status changed from new to needs_review

comment:4 Changed 6 years ago by git

  • Commit changed from fe80386f9fcc211d80ae24dad472da5ec5cf1229 to 3ff2fcfc5d6ebf92b553c5222383c2b139df64e6

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

3ff2fcfAdd doctest for the ticket

comment:5 Changed 6 years ago by dcoudert

  • 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
 # in-neighborhood 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 ncohen

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 follow-up: Changed 6 years ago by Mantis

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 ncohen

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.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.

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 git

  • Commit changed from 3ff2fcfc5d6ebf92b553c5222383c2b139df64e6 to c33efac6a6846ce26d671cfeccdb621dc2c43784

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

c33efacChange isinstance with is_directed and fix the doctest

comment:10 Changed 6 years ago by git

  • Commit changed from c33efac6a6846ce26d671cfeccdb621dc2c43784 to 7d0c749b1eb9d1b208f53c9b3a99ecaec16ee1bb

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

7d0c749Change isinstance with is_directed and fix the doctest

comment:11 Changed 6 years ago by Mantis

  • Status changed from needs_work to needs_review

comment:12 follow-up: Changed 6 years ago by ncohen

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 ; follow-up: Changed 6 years ago by Mantis

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 ; follow-up: Changed 6 years ago by ncohen

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 sage-devel to ask? Such documentation has to be written eventually.

Nathann

comment:15 in reply to: ↑ 14 Changed 6 years ago by Mantis

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 sage-devel 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 dcoudert

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 follow-up: Changed 6 years ago by Mantis

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 ncohen

  • 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 Mantis

  • 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 walk-through 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:

5e2de2dtrac #17905: Small simplification

comment:20 Changed 6 years ago by git

  • Commit changed from 5e2de2d29888559935c58a4b48db89e5c3fcba6f to c7b5c2461f16bc76ff8de8e0738d3d391c13c2aa

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

c7b5c24trac #17905: Typo

comment:21 Changed 6 years ago by ncohen

Yo guys. The typo is fixed. Is there anything else ?...

Nathann

comment:22 follow-up: Changed 6 years ago by Mantis

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 ncohen

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:24 Changed 6 years ago by Mantis

  • Status changed from needs_review to positive_review

Understood.

comment:25 Changed 6 years ago by ncohen

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 vbraun

  • Branch changed from public/17905 to c7b5c2461f16bc76ff8de8e0738d3d391c13c2aa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.