#18564: Boost Edge Connectivity
-------------------------------------+-------------------------------------
Reporter: borassi | Owner: borassi
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Boost, | Merged in:
connectivity | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 7481889e9795e22c5d7ea9b42335f14548c9c636
u/borassi/boost_edge_connectivity | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Helloooooo,
> I have two problems with rebase:
I will give it a try once I answer this message. I do not understand the
error that you meet. Perhaps a not-up-to-date 'develop'? Either way, if it
takes more than 30 seconds it means that something it not right.
> Could you check that now the SCC/BFS code is correct?
I do not think that it is. It fails on a very simple graph
{{{
sage: digraphs.Circuit(10).edge_connectivity(boost=True,vertices=True)
The directed edge connectivity algorithm implemented in the Boost graph
library is not reliable. The result could be wrong.
[1, [[0, 1]], [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], []]]
}}}
You are simply doing things in the wrong direction. You should use the
*sources* of the edges as the sources of your BFS.
And you can also simplify your code a lot. Something like this should do:
{{{
a = set(H.breadth_first_search([x for x,y in edges])))
b = set(H).difference(a)
}}}
I did not try it, but I am optimistic.
Two other things:
- There are many 'trailing whitespaces' [1] in your code. You can add
`'(show-trailing-whitespace t)` in your `~/.emacs` file (if you use emacs
`:-P`) to see them.
- You should add a doctest for the digraph+boost case. You would see that
your code breaks.
- `Set` is a combinat object that you should not use unless you need their
usual over-abstraction. 'set' is a faster python set object, which does
what you need in this situation.
Nathann
[1] http://programmers.stackexchange.com/questions/121555/why-is-trailing-
whitespace-a-big-deal
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:35>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
