Boost Edge Connectivity

[sagetrac-borassi]

This is a first step in including Boost Graph Library (#17966). I would like to implement the edge connectivity algorithm by converting a given Sage graph into a Boost graph, apply the Boost edge connectivity algorithm, and convert the result.

CC: @nathanncohen @dcoudert @jdemeyer @jpflori @slel @SnarkBoojum @vbraun @williamstein

Component: graph theory

Keywords: Boost, connectivity

Author: Michele Borassi

Branch: fe55f76

Reviewer: Nathann Cohen

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

[sagetrac-borassi]

Author: Michele Borassi

[sagetrac-borassi]

Changed keywords from none to Boost, connectivity

[sagetrac-borassi]

Branch: u/borassi/boost_edge_connectivity

[sagetrac-git]

Commit: fe40c54

[sagetrac-git]

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

fe40c54

Edge connectivity working

[sagetrac-borassi]

comment:4

This version lets us use Boost graph library to compute edge connectivity. Probably it is not the cleanest way to do it, but at least it works. I am looking for suggestions on how to improve the code, in order to make it more readable:

• is it better to use only Boost in C++ and Cython for the interface, or write the code in C++ and use Cython to convert the results? In the first case, we might have problems with generic types.
• should we only keep translation capabilities, or should we also add a new backend? In other words, do we need Boost for linear-time or O(n log n) time algorithms?

Some benchmark:

sage: G = graphs.RandomGNM(100,1000)
sage: %timeit G.edge_connectivity()
1 loops, best of 3: 10.7 s per loop
sage: %timeit G.to_boost_graph().edge_connectivity()
100 loops, best of 3: 2.04 ms per loop

Thank you very much!

[sagetrac-git]

Changed commit from fe40c54 to 9a0e868

[sagetrac-git]

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

9a0e868

Improved code for conversion

[dcoudert]

comment:6

Something is missing in BoostGraph

sage: H = G.to_boost_graph()
sage: H
<sage.graphs.base.boost_graph.BoostGraph object at 0x10f1a4ef0>
sage: H.
H.add_edge      H.add_vertex    H.num_edges     H.num_vertices  
sage: H.num_edges
<built-in method num_edges of sage.graphs.base.boost_graph.BoostGraph object at 0x10f1a4ef0>
sage: H.num_edges()
1000
sage: %timeit G.to_boost_graph().edge_connectivity()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-7-86519c65f6dd> in <module>()
----> 1 get_ipython().magic(u'timeit G.to_boost_graph().edge_connectivity()')

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
   2305         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2306         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2307         return self.run_line_magic(magic_name, magic_arg_s)
   2308 
   2309     #-------------------------------------------------------------------------

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
   2226                 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
   2227             with self.builtin_trap:
-> 2228                 result = fn(*args,**kwargs)
   2229             return result
   2230 

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, line, cell)

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
    191     # but it's overkill for just that one bit of state.
    192     def magic_deco(arg):
--> 193         call = lambda f, *a, **k: f(*a, **k)
    194 
    195         if callable(arg):

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, line, cell)
   1034             number = 1
   1035             for _ in range(1, 10):
-> 1036                 time_number = timer.timeit(number)
   1037                 worst_tuning = max(worst_tuning, time_number / number)
   1038                 if time_number >= 0.2:

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, number)
    130         gc.disable()
    131         try:
--> 132             timing = self.inner(it, self.timer)
    133         finally:
    134             if gcold:

<magic-timeit> in inner(_it, _timer)

AttributeError: 'sage.graphs.base.boost_graph.BoostGraph' object has no attribute 'edge_connectivity'
sage: 

[sagetrac-git]

Changed commit from 9a0e868 to b0ca92c

[sagetrac-git]

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

b0ca92c

Added sig_on, sig_off, and corrected edge_connectivity

[sagetrac-borassi]

comment:8

Now it should work!

[nathanncohen]

comment:9

Hellooooo Michele,

Great work, thank you very much! If we can speedup several Sage functions the
way you did for edge connectivity, the future looks bright :-P

I have been trying to avoid the creation of these two .cpp/.hpp files, but no
good new for the moment. I sent a question on cython-users [1], let's pray for
their wisdom. If there is no better way to do it than write cpp code, then
perhaps it will be better to 'patch' boost when it is installed, and only add
the couple of lines we need? We'll see this later, after they have had the time
to answer.

About your code:

• You add 'copyright' headers with a name which isn't yours: that's neither fair
  to Robert Miller nor to yourself! If you want your files to have a copyright
  header, please make it contain your name. Oh, and please steal a more recent
  header, for this one is a bit old. I think this one is the most recent

  #*****************************************************************************
  #       Copyright (C) 2015 Michele Borassi <email_adress>
  #
  #  Distributed under the terms of the GNU General Public License (GPL)
  #  as published by the Free Software Foundation; either version 2 of
  #  the License, or (at your option) any later version.
  #                  http://www.gnu.org/licenses/
  #*****************************************************************************
  

• I do not think that having a Graph.to_boost_graph makes much sense: at
  user-level, having a 'boost' graph does not have much interest as it only has
  very few commands to add edges/vertices, and your edge_connectivity
  function. It would make more sense to keep this function inside of
  boost_graph.pyx, for internal use.

• You should modify GenericGraph.edge_connectivity to make it able to call
  your function. Beware: this function applies to both directed and undirected
  graphs, while apparently your function only handles undirected graphs. The
  ideal, of course, would be to be able to call boost in both situations.

  Many graph function make several implementations available, and for instance
  GenericGraph.automorphism_group.

• Every function that you add must be documented. Besides, it would be cool to
  add your new file to the doc index [2].

• Every function must contain doctests.

  (tmp|✚3)~/sage/graphs/base$ sage -coverage boost_graph.pyx
  ------------------------------------------------------------------------
  SCORE boost_graph.pyx: 0.0% (0 of 6)
  
  Missing documentation:
      * line 57: def __cinit__(self)
      * line 62: def add_vertex(self)
      * line 65: def add_edge(self, u, v)
      * line 68: def num_vertices(self)
      * line 71: def num_edges(self)
      * line 74: def edge_connectivity(self)
  ------------------------------------------------------------------------
  

Thank you very much for this improvement. That's no small speedup, and an
important function.

Nathann

PS: Set the ticket's status to 'needs_review' when you want somebody to look at it.

[1] https://groups.google.com/d/topic/cython-users/ICRgCWVZ6RQ/discussion
[2] http://doc.sagemath.org/html/en/developer/sage_manuals.html#adding-a-new-file

[nathanncohen]

comment:10

Hello Michele,

You will find at public/18564 a commit that avoids the creation of .hpp and .cpp files.

Nathann

[dcoudert]

comment:11

Hello Nathann,

your branch is working well and this is easier than the first solution proposed by Michele.

sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %timeit G.edge_connectivity()
1 loops, best of 3: 1.02 s per loop
sage: %timeit G.to_boost_graph().edge_connectivity()
10 loops, best of 3: 46 ms per loop

I’m really impressed by what you did (both of you).

[sagetrac-git]

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

2b85ec1	trac #18564: Merged with 6.8.beta3
7d272ab	Avoid .hpp/.cpp files

[sagetrac-git]

Changed commit from b0ca92c to 7d272ab

[sagetrac-borassi]

comment:13

I have merged Nathann's work. I will continue from here!

[sagetrac-git]

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

9fc1be6	Moved conversion to file boost_graph
911c3ea	Multiple vertex/edge implementations working

[sagetrac-git]

Changed commit from 7d272ab to 911c3ea

[nathanncohen]

comment:15

Just a tip: if you run 'sage -cython -a your_file.pyx', you will get a .html file which indicates how much C code it takes to repleace each of your python lines (click on the yellow lines you see).

With this, you can easily notice loops which involve Python though they should not. It is often because of variables of unspecified type.

If you do the following replacement

- N = G_sage.num_verts()
+ cdef int N = G_sage.num_verts()

you should see something happen in the loops involving N.

Nathann

[sagetrac-borassi]

comment:16

Error compiling Cython file:
------------------------------------------------------------
...
                
        return G
    
    def __cinit__(self):
        sig_on()
        self.graph = new UndVecGraph()
                        ^
------------------------------------------------------------

src/sage/graphs/base/boost_graph.pyx:80:25: Operation only allowed in c++

How can I tell it that the language is C++?

[nathanncohen]

comment:17

On my machine your code compiles.

[dcoudert]

comment:18

The code also compiles on my computer

[sagetrac-borassi]

comment:42

Hellooooooo!

I summarize a discussion we had via email, dealing with the huge copy-paste. We found a way to avoid it: we created a C++ class boost_interface that interfaces Cython with Boost, and we used fused types to make generic functions accessing the C++ class.

The drawback is that we cannot access Boost graphs from Python anymore: Boost graphs must be defined and deleted in the same cdef function.

The advantage is that we can fully use the genericity of Boost, by calling any graph implementation we want.

The new code is available in this ticket's branch, while the old code is still available at u/borassi/boost_edge_connectivity_not_generic.

I changed the status to needs_work, because I would like to test the code and the doctest a bit more before asking for a review (in particular, I would like to check if all previous comments are still applied).

[dcoudert]

comment:43

I like this new implementation. I assume it will be relativity easy to call other boost method the same way.

[jdemeyer]

comment:44

This comment needs to be expanded:

class BoostGraph
/*
 * This generic class wraps a Boost graph, in order to make it Cython-friendly.

From reading the code, I have no idea what is Cython-unfriendly.

[sagetrac-git]

Changed commit from f3a1c07 to 51a183a

[sagetrac-git]

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

51a183a

Expanded the Cython-friendly comment, linked Boost ticket, removed trailing whitespaces

[sagetrac-borassi]

comment:46

Hello!

I have opened a Boost ticket on edge connectivity (https://svn.boost.org/trac/boost/ticket/11406), I have added this link in the documentation of our edge connectivity, I have expanded the comment as asked by jdemeyer, and I have corrected some small issues.

I hope that now the code is correct!

[dcoudert]

comment:47

Hello,

Install OK, tests OK, docbuild OK, page boost_graph.html looks good (it will certainly be enriched in the future), and it is fast.

sage: G = graphs.Grid2dGraph(20,20)
sage: %timeit G.edge_connectivity(boost=0)
1 loops, best of 3: 724 ms per loop
sage: %timeit G.edge_connectivity(boost=1)
100 loops, best of 3: 5.86 ms per loop

sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %timeit G.edge_connectivity(boost=0)
1 loops, best of 3: 1.14 s per loop
sage: %timeit G.edge_connectivity(boost=1)
10 loops, best of 3: 41.4 ms per loop

For me the patch is good to go. However, it would be better if an expert in C++/boost/etc. could check the patch before setting it to positive review.

Nice work anyway!

David.

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:48

Helloooooo Michele,

I made several modifications, available as a new commit at public/18564. All
of them are, of course, open to discussion.

• You don't need two 'pass' in the .pxd file

• About the paragraphs at the top of boost_graph.pyx: I find them a bit
  unclear. Could you be more specific in those sentences? For example (but not
  only), I do not get the meaning of

  and they cannot be shared by different Python functions, because they cannot
  be converted to Python objects.
  

• I opened a ticket at Boost's edge_connectivity returns wrong result on directed graphs #18753 (you are its author) to indicate that the boost
  bug had been reported upstream. That's part of a 'procedure' called 'stopgap',
  precisely meant for those situations (see
  http://doc.sagemath.org/html/en/developer/trac.html#stopgaps)

  I also turned your 'print warning' into a stopgap message.

• I reversed the names of edge_connectivity and boost_edge_connectivity: now
  the boost_edge_connectivity function is the one which takes a boost graph as
  argument.

• The link toward edge_connectivity that you had added at the top of the
  document was broken, for edge_connectivity was a cdef function in your
  patch, and you cannot link (in Sphinx) toward cdef functions. When yo uwork on
  the doc, you can compile it with --warn-links to spot broken links.

• I shortened a bit the doc of some boost functions: some of the things you say
  in the doc would be more appropriate as comments in the code.

• in simple cases, it is easier to use sig_check than sig_on/off. A
  sig_check is a way to check at a specific time whether an exception should
  be raised. See
  http://www.sagemath.org/documentation/html/en/developer/coding_in_cython.html#interrupt-and-signal-handling

• I renamed 'boost=True' to 'implementation="boost"', which is a bit more
  'standard'. You may not know what 'boost' is, but you understand the meaning
  of a 'implementation' selector.

Again, don't hesitate to oppose and discuss any of the changes in this commit,
as you are the reviewer of them. You are supposed to be as picky as we are when
we review your code.

In my mind, the branch with this commit added is good to go, though perhaps the
comments to the top of boost_graph.pyx could be made clearer. That's up to
you.

Have fun, and thank you very much again for this addition. Now that this is
written, it will be much easier to steal more boost code ;-)

Nathann

[sagetrac-git]

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

9063cdc	trac #18564: Merged with 6.8.beta5
f0709aa	trac #18564: Reviewer's commit

[sagetrac-git]

Changed commit from 51a183a to f0709aa

[sagetrac-borassi]

comment:50

Hello!
I have checked your code and included it into the current version. I have made a few modifications:

• I have tried to clarify a bit more the comment at the beginning of boost_graph.pyx.
• Martin showed me that the Boost edge connectivity code actually tells that the input graph must be undirected (Create a network flow graph out of the undirected graph FlowGraph flow_g(num_vertices(g))). Hence, I changed the stopgap sentence to "The edge connectivity of directed graphs is not implemented in Boost. The result may be mathematically unreliable." Thank you, Martin!
• I have added some spaces at the bottom of boost_graph.pxd, so that different graph implementations are aligned.
• Currently, our Boost code does not support edge labels. With the previous code, if we have used "implementation='boost',use_edge_labels=True" the edge labels would simply have been ignored without a warning. Now, the algorithm raises an error.
• If num_edges()==0 and vertices=True, I have modified the output to return [0,[],[[],[]]], that is [edge_connectivity, edges, [first set of vertices, second set of vertices]].

Also for me, now the patch is good to go!

[sagetrac-git]

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

fe55f76

Few more modifications

[sagetrac-git]

Changed commit from f0709aa to fe55f76

[nathanncohen]

comment:52

Hello Michele,

• I have tried to clarify a bit more the comment at the beginning of boost_graph.pyx.

Thanks! That's better.

• Martin showed me that the Boost edge connectivity code actually tells that the input graph must be undirected (Create a network flow graph out of the undirected graph FlowGraph flow_g(num_vertices(g))). Hence, I changed the stopgap sentence to "The edge connectivity of directed graphs is not implemented in Boost. The result may be mathematically unreliable." Thank you, Martin!

Oh. Does that mean that there is "no bug" in boost because they never claimed that it worked? If so, several things need to be done:

1. Close the bug report on boost's trac, as it is invalid
2. Change the milestone of our 'stopgap' ticket Boost's edge_connectivity returns wrong result on directed graphs #18753 to invalid/wontfix (and status to positive review)
3. Remove the stopgap warning from this branch's code
4. Remove any claim that boost's algorithm is unreliable for directed graphs, and claim instead that it is only avilable for undirected graphs
5. Raise an exception when 'boost' is requested to run on a directed graph.

• Currently, our Boost code does not support edge labels. With the previous code, if we have used "implementation='boost',use_edge_labels=True" the edge labels would simply have been ignored without a warning. Now, the algorithm raises an error.

Good. I missed that :-/

• If num_edges()==0 and vertices=True, I have modified the output to return [0,[],[[],[]]], that is [edge_connectivity, edges, [first set of vertices, second set of vertices]].

OKayyyyyyyyyyy.

Nathann

[sagetrac-borassi]

comment:53

• Martin showed me that the Boost edge connectivity code actually tells that the input graph must be undirected (Create a network flow graph out of the undirected graph FlowGraph flow_g(num_vertices(g))). Hence, I changed the stopgap sentence to "The edge connectivity of directed graphs is not implemented in Boost. The result may be mathematically unreliable." Thank you, Martin!

Oh. Does that mean that there is "no bug" in boost because they never claimed that it worked? If so, several things need to be done:

1. Close the bug report on boost's trac, as it is invalid
2. Change the milestone of our 'stopgap' ticket Boost's edge_connectivity returns wrong result on directed graphs #18753 to invalid/wontfix (and status to positive review)
3. Remove the stopgap warning from this branch's code
4. Remove any claim that boost's algorithm is unreliable for directed graphs, and claim instead that it is only avilable for undirected graphs
5. Raise an exception when 'boost' is requested to run on a directed graph.

Well, not so fast! Martin told me that the edge connectivity is a work in progress, and that they might make it work on directed graph soon. Furthermore, I still think that the Boost code has a bug: the comment I mentioned is a line comment in the middle of the code, and a user does not necessarily read the whole code before using it! Furthermore, the comment does not say explicitly that they do not claim it works. For this reason, I have added a comment saying this in the Boost ticket, but I think we should leave the patch as it is, waiting for the final Boost edge connectivity!

What do you think?

Thank you very much,

Michele

[nathanncohen]

comment:54

Well, not so fast! Martin told me that the edge connectivity is a work in progress, and that they might make it work on directed graph soon. Furthermore, I still think that the Boost code has a bug: the comment I mentioned is a line comment in the middle of the code, and a user does not necessarily read the whole code before using it! Furthermore, the comment does not say explicitly that they do not claim it works. For this reason, I have added a comment saying this in the Boost ticket, but I think we should leave the patch as it is, waiting for the final Boost edge connectivity!

What do you think?

That I trust your advice on this matter.

Good to go! (and thank you very much for this first 'boost' addition)

Nathann

[vbraun]

Changed branch from u/borassi/boost_edge_connectivity to fe55f76

[fchapoton]

Changed commit from fe55f76 to none