Opened 7 years ago

Closed 7 years ago

# 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 7 years 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 7 years ago by SimonKing

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

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

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 7 years ago by SimonKing

• 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 7 years ago by SimonKing

• Dependencies set to #15623

### comment:7 Changed 7 years 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 7 years 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 7 years ago by ncohen

Arg... I was uploading mine `:-/`

Nathann

### comment:10 follow-up: ↓ 12 Changed 7 years ago by ncohen

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

Nathann

### comment:11 follow-up: ↓ 14 Changed 7 years 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 7 years ago by SimonKing

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 7 years 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 7 years 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 7 years 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 7 years ago by SimonKing

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 7 years ago by SimonKing

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 7 years 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 why I thought it wouldn't.

Nathann

Version 0, edited 7 years ago by ncohen (next)

### comment:19 follow-up: ↓ 21 Changed 7 years 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 7 years ago by SimonKing

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 7 years ago by SimonKing

```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 7 years 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 7 years 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 7 years 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 7 years ago by SimonKing

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 7 years 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 7 years 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 7 years 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 7 years ago by SimonKing

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 7 years 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 7 years 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 7 years 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 7 years 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 self.directed:
```

### comment:35 Changed 7 years ago by SimonKing

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

### comment:36 Changed 7 years 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 7 years 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 7 years 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 7 years 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 7 years ago by SimonKing

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 7 years 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 7 years ago by ncohen

Thanks for the review `:-)`

Nathann

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