Immutable directed graphs should know that they are directed #15810

simon-king-jena · 2014-02-11T14:13:07Z

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.

Depends on #15623

CC: @nathanncohen

Component: graph theory

Keywords: immutable directed graph

Author: Nathann Cohen

Branch/Commit: d6ca86c

Reviewer: Simon King

Issue created by migration from https://trac.sagemath.org/ticket/15810

The text was updated successfully, but these errors were encountered:

simon-king-jena · 2014-02-11T14:18:12Z

comment:1

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

simon-king-jena · 2014-02-11T14:18:43Z

comment:2

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

nathanncohen · 2014-02-11T14:20:23Z

comment:3

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

Nathann

simon-king-jena · 2014-02-11T14:22:14Z

comment:4

Replying to @nathanncohen:

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

simon-king-jena · 2014-02-11T14:31:42Z

Branch: u/SimonKing/ticket/15810

simon-king-jena · 2014-02-11T14:31:44Z

Dependencies: #15623

simon-king-jena · 2014-02-11T14:32:26Z

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`

simon-king-jena · 2014-02-11T14:32:26Z

Commit: 1382f4f

simon-king-jena · 2014-02-11T14:32:26Z

Author: Simon King

simon-king-jena · 2014-02-11T14:34:29Z

comment:8

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

nathanncohen · 2014-02-11T14:35:07Z

comment:9

Arg... I was uploading mine :-/

Nathann

nathanncohen · 2014-02-11T14:35:43Z

comment:10

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

Nathann

simon-king-jena · 2014-02-11T14:36:37Z

comment:11

WTF?????

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

simon-king-jena · 2014-02-11T14:36:53Z

comment:12

Replying to @nathanncohen:

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

Nathann

Why not? It fixes it.

simon-king-jena · 2014-02-11T14:40:01Z

comment:13

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

nathanncohen · 2014-02-11T14:40:47Z

comment:14

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

nathanncohen · 2014-02-11T14:41:48Z

comment:15

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

simon-king-jena · 2014-02-11T14:43:36Z

comment:16

Replying to @nathanncohen:

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

simon-king-jena · 2014-02-11T14:44:23Z

comment:17

Replying to @nathanncohen:

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)?

nathanncohen · 2014-02-11T14:46:55Z

comment:18

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

nathanncohen · 2014-02-11T14:52:10Z

comment:24

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

simon-king-jena · 2014-02-11T14:55:07Z

comment:25

Replying to @nathanncohen:

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)?

nathanncohen · 2014-02-11T14:56:01Z

comment:26

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

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

Nathann

nathanncohen · 2014-02-11T15:02:57Z

comment:27

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

nathanncohen · 2014-02-11T15:18:50Z

comment:28

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

simon-king-jena · 2014-02-11T15:29:42Z

comment:29

Replying to @nathanncohen:

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?

nathanncohen · 2014-02-11T15:32:31Z

comment:30

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

simon-king-jena · 2014-02-11T15:35:01Z

comment:31

Thank you!

Simon

simon-king-jena · 2014-02-11T15:39:09Z

comment:32

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.

nathanncohen · 2014-02-11T15:43:21Z

comment:33

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

simon-king-jena · 2014-02-11T15:43:39Z

comment:34

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:

simon-king-jena · 2014-02-11T15:44:57Z

comment:35

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

nathanncohen · 2014-02-11T15:49:17Z

comment:36

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.

nathanncohen · 2014-02-11T15:57:49Z

comment:37

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`

nathanncohen · 2014-02-11T15:57:49Z

Changed branch from u/SimonKing/ticket/15810 to public/15810

nathanncohen · 2014-02-11T15:57:49Z

Changed commit from 1382f4f to d6ca86c

simon-king-jena · 2014-02-11T16:16:21Z

comment:38

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

diff --git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py
index f869bb0..d95e96e 100644
--- a/src/sage/graphs/digraph.py
+++ b/src/sage/graphs/digraph.py
@@ -919,7 +919,6 @@ class DiGraph(GenericGraph):
                 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.")
 
diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
index a3f1dcd..4d15305 100644
--- a/src/sage/graphs/graph.py
+++ b/src/sage/graphs/graph.py
@@ -1542,7 +1542,6 @@ class Graph(GenericGraph):
                 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.")

nathanncohen · 2014-02-11T16:20:48Z

comment:39

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

simon-king-jena · 2014-02-11T16:26:39Z

comment:40

Replying to @nathanncohen:

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.

simon-king-jena · 2014-02-11T20:00:41Z

comment:41

Thank you, Nathann!

Simon

simon-king-jena · 2014-02-11T20:00:41Z

Changed author from Simon King to Nathann Cohen

simon-king-jena · 2014-02-11T20:00:41Z

Reviewer: Simon King

nathanncohen · 2014-02-11T20:04:12Z

comment:42

Thanks for the review :-)

Nathann

vbraun · 2014-02-14T19:44:54Z

Changed branch from public/15810 to d6ca86c

* develop: (58 commits) Updated Sage version to 6.2.beta2 fix doctest error Limit the GAP command line history integrate better with Integer.is_prime Combine ECM-GMP with Baillie-PSW for prime factorization Cleaned up documentation and formatting. add doctesr Trac 15262: fix combine function trac sagemath#15810: The graph data structures may have a ._directed but no .directed ignore randomness in assertion trac sagemath#15810: Immutable directed graphs should know that they are directed Trac 15166: regression test Fix representation of RIF elements with large exponent docbuilding: suppress warnings during latex build workaround for the utf8 code points in the Sage banner Trac 15798: fix mwrank doctest for Solaris do not abbreviate 3.99999... to 3.99 with # abs tol 1e-2 setuptools: export PYTHON_EGG_CACHE and silence a warning about it Remove .hgignore files PARI: fix pow, mod and shift operators ...

simon-king-jena added this to the sage-6.2 milestone Feb 11, 2014

simon-king-jena added c: graph theory labels Feb 11, 2014

simon-king-jena added the s: needs review label Feb 11, 2014

simon-king-jena added s: needs work and removed s: needs review labels Feb 11, 2014

simon-king-jena added s: needs review and removed s: needs work labels Feb 11, 2014

simon-king-jena added s: positive review and removed s: needs review labels Feb 11, 2014

vbraun removed the s: positive review label Feb 14, 2014

vbraun closed this as completed in df445cb Feb 14, 2014

sagetrac-JStarx mannequin mentioned this issue Jan 14, 2023

Add representations of quivers and quiver algebras to sage #12630

Closed

Immutable directed graphs should know that they are directed #15810

Immutable directed graphs should know that they are directed #15810

Comments

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

simon-king-jena commented Feb 11, 2014

nathanncohen mannequin commented Feb 11, 2014

vbraun commented Feb 14, 2014