Hi,
I ran across a graph and partition for which it takes the search_tree
function 6 hours on my machine to complete, and I was wondering if
this is something to be expected, or a possible bug. I've been
working with graphs of similar sizes to this one with no real
problems, and in looking at the graph with the visualization
functions, there didn't seem to be anything especially odd about it.
I also profiled the search_tree function running on this graph; it
wasn't all that illuminating, but I can post the results of that here
too, if it would help.
Thanks for all your help,
-Dustin Pluta
University of California-Davis
The graph has 80 vertices, and is three colored:
Pi =
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], [16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47], [48, 49, 50, 51, 52,
53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79]]
G =
{0: {1: None, 6: None, 7: None, 10: None, 11: None, 12: None, 13:
None}, 1: {0: None, 6: None, 7: None, 10: None, 11: None, 12: None,
13: None, 18: None}, 2: {3: None, 4: None, 5: None, 8: None, 9: None,
14: None, 15: None, 20: None}, 3: {2: None, 4: None, 5: None, 8: None,
9: None, 14: None, 15: None, 22: None}, 4: {2: None, 3: None, 5: None,
8: None, 9: None, 14: None, 15: None, 24: None}, 5: {2: None, 3: None,
4: None, 8: None, 9: None, 14: None, 15: None, 26: None}, 6: {0: None,
1: None, 7: None, 10: None, 11: None, 12: None, 13: None, 28: None},
7: {0: None, 1: None, 6: None, 10: None, 11: None, 12: None, 13: None,
30: None}, 8: {32: None, 2: None, 3: None, 4: None, 5: None, 9: None,
14: None, 15: None}, 9: {2: None, 3: None, 4: None, 5: None, 8: None,
34: None, 14: None, 15: None}, 10: {0: None, 1: None, 36: None, 6:
None, 7: None, 11: None, 12: None, 13: None}, 11: {0: None, 1: None,
38: None, 6: None, 7: None, 10: None, 12: None, 13: None}, 12: {0:
None, 1: None, 6: None, 7: None, 40: None, 10: None, 11: None, 13:
None}, 13: {0: None, 1: None, 6: None, 7: None, 10: None, 11: None,
12: None, 42: None}, 14: {2: None, 3: None, 4: None, 5: None, 8: None,
9: None, 44: None, 15: None}, 15: {2: None, 3: None, 4: None, 5: None,
8: None, 9: None, 14: None, 46: None}, 16: {32: None, 34: None, 44:
None, 48: None, 20: None, 22: None, 24: None, 26: None}, 17: {33:
None, 35: None, 45: None, 49: None, 21: None, 23: None, 25: None, 27:
None}, 18: {32: None, 1: None, 34: None, 46: None, 50: None, 20: None,
22: None, 24: None, 26: None}, 19: {33: None, 35: None, 47: None, 51:
None, 21: None, 23: None, 25: None, 27: None}, 20: {2: None, 36: None,
38: None, 40: None, 16: None, 18: None, 52: None, 28: None, 30: None},
21: {37: None, 39: None, 41: None, 17: None, 19: None, 53: None, 29:
None, 31: None}, 22: {3: None, 36: None, 38: None, 42: None, 16: None,
18: None, 54: None, 28: None, 30: None}, 23: {37: None, 39: None, 43:
None, 17: None, 19: None, 55: None, 29: None, 31: None}, 24: {4: None,
40: None, 42: None, 16: None, 18: None, 56: None, 36: None, 28: None,
30: None}, 25: {37: None, 41: None, 43: None, 17: None, 19: None, 57:
None, 29: None, 31: None}, 26: {5: None, 38: None, 40: None, 42: None,
16: None, 18: None, 58: None, 28: None, 30: None}, 27: {39: None, 41:
None, 43: None, 17: None, 19: None, 59: None, 29: None, 31: None}, 28:
{32: None, 6: None, 44: None, 46: None, 20: None, 22: None, 24: None,
26: None, 60: None}, 29: {33: None, 45: None, 47: None, 21: None, 23:
None, 25: None, 27: None, 61: None}, 30: {34: None, 7: None, 44: None,
46: None, 20: None, 22: None, 24: None, 26: None, 62: None}, 31: {35:
None, 45: None, 47: None, 21: None, 23: None, 25: None, 27: None, 63:
None}, 32: {64: None, 36: None, 38: None, 8: None, 42: None, 16: None,
40: None, 18: None, 28: None}, 33: {65: None, 37: None, 39: None, 41:
None, 43: None, 17: None, 19: None, 29: None}, 34: {66: None, 36:
None, 38: None, 40: None, 9: None, 42: None, 16: None, 18: None, 30:
None}, 35: {67: None, 37: None, 39: None, 41: None, 43: None, 17:
None, 19: None, 31: None}, 36: {32: None, 34: None, 68: None, 10:
None, 44: None, 46: None, 20: None, 22: None, 24: None}, 37: {33:
None, 35: None, 69: None, 45: None, 47: None, 21: None, 23: None, 25:
None}, 38: {32: None, 34: None, 70: None, 11: None, 44: None, 46:
None, 20: None, 22: None, 26: None}, 39: {33: None, 35: None, 71:
None, 45: None, 47: None, 21: None, 23: None, 27: None}, 40: {32:
None, 34: None, 72: None, 44: None, 12: None, 46: None, 20: None, 24:
None, 26: None}, 41: {33: None, 35: None, 73: None, 45: None, 47:
None, 21: None, 25: None, 27: None}, 42: {32: None, 34: None, 74:
None, 44: None, 13: None, 46: None, 22: None, 24: None, 26: None}, 43:
{33: None, 35: None, 75: None, 45: None, 47: None, 23: None, 25: None,
27: None}, 44: {36: None, 38: None, 40: None, 42: None, 76: None, 14:
None, 16: None, 28: None, 30: None}, 45: {37: None, 39: None, 41:
None, 43: None, 77: None, 17: None, 29: None, 31: None}, 46: {36:
None, 38: None, 40: None, 42: None, 78: None, 15: None, 18: None, 28:
None, 30: None}, 47: {37: None, 39: None, 41: None, 43: None, 79:
None, 19: None, 29: None, 31: None}, 48: {16: None, 79: None}, 49:
{17: None, 78: None}, 50: {18: None, 77: None}, 51: {19: None, 76:
None}, 52: {75: None, 20: None}, 53: {74: None, 21: None}, 54: {73:
None, 22: None}, 55: {72: None, 23: None}, 56: {24: None, 71: None},
57: {25: None, 70: None}, 58: {26: None, 69: None}, 59: {27: None, 68:
None}, 60: {67: None, 28: None}, 61: {66: None, 29: None}, 62: {65:
None, 30: None}, 63: {64: None, 31: None}, 64: {32: None, 63: None},
65: {33: None, 62: None}, 66: {34: None, 61: None}, 67: {35: None, 60:
None}, 68: {59: None, 36: None}, 69: {58: None, 37: None}, 70: {57:
None, 38: None}, 71: {56: None, 39: None}, 72: {40: None, 55: None},
73: {41: None, 54: None}, 74: {42: None, 53: None}, 75: {43: None, 52:
None}, 76: {51: None, 44: None}, 77: {50: None, 45: None}, 78: {49:
None, 46: None}, 79: {48: None, 47: None}}
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://sage.math.washington.edu/sage/ and http://sage.scipy.org/sage/
-~----------~----~----~----~------~----~------~--~---
