`compressed_sparse_row_graph` has orphaned `add_vertex()` / `add_vertices()` from removed interface

[Becheler]

Problem

compressed_sparse_row_graph.hpp contains four public add_vertex / add_vertices functions that were part of an old interface deliberately removed in 2009:

• Old interface documentation
• New interface documentation

Vertex add_vertex(compressed_sparse_row_graph& g);
Vertex add_vertex(compressed_sparse_row_graph& g, const vertex_bundled& p);  // directed
Vertex add_vertex(compressed_sparse_row_graph& g, const vertex_bundled& p);  // bidirectional
Vertex add_vertices(vertices_size_type count, compressed_sparse_row_graph& g); // directed

These are not in the HTML documentation, not tested in test/csr_graph_test.cpp, and not used anywhere in BGL internally.

Meanwhile, the documentation states: "The CSR graph is immutable after construction. You cannot call add_vertex()."

The related add_edges() and add_edges_sorted() functions are documented and tested.

History

• 2005 (0e2f4646): Jeremiah Willcock added add_vertex(), add_vertices(), and add_edges() as "incremental construction functions." All three were documented and tested.
• 2009 (b2636ec3, "Removed old CSR interface; fixes #3135 "): add_vertex() and add_vertices() were removed from documentation and tests, but the implementations were left in the header.
• 2012 (849d1538): add_edges() was separately removed from bidirectional CSR as "broken and not documented."

Question

Should add_vertex() / add_vertices() be tested and documented, or removed? Probably removed I guess, but I find it odd the implementation was never actually removed.

[jeremy-murphy]

That is curious. As you say, CSR graphs are immutable, so I don't understand why those functions would exist for it at all, other than perhaps to satisfy some graph concept interface. I just noticed test_graphs.cpp, which does just that. It runs a bunch of static (meta) tests on all graphs, and some logical tests on all graphs except for CSR, because it fails the graph_has_add_vertex test. So yeah, I would assume that all the add_ functions are dead code for CSR.

[Becheler]

As you say, CSR graphs are immutable, so I don't understand why those functions would exist for it at all

If I understand CSR format correctly, I believe one can incrementally build the two arrays (neighbors and begin markers) as long as the topology does not change and that you know degrees in advance. So if building the CSR from a parser, I guess they could have used the old interface to progressively add vertices an edges during parsing ? Wild guess.

So the functions could be safely removed ? If undocumented and untested we are unlikely to break any client code relying on it, right ?

[jeremy-murphy]

Problem with undocumented features is we could either document them, but risk is that the functionality is half-baked, or just delete them, and risk breaking users that are actually relying on it (and possibly deleting something that could be useful).
This kind of tech debt is low priority for me. I would like to be able to categorize these "tech debt" issues so we can distinguish them from bugs.

[jeremy-murphy]

I'm not sure this is beginner friendly after all, as I think someone experienced needs to evaluate whether this is functionality worth keeping or not.

[jeremy-murphy]

Unfortunately I can't change labels from the mobile app, but I thought "Undocumented" would be more appropriate than "Enhancement" right now.

[Becheler]

Ok. I will add a label "techical debt" and a "low priority" one.
I will remove the "beginner friendly" label, although we may want to have some issues labeled as such to give the opportunity to actual beginner to get started with BGL contributions.

[andreacassioli]

Lately I have been looking into CSR for my application, and those add_XXX functions have been puzzling me a lot. It is rather confusing that an immutable data structure has some modifiers. If they are used for incremental build, then it would be good to give a good description and an example, otherwise maybe they are good candidates for deprecation.