#17711: Pre-processing for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_info
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | f62716539aaf4c236041d1e31dbf59bcb8bba750
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17711 |
Dependencies: |
#17647 |
-------------------------+-------------------------------------------------
Comment (by ncohen):
> So you propose that I
> 1. test if the graph is connected. If not, then apply the algorithm on
each connected component.
> 2. If G is directed, test if is strongly connected. If not, then apply
the algorithm on each scc
I had something simpler (and a it more ressource-consuming) in mind:
1) If you have a graph, test if it is connected. If it is not, turn it
into a digraph
2) Now the scc code for digraphs will handle each connected component
independently
So you get it for free, more or less.
> I had the same remark while reviewing patch #12181 (and certainly other
tickets). Nothing has been done since. I don't even know where is the
code.
> In fact, we have many random<TAB> stuff in global namespace...
Pffff.. It comes from the "sandpile" module and I am not even sure that
any of that code is useful to anything.
Plus I am not very eager to move 'random_DAG' to `digraphs.<tab>` because
I do not agree with the way it generates the random dag. Also, some random
'weights' are involved.
I will probably end up removing the imports into the global namespace, and
that will be all.
I'll cc you if I do.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17711#comment:7>
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.
