[cl-graph-devel] copy-graph

[Red Daly]

On Wed, Feb 9, 2011 at 3:53 PM, Gary King <garywarrenking at gmail.com> wrote:

> Hi Red,
>
> I use cl-graph for general-purpose algorithms that work on graphical
> models,
>
>
> Cool!
>
> 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.
>
>
> That does seem to make sense.
>
> What do you think?
>
> 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:
>
> 1.  While there are nodes left in the graph G
>          Find a node with degree < N.
>          If such a node is found, remove it from the graph and place it on
> the stack.
>          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'
> 2.  While there are nodes left on the stack
>      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'.
>      Color x based on the colors of its neighbors in G'
>
> 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.
>
>
>
> I would have swore that there was a semi-generic copy-graph function in
> cl-graph. It appears I would have been wrong!
>
> I'll think about this a bit and let you know what I'm thinking... do you
> have already have a function you use?
>

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


> thanks,
>   --
> Gary Warren King, metabang.com
> Cell: (413) 559 8738
> Fax: (206) 338-4052
> gwkkwg on Skype * garethsan on AIM * gwking on twitter
>
>
- Red
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-graph-devel/attachments/20110210/f091d33f/attachment.html>