[cl-graph-devel] copy-graph

[Gary King]

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?

thanks,
--
Gary Warren King, metabang.com 
Cell: (413) 559 8738
Fax: (206) 338-4052
gwkkwg on Skype * garethsan on AIM * gwking on twitter

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-graph-devel/attachments/20110209/7ebd37df/attachment.html>