Opened 9 months ago
Closed 9 months ago
#15810 closed defect (fixed)
Immutable directed graphs should know that they are directed
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  graph theory  Keywords:  immutable directed graph 
Cc:  ncohen  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Simon King 
Report Upstream:  N/A  Work issues:  
Branch:  d6ca86c (Commits)  Commit:  d6ca86c1d6984bc7a468b80905ddec01323cc9b6 
Dependencies:  #15623  Stopgaps: 
Description
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) <ipythoninput191dc52c5fb57c> in <module>() > 1 I.is_directed_acyclic() /home/king/Sage/git/sage/local/lib/python2.7/sitepackages/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/sitepackages/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.
Change History (43)
comment:1 Changed 9 months ago by SimonKing
comment:2 Changed 9 months ago by SimonKing
PS: In that case, Q.show() barks, too.
comment:3 followup: ↓ 4 Changed 9 months ago by ncohen
That's because in static_sparse_backend the binary variable for directed is self.directed instead of self._directed............
Nathann
comment:4 in reply to: ↑ 3 Changed 9 months ago by 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?).
comment:5 Changed 9 months ago by SimonKing
 Branch set to u/SimonKing/ticket/15810
 Created changed from 02/11/14 06:13:07 to 02/11/14 06:13:07
 Modified changed from 02/11/14 06:22:14 to 02/11/14 06:22:14
comment:6 Changed 9 months ago by SimonKing
 Dependencies set to #15623
comment:7 Changed 9 months ago by SimonKing
 Commit set to 1382f4f40bea6fbf32af4f0f745aa2f645a235af
 Status changed from new to needs_review
comment:8 Changed 9 months ago by SimonKing
 Status changed from needs_review to needs_work
There is more than this one type "_directed > directed" to fix.
comment:9 Changed 9 months ago by ncohen
Arg... I was uploading mine :/
Nathann
comment:10 followup: ↓ 12 Changed 9 months ago by ncohen
NOnonono it's not this one that should be changed. Give me a second.
Nathann
comment:11 followup: ↓ 14 Changed 9 months ago by SimonKing
WTF?????
When I generally replace _directed by directed for static graph backend, I get numerous errors!!
comment:12 in reply to: ↑ 10 Changed 9 months ago by SimonKing
Replying to ncohen:
NOnonono it's not this one that should be changed. Give me a second.
Nathann
Why not? It fixes it.
comment:13 followup: ↓ 15 Changed 9 months ago by SimonKing
 Status changed from needs_work to needs_review
With my branch, all tests in sage.graphs pass. So, what's the problem?
comment:14 in reply to: ↑ 11 Changed 9 months ago by 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
comment:15 in reply to: ↑ 13 ; followups: ↓ 16 ↓ 17 Changed 9 months ago by 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
comment:16 in reply to: ↑ 15 Changed 9 months ago by 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'>
comment:17 in reply to: ↑ 15 ; followup: ↓ 18 Changed 9 months ago by 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)?
comment:18 in reply to: ↑ 17 ; followup: ↓ 20 Changed 9 months ago by 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
comment:19 followup: ↓ 21 Changed 9 months ago by ncohen
sage: d = DiGraph() sage: d._backend.directed True sage: d._backend._directed True
I hate this code.
Nathann
comment:20 in reply to: ↑ 18 ; followup: ↓ 23 Changed 9 months ago by 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.
comment:21 in reply to: ↑ 19 Changed 9 months ago by SimonKing
Replying to ncohen:
sage: d = DiGraph() sage: d._backend.directed True sage: d._backend._directed TrueI hate this code.
Understandably.
Nathann
comment:22 followup: ↓ 24 Changed 9 months ago by 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.
comment:23 in reply to: ↑ 20 Changed 9 months ago by 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
comment:24 in reply to: ↑ 22 ; followup: ↓ 25 Changed 9 months ago by 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
comment:25 in reply to: ↑ 24 ; followup: ↓ 26 Changed 9 months ago by SimonKing
comment:26 in reply to: ↑ 25 Changed 9 months ago by ncohen
OK. Will your branch include #15623 (i.e., more than master)?
Well.... It will be based on develop, and include nothing else.
Nathann
comment:27 Changed 9 months ago by 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 sagegit if that's the case ?
Nathann
comment:28 followup: ↓ 29 Changed 9 months ago by 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
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 9 months ago by 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?
comment:30 in reply to: ↑ 29 Changed 9 months ago by 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
comment:31 Changed 9 months ago by SimonKing
Thank you!
Simon
comment:32 followup: ↓ 33 Changed 9 months ago by 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.
comment:33 in reply to: ↑ 32 Changed 9 months ago by 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
comment:34 Changed 9 months ago by SimonKing
king@linuxetl7:~/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@linuxetl7:~/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:
comment:35 Changed 9 months ago by SimonKing
PS: There are numerous hits for both directed and _directed in .py files, too.
comment:36 Changed 9 months ago by 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.
comment:37 Changed 9 months ago by ncohen
 Branch changed from u/SimonKing/ticket/15810 to public/15810
 Commit changed from 1382f4f40bea6fbf32af4f0f745aa2f645a235af to d6ca86c1d6984bc7a468b80905ddec01323cc9b6
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 
comment:38 Changed 9 months ago by SimonKing
Could you elaborate why you remove one line in the following chunks, rather than replace .directed by ._directed?

src/sage/graphs/digraph.py
diff git a/src/sage/graphs/digraph.py b/src/sage/graphs/digraph.py index f869bb0..d95e96e 100644
a b class DiGraph(GenericGraph): 919 919 self._weighted = weighted 920 920 self.allow_loops(loops, check=False) 921 921 self.allow_multiple_edges(multiedges, check=False) 922 self._backend.directed = True923 922 else: 924 923 raise NotImplementedError("Supported implementations: networkx, c_graph.") 925 924 
src/sage/graphs/graph.py
diff git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py index a3f1dcd..4d15305 100644
a b class Graph(GenericGraph): 1542 1542 self._weighted = weighted 1543 1543 self.allow_loops(loops, check=False) 1544 1544 self.allow_multiple_edges(multiedges, check=False) 1545 self._backend.directed = False1546 1545 else: 1547 1546 raise NotImplementedError("Supported implementations: networkx, c_graph.")
comment:39 followup: ↓ 40 Changed 9 months ago by 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
comment:40 in reply to: ↑ 39 Changed 9 months ago by 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.
comment:41 Changed 9 months ago by SimonKing
 Reviewers set to Simon King
 Status changed from needs_review to positive_review
Thank you, Nathann!
Simon
comment:42 Changed 9 months ago by ncohen
Thanks for the review :)
Nathann
comment:43 Changed 9 months ago by vbraun
 Branch changed from public/15810 to d6ca86c1d6984bc7a468b80905ddec01323cc9b6
 Resolution set to fixed
 Status changed from positive_review to closed
Variation of the theme: