Documentation overhaul

A space for us to workshop ideas (maybe enabling Github Discussions later in time).

If you can't edit this page, get in touch with me (Jeremy Murphy).

Please use:

• h1 to propose a new idea,
• h2 to propose variations to an existing idea
• h3 for topics.

Problems with the existing documentation:

• fill in later...

Examples of good documentation that we might copy/steal and how they fix the identified problems:

• etc...

Make the Landing Page more friendly

Existing limitations

• Newcomers struggle to build a simple graph
• Newcomers struggle finding simple examples

A newcomer who wants to simply build their first graph has to:

1. find the Table of Content link hidden in the doc landing page
2. Navigate no less than 7 sections of the ToC to reach a suitable example:
   1. Introduction to the BGL
   2. Parallel BGL
   3. History
   4. List of BGL Users
   5. Publications
   6. Acknowledgements
   7. A Quick Tour of the Boost Graph Library -> here an example of adjacency list

Most of these sections sound like the BGL trying to justify itself: but users just want to be shown how to use it.

Possible solutions

1. Make the ToC the first page users land on
2. Just below the ToC display an example to showcase how concise the BGL syntax can be, e.g.: build a graph, print vertices and edges, and run a DFS.
3. Merge the History/List of Users/Publications/Acknowledgements into a single page About and move it toward the end of the ToC
4. Update the Introduction to the BGL section, that it is too long and noisy:
   • make it less like self-justification (noise)
   • remove the analogy to the STL (noise: in 2023 we know what iterators are)
   • Make it very minimal, with only most important information:
     • 1 sentence description
     • Github Link
     • License
     • Supported compilers (?)
     • Very short example to show includes + one line of code + output
     • Important current topic (?)
     • e.g. mp-units home

Better navigation simple features

Existing limitations

Newcomers struggle with simple features, e.g. modifying vertex property

This stems from several reasons:

• The "right" example code is difficult to locate in the BGL documentation
• Examples are pre-C++11
• Useful snippets of code are diluted in text, making it harder to identify sections of interest
• Navigation in the doc is difficult, as returning to the top-level ToC is cumbersome or not possible

Possible solution

1. Make a permanent link to the top-level ToC (homepage) on every documentation page
2. Simple features seem to be listed in the A Quick Tour of the Boost Graph Library page, but it could be made easier to navigate:
   • remove the illustration comparing with STL (noise)
   • remove most of the text (noise): for example "First we can access all of the vertices in the graph using the vertices() function of the VertexListGraph interface. This function returns a std::pair of vertex iterators (the first iterator points to the "beginning" of the vertices and the second iterator points "past the end")": this is just noise.
   • Add self-contained examples for each purpose a new user may have in mind:
     • build a graph
     • add edges
     • in_edges vs out_edges
     • add vertices properties
     • add edges properties
   • Do NOT split example codes, this makes copy pasting nasty: for newcomers it is better to have some repetition than having them scroll to find the missing parts of the code that would make their example compile ...
   • Make all these examples easily discoverable by summarizing them in a page-ToC at the top

Explain Graph Representations and their template parameters better

Existing limitations

Newcomers struggle instantiating simple adjacency lists

Possible reasons:

1. Template parameters overhead: Newcomers will often want to play with VertexProperty and EdgeProperty first, and later think about graph optimized representation. But the order of the template parameters force them to think first about OutEdgeList, VertexList, Directed.
2. The page Chosing graph type is very noisy, lengthy, technical, discouraging newcomers to actually make these choices.
3. The same page presents template parameter choices in a different order (VertexList first) than the implementation (OutEdgeList first), what confused me further.

Possible solution

1. Implement a helper function with defaulted template arguments in the "user-friendly-order":

template<class VertexProperties=no_property, class EdgeProperties=no_property, class OutEdgeList=vecS, VertexList=vecS, Directed=directedS, GraphProperties= no_property, EdgeList=listS>
make_swiss_army_knife_graph()

So the example code becomes simply:

auto graph1 = make_swiss_army_knife_graph<>();

using vertex_info = std::string;
using edge_info = bool;
auto graph2 = make_swiss_army_knife_graph<vertex_info, edge_info>();

2. To simplify the Chosing graph type page, why not simply draw a Decision Tree for each template parameter type? Defaulted types like OutEdgeList=vecS could be shown as green boxes at the end of the tree. Mermaid could make this easy and git-abled:

graph TD;
    A[OutEdgeList]-->B{Avoid multigraphs?};
    B-- No -->C[vecS];
    B-- Yes-->D[setS];
    classDef green fill:#9f6,stroke:#333,stroke-width:2px;
    class C green;

Loading

3. I personally had to write this to remain clear on the choices I made, maybe do the same in the documentation examples?

    ///
    /// @brief Defines the desired graph properties and constraints for a coalescent tree
    ///
    struct tree_traits
    {
        /// @brief Trees are sparse graph in nature, adjacency_matrix would not be justified here
        template <class... Types>
        using model = boost::adjacency_list<Types...>;

        /// @brief We want to enforce avoiding multi-graphs (edges with same end nodes)
        using out_edge_list_type = boost::setS;

        /// @brief We don't allow for inserting vertices except at the end and we don't remove vertices.
        ///        This means that neither reallocation cost nor stability are reasons for preferring listS to vecS.
        using vertex_list_type = boost::vecS;

        /// @brief Coalescent trees are directed acyclic graphs but we need bidirectionality for in-edges access
        /// @remark Bidirectionality trades off storage/insertion overhead for the ability to get in-edges
        ///         and in-degree without having to enumerate all vertices or edges
        using directed_type = boost::bidirectionalS;
    };

Discoverability of free functions

Existing limitations

Users struggle to discover free functions callable of their graph type

Possible solutions

1. More examples: while waiting for tooling/Intellisense to catch up, it may be worth putting together examples that actually invoke the related functions. If an example exists for a Bidirected Graph, it should document its valid expressions: Doxygen (?) would make the function clickable, redirecting to its documentation.
2. In [Graph Concepts page](the https://www.boost.org/doc/libs/1_82_0/libs/graph/doc/graph_concepts.html), replace the old Illustration 1 with a clickable Mermaid graph redirecting towards the concept interface.
3. Graph Concepts documents the requirements of algorithms. Most often, new users just want to know what functions can be invoked on their type of graph. This is made cumbersome by the fact they have to wait section 18 (!!!) to discover the interface of the graph classes.
   1. Move section 18 much closer to the top of the ToC, somewhere between Quick Tour and Examples.
   2. Section 9.2 (Using adjacency List) is redundant with section 18.1 and confuses discoverability.
   3. Make explicit references to the interface documentation: any mention to adjacency_list should link to its interface documentation. This includes references in the mermaid graphs so that users could e.g. check what interface they get while selecting their graph type in the decision graph.
   4. Compared to cppreference the interface listing is much less dense: this decreases the amount of information one navigate on a single glance, requires more scrolling, and hinders discoverability
      1. decrease font size and table spacing
      2. highlight function names with a different color than their doc string
      3. Put both function and doc string on the same line, as cppreference does

Bundled, Internal, External Properties Confusion

Existing limitations

New users struggle to understand the difference between Bundled vs External Properties

Possible solutions

If bundled properties are the best or easiest way to go for newcomers, then the documentation should present it as the only way to go, and make it easy for newcomers to leverage them through clear and self-contained examples.

If edge-cases and performance justify the use of external properties, then it should be part of a Optimization and Performance section, Properties management subsection.