On Nov 23, 4:05 am, Dustin Pluta <[EMAIL PROTECTED]> wrote:
> Hi,
Hello Dustin,
>
> 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.
>
Could you post the exact code that you are running? Maybe somebody
more familiar with the code (Robert or Jason) might be able to guess
what is happening without it, but I think it can't hurt.
> Thanks for all your help,
> -Dustin Pluta
> University of California-Davis
>
Cheers,
Michael
> 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/
-~----------~----~----~----~------~----~------~--~---
