# Immutable directed graphs should know that they are directed

Reported by: Owned by: SimonKing major sage-6.2 graph theory immutable directed graph ncohen Nathann Cohen Simon King N/A d6ca86c (Commits) d6ca86c1d6984bc7a468b80905ddec01323cc9b6 #15623

### 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.
```

### comment:1 Changed 22 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 22 months ago by SimonKing

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

### comment:3 follow-up: ↓ 4 Changed 22 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 22 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 22 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 22 months ago by SimonKing

• Dependencies set to #15623

### comment:7 Changed 22 months ago by SimonKing

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

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

### comment:8 Changed 22 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 22 months ago by ncohen

Arg... I was uploading mine :-/

Nathann

### comment:10 follow-up: ↓ 12 Changed 22 months ago by ncohen

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

Nathann

### comment:11 follow-up: ↓ 14 Changed 22 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 22 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: ↓ 15 Changed 22 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 22 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: ↓ 16 ↓ 17 Changed 22 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 22 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: ↓ 18 Changed 22 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: ↓ 20 Changed 22 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 22 months ago by ncohen (previous) (diff)

### comment:19 follow-up: ↓ 21 Changed 22 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: ↓ 23 Changed 22 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 22 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: ↓ 24 Changed 22 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 22 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: ↓ 25 Changed 22 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: ↓ 26 Changed 22 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 22 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 22 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: ↓ 29 Changed 22 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: ↓ 30 Changed 22 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 22 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

Thank you!

Simon

### comment:32 follow-up: ↓ 33 Changed 22 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 22 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 22 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 22 months ago by SimonKing

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

### comment:36 Changed 22 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 22 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 22 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 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.")
• ## src/sage/graphs/graph.py

```diff --git a/src/sage/graphs/graph.py b/src/sage/graphs/graph.py
index a3f1dcd..4d15305 100644```
 a 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.")

### comment:39 follow-up: ↓ 40 Changed 22 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 22 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 22 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 22 months ago by ncohen

Thanks for the review :-)

Nathann

### comment:43 Changed 22 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.