Opened 6 years ago
Closed 6 years 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 6 years ago by
comment:2 Changed 6 years ago by
PS: In that case, Q.show()
barks, too.
comment:3 followup: ↓ 4 Changed 6 years ago by
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 6 years ago by
Replying to ncohen:
That's because in
static_sparse_backend
the binary variable for directed isself.directed
instead ofself._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 6 years ago by
 Branch set to u/SimonKing/ticket/15810
 Created changed from 02/11/14 14:13:07 to 02/11/14 14:13:07
 Modified changed from 02/11/14 14:22:14 to 02/11/14 14:22:14
comment:6 Changed 6 years ago by
 Dependencies set to #15623
comment:7 Changed 6 years ago by
 Commit set to 1382f4f40bea6fbf32af4f0f745aa2f645a235af
 Status changed from new to needs_review
comment:8 Changed 6 years ago by
 Status changed from needs_review to needs_work
There is more than this one type "_directed > directed" to fix.
comment:9 Changed 6 years ago by
Arg... I was uploading mine :/
Nathann
comment:10 followup: ↓ 12 Changed 6 years ago by
NOnonono it's not this one that should be changed. Give me a second.
Nathann
comment:11 followup: ↓ 14 Changed 6 years ago by
WTF?????
When I generally replace _directed by directed for static graph backend, I get numerous errors!!
comment:12 in reply to: ↑ 10 Changed 6 years ago by
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 6 years ago by
 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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
comment:26 in reply to: ↑ 25 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
Thank you!
Simon
comment:32 followup: ↓ 33 Changed 6 years ago by
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 6 years ago by
Is the purpose of this ticket to remove the confusion between
_directed
anddirected
? 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 6 years ago by
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 6 years ago by
PS: There are numerous hits for both directed and _directed in .py files, too.
comment:36 Changed 6 years ago by
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 6 years ago by
 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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
 Reviewers set to Simon King
 Status changed from needs_review to positive_review
Thank you, Nathann!
Simon
comment:42 Changed 6 years ago by
Thanks for the review :)
Nathann
comment:43 Changed 6 years ago by
 Branch changed from public/15810 to d6ca86c1d6984bc7a468b80905ddec01323cc9b6
 Resolution set to fixed
 Status changed from positive_review to closed
Variation of the theme: