#18746: Cutwidth of a graph
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | d92f30f684949592f36e53e4c03c3bf73c583299
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18746 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
> I have performed several modifications and I'm now using the
`find_order` method of `vertex_separation`.
Okay ! Note that replacing the import 'fily.pyx' with a cimport is not
totally free. If you cimport functions, those functions will not be
inlined (in particular popcount32).
> I don't know how to use the templates (and I'm unable to find this in
#18395).
I just added a merge commit (that branch was in conflict with the latest
beta). The trick that is used in that ticket is the following: the
function `run_spring` takes an argument of type `dimension_t` (a fused
type). We do not care what the value of this parameter is, only its type
matters (`D_TWO` or `D_THREE`), for the function will be compiled twice,
once for each type.
Inside the function, depending on the *type* of this variable, the value
of `dim` is determined. As it never changes throughout the function, all
tests 'if dim == 2' are resolved at compile-time. You could use the same
trick to be able to pick different cost functions for free (at runtime),
but admittedly the trick is more a 'hack'.
> I agree that we can certainly speed-up method `compute_edge_cut`. The
best operation to compute the number of edges from `S+i` to `V\(S+i)` is
`count_S + degree[i] - 2*popcount32(S&g.graph[i])`, where `count_S` is the
number of edges from `S` to `V\S`. However, we don't store the number of
edges from `S` to `V\S`, so I don't know how to do this incremental
process.
Well, it is the 'current cost' that is computed in 'exists', isn't it? We
can just add an argument 'previous_cost' to 'exists', and then whenever
'exists' (which computed 'current_cost') calls 'exists', it can pass its
'current_cost' as a 'previous_cost'?.. This way 'exists' only has to
compute the difference.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18746#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.
