#5793: [with patch, needs work] New algorithm for Max Clique in Graph class
using
Cython
--------------------------+-------------------------------------------------
Reporter: ncohen | Owner: rlm
Type: enhancement | Status: reopened
Priority: minor | Milestone: sage-4.1.1
Component: graph theory | Resolution:
Keywords: | Reviewer:
Author: | Merged:
--------------------------+-------------------------------------------------
Comment(by rlm):
5. There is one other thing to be aware of. You are assuming that the
vertex set is *always* {0,...,n-1}. In fact, this will cause some trouble:
{{{
sage: C = graphs.CubeGraph(4)
sage: C.maximum_clique()
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
...
TypeError: cannot concatenate 'str' and 'int' objects
sage: C.vertices()[0]
'0000'
}}}
Here is the idea to get around this, since this problem has come up many
times before:
{{{
sage: C = graphs.CubeGraph(4)
sage: G,d = C.relabel(inplace=False, return_map=True)
sage: d_inv = {}
sage: for v in d:
....: d_inv[d[v]] = v
....:
sage: C.vertices()
['0000',
'0001',
'0010',
'0011',
'0100',
'0101',
'0110',
'0111',
'1000',
'1001',
'1010',
'1011',
'1100',
'1101',
'1110',
'1111']
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sage: d
{'0000': 0,
'0001': 1,
'0010': 2,
'0011': 3,
'0100': 4,
'0101': 5,
'0110': 6,
'0111': 7,
'1000': 8,
'1001': 9,
'1010': 10,
'1011': 11,
'1100': 12,
'1101': 13,
'1110': 14,
'1111': 15}
sage: d_inv
{0: '0000',
1: '0001',
2: '0010',
3: '0011',
4: '0100',
5: '0101',
6: '0110',
7: '0111',
8: '1000',
9: '1001',
10: '1010',
11: '1011',
12: '1100',
13: '1101',
14: '1110',
15: '1111'}
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5793#comment:26>
Sage <http://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 post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
