#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 | 165c0b64eeb569161e862603535e2ef2592c2229
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18746 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Helloooooooo,
Several remarks:
- You can rewrite {{{dict( (u,i) for i,u in enumerate(L) )}}} as
{{{ {u:i for i,v in enumerate(L) }}}
- In
{{{ cpt += popcount32( (Sbar&g.graph[i]) * ((S>>i)&1) ) }}}
Instead of multiplying by {{{((S>>i)&1)}}}, which is 0 or 1, you can do
{{{ cpt += popcount32( (Sbar&g.graph[i]) & (-((S>>i)&1)) ) }}}
given that 0 in binary is '0...0' and that -1 is '1.....1'.
This being said, there may be time to save by not re-computing the cost
from
scratch (considering all n vertices) but by computing only the
difference from
the previous cost, caused by the addition of the last vertex in the
ordering.
- About
{{{
+ This method differs from method
+ `sage.graphs.graph_decompositions.vertex_separation.exists` by a
single
+ line. We can certainly combine codes.
}}}
Something with templates, like it is done in #18395?
- About
{{{
+
+ This is a copy/paste of method
+ `sage.graphs.graph_decompositions.vertex_separation.find_order` and
so we
+ can certainly directly import it.
}}}
If all you need is to change `int8_t` into `uint8_t`
`vertex_separation_exp` then yes of course!
Have fuuuuuuun,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18746#comment:4>
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.
