"Claude 3.5 Sonnet" created code for "Boost remove edge constant time" overall behaves quadratic

fgqr.cpp

//=======================================================================
// Copyright 2024
// Author: Hermann Stamm-Wilbrandt
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <iostream>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <vector>

struct EdgeData {
    std::size_t index;
};

using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    boost::no_property,
    EdgeData
>;

class FastGraph {
    Graph g;
    std::vector<Graph::edge_descriptor> edge_index;
    std::vector<bool> removed;
    
public:
    void add_edge(int u, int v) {
        auto [e, success] = boost::add_edge(u, v, g);
        g[e].index = edge_index.size();
        edge_index.push_back(e);
        removed.push_back(false);
    }

    void remove_edge(Graph::edge_descriptor e) {
        std::size_t idx = g[e].index;
        removed[idx] = true;
        boost::remove_edge(e, g);
    }

    void remove_edge(int u, int v) {
        auto [e, exists] = boost::edge(u, v, g);
        if (exists) {
            remove_edge(e);
        }
    }

    bool has_edge(int u, int v) const {
        auto [e, exists] = boost::edge(u, v, g);
        return exists && !removed[g[e].index];
    }

    void clear_vertex(int u) {
        while (true) {
            auto [ei, eend] = boost::out_edges(u, g);
	    if (ei == eend)
                break;
            if (!removed[g[*ei].index]) {
                remove_edge(*ei);
            }
        }
    }

    // Additional utility functions
    std::size_t num_vertices() const {
        return boost::num_vertices(g);
    }

    std::size_t num_edges() const {
        return boost::num_edges(g);
    }

    // Print graph structure
    void print() const {
        std::cout << "Graph structure:\n";
        for (auto [vi, vend] = boost::vertices(g); vi != vend; ++vi) {
            std::cout << *vi << " -> ";
            for (auto [ei, eend] = boost::out_edges(*vi, g); ei != eend; ++ei) {
                auto target = boost::target(*ei, g);
                if (!removed[g[*ei].index]) {
                    std::cout << target << " ";
                }
            }
            std::cout << "\n";
        }
    }
};

/*
    Wheel graphs      W5   4      W7  6---1
                          /|\        / \ / \
                         / | \      5---0---2
                        3--0--1      \ / \ /
                         \ | /        4---3
                          \|/
                           2
*/
template< class Graph >  void wheel(Graph& g, int n);


/*
   Demo function removing the edges for all but central vertex of
   wheel graph Wn, showing roughly linear time for ugraph_01 
   [because of O(1) remove_edge()] and quadratic time for ugraph.

   Very simplified version of what planar_vertex_six_coloring() does.
   Proof that boost::undirected_graph_constant_time_edge_add_and_remove
   class is essential for linear runtime of that vertex coloring algorithm.
*/
template< class Graph >  float clear_vertices(Graph& g, int n)
{
    wheel(g, n);

    std::vector< unsigned > vec;
    for(unsigned v=0; v<g.num_vertices(); ++v)
        { vec.push_back(v); }

    clock_t start = clock();

    unsigned u;
    BOOST_REVERSE_FOREACH(u, vec)  { g.clear_vertex(u); }

    return (clock()-start)*1.0/CLOCKS_PER_SEC;
}


int main(int argc, char*argv[]) {
    int n = argc < 2 ? 10000 : atoi(argv[1]);
    FastGraph fg;

    std::cout << "Wn     FastGraph  runtimes [s]" << std::endl;

    for (int i=0; i <= 4; ++i, n*=2)
    {
        std::cout << n << "  "
                  << clear_vertices(fg, n) << std::endl;
    }

    return 0;
}


template< class Graph >
void wheel(Graph& g, int n)
{
    BOOST_ASSERT(n > 3);

    g = Graph();
    int c = 0;

    unsigned v = c++;
    unsigned w = c++;
    g.add_edge(v, w);

    unsigned x = w;

    for (int i=3; i <= n; ++i)
    {
        unsigned y = c++;
        g.add_edge(v, y);
        g.add_edge(x, y);
        x = y;
    }

    g.add_edge(x, w);
}

I asked "Claude 3.5 Sonnet" AI for "Boost remove edge constant time" and got "FastGraph" code.
I inserted that into my Boost code showing quadratic runtime for undirected graph:
https://github.com/Hermann-SW/graph/blob/develop/example/undirected_graph_constant_time_edge_add_and_remove.cpp

Result is above script showing quadratic runtime:

pi@raspberrypi5:~/graph/example $ g++ -O3 -Wall -Wextra -pedantic fgqr.cpp
pi@raspberrypi5:~/graph/example $ ./a.out 
Wn     FastGraph  runtimes [s]
10000  0.038851
20000  0.153668
40000  0.608109
80000  2.40422
160000  9.69207
pi@raspberrypi5:~/graph/example $