[cl-graph-devel] copy-graph

[Red Daly]

A generic copy-graph function is desired to handle common cases where a
duplicated graph is desired.

I use cl-graph for general-purpose algorithms that work on graphical models,
and it's handy to have a simple clone feature. A "deep clone" is a pretty
messy concept without more clarification--after all, where does the copying
stop?  However, for the built-in graph container classes it makes sense to
have a common-sense copy operation.

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.

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.

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