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

Change History (43)

comment:1 Changed 9 months ago by 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

comment:2 Changed 9 months ago by SimonKing

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

comment:3 follow-up: 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

  • Authors set to Simon King
  • Commit set to 1382f4f40bea6fbf32af4f0f745aa2f645a235af
  • Status changed from new to needs_review

New commits:

175027dMerge branch 'u/SimonKing/ticket/15623' of git://trac.sagemath.org/sage into ticket/15810
1382f4fTrac 15810: Replace ._directed by .directed for immutable graph backend

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 follow-up: Changed 9 months ago by ncohen

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

Nathann

comment:11 follow-up: 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 follow-up: 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 ; follow-ups: 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 ; follow-up: 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 ; follow-up: 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

Last edited 9 months ago by ncohen (previous) (diff)

comment:19 follow-up: 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 ; follow-up: 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
True

I hate this code.

Understandably.

Nathann

comment:22 follow-up: 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 ; follow-up: 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 ; follow-up: Changed 9 months ago by 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)?

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 sage-git if that's the case ?

Nathann

comment:28 follow-up: 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 ; follow-up: 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 follow-up: 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@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:

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:

e9796a1trac #15810: Immutable directed graphs should know that they are directed
d6ca86ctrac #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): 
    919919                self._weighted = weighted 
    920920                self.allow_loops(loops, check=False) 
    921921                self.allow_multiple_edges(multiedges, check=False) 
    922             self._backend.directed = True 
    923922        else: 
    924923            raise NotImplementedError("Supported implementations: networkx, c_graph.") 
    925924 
  • 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): 
    15421542                self._weighted = weighted 
    15431543                self.allow_loops(loops, check=False) 
    15441544                self.allow_multiple_edges(multiedges, check=False) 
    1545             self._backend.directed = False 
    15461545        else: 
    15471546            raise NotImplementedError("Supported implementations: networkx, c_graph.") 

comment:39 follow-up: 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

  • Authors changed from Simon King to Nathann Cohen
  • 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
Note: See TracTickets for help on using tickets.