<br><br><div class="gmail_quote">On Wed, Feb 9, 2011 at 3:53 PM, Gary King <span dir="ltr"><<a href="mailto:garywarrenking@gmail.com" target="_blank">garywarrenking@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">Hi Red,<div><br></div><div><div><div><blockquote type="cite"><div>I use cl-graph for general-purpose algorithms that work on graphical models, </div></blockquote><div><br></div>
</div>Cool!</div><div><div><br><blockquote type="cite"><div>copy-graph should probably call copy-vertex for every vertex and copy-edge for every edge. Subclasses are free to override as they see fit.</div></blockquote>
<div><br></div></div>That does seem to make sense.</div><div><div><br><blockquote type="cite"><div>What do you think?</div><div><br></div>
<div>Now I will describe an algorithm I think should be implementable using cl-graph with under 20 lines of code: a heuristic graph-coloring algorithm that attempts to paint a graph N colors and proceeds as follows:</div>
<div><br></div><div>1. While there are nodes left in the graph G</div><div> Find a node with degree < N.</div><div> If such a node is found, remove it from the graph and place it on the stack.</div><div>
If such a node is not found, choose some node x heuristically, remove it from the graph, and place it on the stack, marking it as 'spilled'</div><div>2. While there are nodes left on the stack</div><div>
Pop node x from the stack, construing a new graph G' that has x and any edges from G where the other edge is already in G'.</div><div> Color x based on the colors of its neighbors in G'</div><div><br>
</div><div>This is a simple graph-coloring algorithm used for register allocation. It's pretty straightforward to implement if the input graph can be copied, withered down to nothing, and then G' can be built back up using information from the original graph. Without a copy, more bookkeeping is required.</div>
</blockquote></div><div><br></div><div><br></div></div>I would have swore that there was a semi-generic copy-graph function in cl-graph. It appears I would have been wrong!</div><div><br></div><div>I'll think about this a bit and let you know what I'm thinking... do you have already have a function you use?</div>
</div></blockquote><div><br></div><div>I have nothing so far. I used moptilities' COPY-TEMPLATE in a basic version, but I wouldn't mind a more verbose method that subclasses override to more precisely copy over necessary slots. copy-graph et al should probably accept &key &allow-other-keys</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div>thanks,<br>
<font color="#888888"><div>
<span style="border-collapse:separate;color:rgb(0, 0, 0);font-family:Helvetica;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="border-collapse:separate;color:rgb(0, 0, 0);font-family:Helvetica;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div style="word-wrap:break-word">
<span style="border-collapse:separate;color:rgb(0, 0, 0);font-family:Helvetica;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div style="word-wrap:break-word">
<div>--</div><div>Gary Warren King, <a href="http://metabang.com/" target="_blank">metabang.com</a> <br>Cell: (413) 559 8738<br>Fax: (206) 338-4052<br>gwkkwg on Skype * garethsan on AIM * gwking on twitter<br></div></div>
</span></div></span></span>
</div>
<br></font></div></div></blockquote></div><br>
<div>- Red</div>