edge_connectivity and vertex labels

[jm58660]

g1 = Graph({0: [1]})
g2 = Graph({'a': ['b']})
g1.edge_connectivity(value_only=False), g2.edge_connectivity(value_only=False)

should output ([1, [(0, 1)]], [1, [('a', 'b')]]), but it does not look vertex labels at all.

CC: @nathanncohen @sagetrac-borassi @dcoudert

Component: graph theory

Author: Michele Borassi

Branch/Commit: 7f3c0b9

Reviewer: Vincent Delecroix, Jori Mäntysalo, Nathann Cohen, David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/19348

[jm58660]

Branch: u/jmantysalo/edge_connectivity_and_vertex_labels

[jm58660]

Author: Jori Mäntysalo

[jm58660]

Commit: b788ce7

[jm58660]

comment:3

This at least seems to work. May not be best way to write the code.

(Btw, I don't like to have keyword implementation in one function and algorithm in another.)

---

New commits:

b788ce7

Fix edge labels with value_only=False in edge_connectivity().

[nathanncohen]

comment:4

Hello Jori,

Sorry but the "bug" is more in the boost function that in generic_graph.py. Otherwise we still have a function somewhere that takes a vertex-labelled graph as input and returns an integer-labelled answer.

Furthermore, it is in any case better if instead of having a doctest returning 'a' you just check that the vertex belongs to the graph: the answer 'b' would be valid too.

Nathann

[jm58660]

Changed author from Jori Mäntysalo to none

[jm58660]

comment:5

Replying to @nathanncohen:

Sorry but the "bug" is more in the boost function that in generic_graph.py. Otherwise we still have a function somewhere that takes a vertex-labelled graph as input and returns an integer-labelled answer.

OK. I mark this as needs_work. (And let others to do it.)

Furthermore, it is in any case better if instead of having a doctest returning 'a' you just check that the vertex belongs to the graph: the answer 'b' would be valid too.

Ah, then I misunderstood some documentation about this kind of functions.

Assuming for example that vertices are ASCII-strings, will .vertices() give them alphabetically?

[nathanncohen]

comment:6

Ah, then I misunderstood some documentation about this kind of functions.

Assuming for example that vertices are ASCII-strings, will .vertices() give them alphabetically?

It will. But in the present case, I think that you are after a "bipartition of your vertex set", and that you could get {a},{b} as often as {b},{a}.

Nathann

[sagetrac-borassi]

Author: Michele Borassi

[sagetrac-borassi]

comment:7

Hello!

You are right: the edge connectivity is the first Boost algorithm I implemented, and I missed the vertex labels. Thank you very much for noting this.

Since I made the mistake, I think I should solve it: let me know if you like my solution. I replaced Jori's branch with a different one, that corrects boost_graph.pyx instead of generic_graph.pyx. I hope this is the correct procedure: if not, let me know!

Have fun!

Michele

[sagetrac-borassi]

Changed branch from u/jmantysalo/edge_connectivity_and_vertex_labels to u/borassi/edge_connectivity_and_vertex_labels

[videlec]

comment:9

Hello,

What is the point of making a dict to map 0, 1, 2, 3, ... to Python objects? Use a list!

cdef list int_to_vertex = g.vertices()

Vincent

---

New commits:

98e4667

Solved bug with edge labels

[videlec]

Changed commit from b788ce7 to 98e4667

[videlec]

Reviewer: Vincent Delecroix

[jm58660]

comment:10

Replying to @sagetrac-borassi:

I replaced Jori's branch with a different one, that corrects boost_graph.pyx instead of generic_graph.pyx. I hope this is the correct procedure: if not, let me know!

Yes, it is good. Actually I think that whatever makes Sage better is good.

[sagetrac-borassi]

comment:11

Hello!

What is the point of making a dict to map 0, 1, 2, 3, ... to Python objects? Use a list!

I used a dict because (I think) lists are linked lists, and the random access time is O(n). Am I missing something?

[jm58660]

comment:12

Replying to @sagetrac-borassi:

What is the point of making a dict to map 0, 1, 2, 3, ... to Python objects? Use a list!

I used a dict because (I think) lists are linked lists, and the random access time is O(n). Am I missing something?

https://wiki.python.org/moin/TimeComplexity says that it is O(1).

[sagetrac-borassi]

comment:13

You are right! I modified everything!

[sagetrac-git]

Changed commit from 98e4667 to 7f3c0b9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7f3c0b9

Use list instead of dict

[jm58660]

comment:15

FYI I did some more testing and it seems that vertex_connectivity(), line_graph() etc etc. does not have same kind of bug.

I guess this could be on checklist for reviewers. This applies to all kind of containers, like graphs and sets.

[sagetrac-borassi]

comment:16

Sorry, I have troubles understanding your comment. After you said that lists were better than dictionaries, I transformed all dictionaries named int_to_vertex into lists (there were several other routines where these dictionaries were used: these routines were correct, but the new version is simpler and more efficient).

Am I missing some points?

Replying to @jm58660:

FYI I did some more testing and it seems that vertex_connectivity(), line_graph() etc etc. does not have same kind of bug.

I guess this could be on checklist for reviewers. This applies to all kind of containers, like graphs and sets.

[jm58660]

comment:17

Replying to @sagetrac-borassi:

Sorry, I have troubles understanding your comment.

Sorry for being unclear. My comment did not relate to this spefic ticket. (And maybe I should have write it to sage-devel instead of this.)

[nathanncohen]

comment:18

Sorry, I have troubles understanding your comment. After you said that lists were better than dictionaries, I transformed all dictionaries named int_to_vertex into lists (there were several other routines where these dictionaries were used: these routines were correct, but the new version is simpler and more efficient).

Am I missing some points?

To me at least you did right. Is there any reason why you added those <int> cast though? Given that result is a typed vector that should not be necessary ?... O_o

Nathann

[sagetrac-borassi]

comment:19

I inserted them in order to avoid a compilation error, saying that there was a wrong conversion from long to int.

Replying to @nathanncohen:

Sorry, I have troubles understanding your comment. After you said that lists were better than dictionaries, I transformed all dictionaries named int_to_vertex into lists (there were several other routines where these dictionaries were used: these routines were correct, but the new version is simpler and more efficient).

Am I missing some points?

To me at least you did right. Is there any reason why you added those <int> cast though? Given that result is a typed vector that should not be necessary ?... O_o

Nathann

[nathanncohen]

comment:20

I inserted them in order to avoid a compilation error, saying that there was a wrong conversion from long to int.

Okayyyyy O_o

Good to know. Thanks.

Nathann

[videlec]

comment:21

Replying to @jm58660:

Replying to @sagetrac-borassi:

What is the point of making a dict to map 0, 1, 2, 3, ... to Python objects? Use a list!

I used a dict because (I think) lists are linked lists, and the random access time is O(n). Am I missing something?

https://wiki.python.org/moin/TimeComplexity says that it is O(1).

More precisely:

• A python object is a PyObject *
• A list or a tuple is a PyObject **
• A set/dict is a hash table
  So you that you can not beat a Python list.

On the other hand, if you want faster access to my_list[i] you can have a look at Cython compiler directives.

[jm58660]

comment:22

This is still in needs_review, but the discussions seems to have end. Is there something to do, or can someone who understand the code click this to positive_review?

[videlec]

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Jori Mäntysalo, Nathann Cohen

[videlec]

comment:23

I am ok for a positive review. I let to the other reviewers some possible final comment.

[nathanncohen]

comment:24

I have nothing against this branch.

[dcoudert]

Changed reviewer from Vincent Delecroix, Jori Mäntysalo, Nathann Cohen to Vincent Delecroix, Jori Mäntysalo, Nathann Cohen, David Coudert

[dcoudert]

comment:25

Passes all tests on my computer as well, so let's go.

[vbraun]

Changed branch from u/borassi/edge_connectivity_and_vertex_labels to 7f3c0b9