A generic copy-graph function is desired to handle common cases where a duplicated graph is desired.<div><br></div><div>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.</div>
<div><br></div><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><div><br></div><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>
<div><br></div><div>- Red</div><div><br></div>