Immutable directed graphs should know that they are directed

[SimonKing]

Bug:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: Q.is_directed_acyclic()
True
sage: I = Q.copy(immutable=True)
sage: I.is_directed_acyclic()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-19-1dc52c5fb57c> in <module>()
----> 1 I.is_directed_acyclic()

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/digraph.pyc in is_directed_acyclic(self, certificate)
   1117             False
   1118         """
-> 1119         return self._backend.is_directed_acyclic(certificate = certificate)
   1120 
   1121     def to_directed(self):

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/base/c_graph.so in sage.graphs.base.c_graph.CGraphBackend.is_directed_acyclic (sage/graphs/base/c_graph.c:19314)()

ValueError: Input must be a directed graph.

[SimonKing]

Variation of the theme:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}}, immutable=True)
sage: Q.is_directed_acyclic()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-3-a8ff599a3235> in <module>()
----> 1 Q.is_directed_acyclic()

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/digraph.pyc in is_directed_acyclic(self, certificate)
   1108             False
   1109         """
-> 1110         return self._backend.is_directed_acyclic(certificate = certificate)
   1111 
   1112     def to_directed(self):

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/base/c_graph.so in sage.graphs.base.c_graph.CGraphBackend.is_directed_acyclic (sage/graphs/base/c_graph.c:19328)()

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/graphs/base/c_graph.so in sage.graphs.base.c_graph.bitset_init (sage/graphs/base/c_graph.c:3113)()

ValueError: bitset capacity must be greater than 0

[SimonKing]

PS: In that case, Q.show() barks, too.

[ncohen]

That's because in static_sparse_backend the binary variable for directed is self.directed instead of self._directed............

Nathann

[SimonKing]

Replying to ncohen:

That's because in static_sparse_backend the binary variable for directed is self.directed instead of self._directed............

So, easy to fix, then? What are the dependencies of this ticket? Actually, the error with the master branch is as in comment:1, whereas I get the error shown in the ticket description with a different branch (develop?).

[SimonKing]

New commits:

​175027d	Merge branch 'u/SimonKing/ticket/15623' of git://trac.sagemath.org/sage into ticket/15810
​1382f4f	Trac 15810: Replace ._directed by .directed for immutable graph backend

[SimonKing]

There is more than this one type "_directed --> directed" to fix.

[ncohen]

Arg... I was uploading mine :-/

Nathann

[ncohen]

NOnonono it's not this one that should be changed. Give me a second.

Nathann

[SimonKing]

WTF?????

When I generally replace _directed by directed for static graph backend, I get numerous errors!!

[SimonKing]

Replying to ncohen:

NOnonono it's not this one that should be changed. Give me a second.

Nathann

Why not? It fixes it.

[SimonKing]

With my branch, all tests in sage.graphs pass. So, what's the problem?

[ncohen]

When I generally replace _directed by directed for static graph backend, I get numerous errors!!

The file static_graph_backend also contains a CGraph class, which uses .directed and not _directed. It's just a terrible choice. It has to be ._directed for GraphBackend? and .directed for CGraph. And if you change the value used in is_directed_acyclic that's going to fail when the backend is a SparseGraph. :-/

Nathann

[ncohen]

With my branch, all tests in sage.graphs pass. So, what's the problem?

O_o

No problem with SparseGraph? backends ? Then I don't get it either.

Nathann

[SimonKing]

Replying to ncohen:

No problem with SparseGraph? backends ? Then I don't get it either.

Apparently:

sage: D = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: D.is_directed_acyclic()
True
sage: I = D.copy(immutable=True)
sage: I.is_directed_acyclic()
True
sage: D._backend
<class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>
sage: I._backend
<class 'sage.graphs.base.static_sparse_backend.StaticSparseBackend'>

[SimonKing]

Replying to ncohen:

No problem with SparseGraph? backends ? Then I don't get it either.

Did you not fix something of this kind in #15623 (which is a dependency)?

[ncohen]

Did you not fix something of this kind in #15623 (which is a dependency)?

No idea O_o

It's merged anyway, so what's the point ?

I'm trying to find out why your branch works while I thought it wouldn't.

Nathann

[ncohen]

sage: d = DiGraph()       
sage: d._backend.directed 
True
sage: d._backend._directed
True

I hate this code.

Nathann

[SimonKing]

Replying to ncohen:

It's merged anyway, so what's the point ?

I think it is in "develop", but not in "master", which is the default branching point when you create a ticket.

[SimonKing]

Replying to ncohen:

sage: d = DiGraph()       
sage: d._backend.directed 
True
sage: d._backend._directed
True

I hate this code.

Understandably.

Nathann

[SimonKing]

OK, but this seems to indicate that _backend.directed and _backend._directed are both used and are out of sync. That's bad. Perhaps this can be cleaned up in this ticket.

[ncohen]

I think it is in "develop", but not in "master", which is the default branching point when you create a ticket.

Simon, I don't want to antagonize anybody and I'm sorry enough that you have to deal with stupid errors like that in the graph code (even though these things are not my doing either), but I really believe that the develop/ branch exists for developpers to work with.

Nathann

[ncohen]

OK, but this seems to indicate that _backend.directed and _backend._directed are both used and are out of sync. That's bad. Perhaps this can be cleaned up in this ticket.

Yeah, the .directed variable is set explicitly in the DiGraph constructor. I will update my branch in a second and add a message here when it is done.

Nathann

[SimonKing]

Replying to ncohen:

Yeah, the .directed variable is set explicitly in the DiGraph constructor. I will update my branch in a second and add a message here when it is done.

OK. Will your branch include #15623 (i.e., more than master)?

[ncohen]

OK. Will your branch include #15623 (i.e., more than master)?

Well.... It will be based on develop, and include nothing else.

Nathann

[ncohen]

By the way if you use the dev scripts and if they use the master branch as a default then that's probably a bug that should be fixed. Could you write to sage-git if that's the case ?

Nathann

[ncohen]

What do you think of the current public/15810 ? It removes the ugly definition of .directed in the constructor of DiGraph. Another part of the code used this .directed once, and I converted it too. Now, Backends only have a ._directed flag, as indicated by the very first lines of GenericGraphBackend

Nathann

[SimonKing]

Replying to ncohen:

What do you think of the current public/15810

Can you remind me how to obtain that branch and how to set the default location for pushing a commit?

[ncohen]

Can you remind me how to obtain that branch and how to set the default location for pushing a commit?

git fetch trac public/15810:local_branch will fetch this branch and call it local_branch on your computer.

I do not know if it is what you ask with your second question, but git push trac local_branch:remote_branch will upload local_branch on Trac where it will be called remote_branch. remote_branch can be something like public/168543843 or u/your_trac_login/7687687.

Nathann

[SimonKing]

Thank you!

Simon

[SimonKing]

Is the purpose of this ticket to remove the confusion between _directed and directed? Then it needs work, as both is still in the code.

[ncohen]

Is the purpose of this ticket to remove the confusion between _directed and directed? Then it needs work, as both is still in the code.

Where ?

• There is a Graph._directed which cannot be renamed to .directed, for that's an internal variable
• With this ticket there is a CGraphBackend._directed, and only that.
• There is a CGraph.directed, as before.

How simple can it get ? We only store this boolean 3 times, and probably have as many functions that only return its value >_<

Nathann

[SimonKing]

king@linux-etl7:~/Sage/git/sage> grep "\._directed" -R src/sage/graphs/ | grep pyx:
src/sage/graphs/base/static_sparse_backend.pyx:        self._directed = cg.directed
src/sage/graphs/base/static_sparse_backend.pyx:        if self._directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if self._directed:
src/sage/graphs/base/sparse_graph.pyx:        self._directed = directed
src/sage/graphs/base/sparse_graph.pyx:                      self._cg, self._cg_rev, self._directed)
src/sage/graphs/base/sparse_graph.pyx:                      self._cg, self._cg_rev, self._directed)
src/sage/graphs/base/sparse_graph.pyx:                      self._cg, self._cg_rev, self._directed)
src/sage/graphs/base/sparse_graph.pyx:                      self._cg, self._cg_rev, self._directed)
src/sage/graphs/base/dense_graph.pyx:        self._directed = directed
src/sage/graphs/base/c_graph.pyx:        if self._directed:
src/sage/graphs/base/c_graph.pyx:                     (self._directed and
src/sage/graphs/base/c_graph.pyx:        if not self._directed:
src/sage/graphs/base/c_graph.pyx:        if not self._directed:
src/sage/graphs/base/c_graph.pyx:        if not self.graph._directed:
src/sage/graphs/graph_decompositions/vertex_separation.pyx:        if G._directed:

versus

king@linux-etl7:~/Sage/git/sage> grep "\.directed" -R src/sage/graphs/ | grep pyx:
src/sage/graphs/base/static_sparse_backend.pyx:        self.directed = G.is_directed()
src/sage/graphs/base/static_sparse_backend.pyx:        if self.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if not self.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if not self.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if not self.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        self._directed = cg.directed
src/sage/graphs/base/static_sparse_backend.pyx:        if not cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:            if cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:            if cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:            if cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:            if cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if cg.directed:
src/sage/graphs/base/static_sparse_backend.pyx:        if cg.directed:
src/sage/graphs/generic_graph_pyx.pyx:        self.directed = G.is_directed()
src/sage/graphs/generic_graph_pyx.pyx:        if self.directed:
src/sage/graphs/generic_graph_pyx.pyx:                    if is_admissible and self.directed:
src/sage/graphs/generic_graph_pyx.pyx:        if self.directed:

[SimonKing]

PS: There are numerous hits for both directed and _directed in .py files, too.

[ncohen]

Oh. Looks like the CGraph do not insist on having a _directed or a directed. So I can change the instances of static_sparse_backend if you like. I don't think that those of SubgraphSearch? matter to you, do they ? Those are the ones you find in generic_graph_pyx.pyx.

[ncohen]

I updated the branch with a new commit. I set it as this ticket's branch so that you can see it more easily. The only .directed that remain are those of SubgraphSearch? in generic_graph_pyx.pyx.

Nathann

---

New commits:

​e9796a1	trac #15810: Immutable directed graphs should know that they are directed
​d6ca86c	trac #15810: The graph data structures may have a ._directed but no .directed

[SimonKing]

Could you elaborate why you remove one line in the following chunks, rather than replace .directed by ._directed?

src/sage/graphs/digraph.py

@@ -919 +919 @@
                 self._weighted = weighted
                 self.allow_loops(loops, check=False)
                 self.allow_multiple_edges(multiedges, check=False)
-            self._backend.directed = True
         else:
             raise NotImplementedError("Supported implementations: networkx, c_graph.")
 

src/sage/graphs/graph.py

@@ -1542 +1542 @@
                 self._weighted = weighted
                 self.allow_loops(loops, check=False)
                 self.allow_multiple_edges(multiedges, check=False)
-            self._backend.directed = False
         else:
             raise NotImplementedError("Supported implementations: networkx, c_graph.")

[ncohen]

Because several lines above those two lines, self._backend is created using the backend's constructor, which takes the value True/False as an input.

And well, setting the value of a private variable of the backend is the backend's constructor's job. So this way, the constructors of !Graph and DiGraph do not mess with what they should not touch, the value of _directed is set only in the backend's constructor's code, and there is no fancy alias in the backend that is set where there should not be.

Nathann

[SimonKing]

Replying to ncohen:

And well, setting the value of a private variable of the backend is the backend's constructor's job. So this way, the constructors of !Graph and DiGraph do not mess with what they should not touch, the value of _directed is set only in the backend's constructor's code, and there is no fancy alias in the backend that is set where there should not be.

OK. Then, provided tests pass, it will be positive review.

[SimonKing]

Thank you, Nathann!

Simon

[ncohen]

Thanks for the review :-)

Nathann