Thanks Nathan, I found Sage based on your introduction.
Can you or anyone suggest a good small starter graph program in Java. On Mar 7, 11:07 am, Nathann Cohen <[email protected]> wrote: > Hello !!! > > I thought a bit about your problem but I do not think I could smartly > change the edge_coloring function either to obtain a solver for what > you are trying to do... > > As you seem to be trying to solve your problem on > - Small instances > - Not necessarily using the least number possible of colors (so you do > not really need a proof of optimality) > > I think the best way to solve your puzzle may be to bruteforce it > using C, or if it is a bit too long, to randomize it as you mentionned > it yourself. I do not advise you to write this program using Sage, as > it would perform very badly :-) > > As checking whether two adjacent vertices have the same color code is > not hard to write, it may be quick enough to write the monte carlo > version. If you want to bruteforce it, it may not be too bad to use > some kind of depth-first search : > As you want to try *all* the possible colorings, and check whether > your constraint is fulfilled, maybe you could use the order on the > vertices to : > > * color the edges of vertex 0, then complete with the edges of 1, > then ... > * each time you notice that you have given a color to all the edges of > a new vertex, check its neighbors which are already totally colored > have different codes > * if it is not the case, there is no need to explore further this > coloring, and you can cut to try the next > > Besides, if you have few graphs to test, maybe you could first pick a > *potentially good* ordering of your vertices using Sage. I would try > the reverse of the ordering given by a lex_BFS, just in case. I can > not prove it will be better than any other, but it is meant to group > together vertices which have many common neighbors, so it could be a > way for your bruteforce to *cut* more often :-) > > Nathann > > P.S. : there are ways to make Sage communicate efficiently with C > sources, and it is what should be done if you end up with a piece of > software you would like to integrate in Sage, but considering the time > you have available... :-) > > On 7 mar, 16:51, Michael Vogt <[email protected]> wrote: > > > > > David, > > > Thanks so much for your interest. > > > I want the program to calculate the edge labels/colors/weight for a given > > unlabeled graph under the constraint that no adjacent vertices have the > > same number of each label. > > > Maybe "weights" can be used instead of the edge label data structure in > > Sage. > > > I want to start with the straight adj. matrix, only 1 for values, and > > compute the labels for edges, however they are represented. > > > Michael > > > --- On Sun, 3/7/10, David Joyner <[email protected]> wrote: > > > > From: David Joyner <[email protected]> > > > Subject: Re: [sage-edu] Re: I need a modified edge coloring function to > > > help student with graph theory project > > > To: [email protected] > > > Date: Sunday, March 7, 2010, 10:30 AM > > > On Sun, Mar 7, 2010 at 10:24 AM, > > > m_p_v_13 <[email protected]> > > > wrote: > > > > David, > > > > > Yes, the graph is simple. > > > > > The problem is to find a coloring, or colorings, of a > > > given simple > > > > connected graph using three colors. > > > > > For example for this sample graph with verticies > > > 1,2,3,4 and edge > > > > colors a,b,c > > > > > 1--b--2 > > > > | | > > > > c b > > > > | | > > > > 4--c--3 > > > > > Below is the Adjacency Matrix with a sample coloring > > > using colors > > > > a,b,c > > > > and a table showing the color code for each vertice. > > > > > Adj. Mat. color code > > > > 1 2 3 4 v abc > > > > ------- - ---- > > > > 1 | 0 b 0 c 1 | 011 e.g. 0-a, 1-2, > > > 1-c > > > > 2 | b 0 b 0 2 | 020 > > > > 3 | 0 b 0 c 3 | 011 > > > > 4 | c 0 c 0 4 | 002 > > > > You mean this? > > > > sage: A = > > > matrix([[0,2,0,3],[0,0,2,0],[0,0,0,3],[0,0,0,0]]) > > > sage: G = Graph(A, format = "adjacency_matrix", weighted = > > > True) > > > sage: G.weighted_adjacency_matrix() > > > [0 2 0 3] > > > [2 0 2 0] > > > [0 2 0 3] > > > [3 0 3 0] > > > > What else are you trying to do? Enumerate all colorings? > > > I think the wikipedia links explain more about that. > > > > > This coloring works because no adjacent vertices have > > > the same color > > > > code. > > > > > On Mar 7, 7:13 am, David Joyner <[email protected]> > > > wrote: > > > >> On Sun, Mar 7, 2010 at 5:32 AM, m_p_v_13 <[email protected]> > > > wrote: > > > >> > Hello, > > > > >> > The student is my daughter who is doing a > > > graph theory investigation > > > >> > for a high school class independent study. > > > > >> > It is an detectable type edge coloring > > > problem. > > > >> > Edges must be colored so that adjacent > > > vertices do not have the same > > > >> > number of each color of edges. > > > > >> Can you please rephrase? Do you have a simple > > > graph? > > > >> Do you want the chromatic index > > > >> (http://en.wikipedia.org/wiki/Edge_coloring) > > > >> or the chromatic number (http://en.wikipedia.org/wiki/Graph_coloring)? > > > > >> > She is investigating a limited case for three > > > colors and 6 or seven > > > >> > vertices, primarily theoretically by > > > partitioning the problem. > > > > >> > She asked if I could help her with a program > > > to generate some > > > >> > solutions as an investigative tool. > > > >> > I thought I could, but I'm stuck. > > > > >> > I was able to generate and print adj. > > > matrices for the appropriate > > > >> > graphs using the graphs() function and > > > figured out how to set the edge > > > >> > labels. > > > > >> > I tried to understand and modify the > > > edge_coloring() function in > > > >> > sage.graphs.graph_coloring package but it is > > > way to complex for me and > > > >> > the time I have left. This has been my > > > first exposure to Sage or > > > >> > python. I have programmed a lot of C, C++, > > > and Java. > > > > >> > Is there anyone out there who can either > > > (within the next 10 hours) > > > > >> > - modify the Sage edge_coloring function for > > > this case, or > > > > >> > - point me to anything else, simpler, that > > > can be used or modified to > > > >> > generate some solutions (greedy, monte carlo, > > > brute force, slow, etc.) > > > >> > on any platform (in Sage, Java, Matlib, > > > etc.) that we have a chance > > > >> > to understand. (e.g. like the "The greedy > > > coloring algorithm in 6 > > > >> > lines" described by Nathann.Cohen). > > > > >> > Thanks for any help or suggestions. > > > > >> > Michael Vogt > > > > >> > -- > > > >> > You received this message because you are > > > subscribed to the Google Groups "sage-edu" 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 > > > >> > athttp://groups.google.com/group/sage-edu?hl=en. > > > > > -- > > > > You received this message because you are subscribed > > > to the Google Groups "sage-edu" 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 > > > > athttp://groups.google.com/group/sage-edu?hl=en. > > > > -- > > > You received this message because you are subscribed to the > > > Google Groups "sage-edu" 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 > > > athttp://groups.google.com/group/sage-edu?hl=en. -- You received this message because you are subscribed to the Google Groups "sage-edu" 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-edu?hl=en.
