Tukukkk

In my previous post I made rather dull (and, as it turns out, bluntly wrong) attempt at solving the problem:

Generate a maze with $N$ nodes, $K<N$ of which are border nodes. Each border must have degree of $m$, and each non-border node must have degree of $p>m$. The generated maze must be a minimally connected graph. Duplicating edges is not allowed (each pair of nodes can have only zero or one edge).

Algorithm:

My algorithm generates disconnected nodes first, sorted by their indices. Memory for neighbor indices is managed semi-manually, because I believe that on smaller neighbor count standard memory allocator becomes less efficient (to be checked). Satisfied nodes are the ones which have required number of edges in place.

-1. head <- first of nodes

-2. while head is not at end of nodes:

---2.1. neighbor <- last element of nodes

---2.2. while *head is not satisfied

-----2.2.1. connect *head and *neighbor

-----2.2.2. advance neighbor towards head (decrement)

---2.3. if *head is not satisfied, return empty maze

---2.4. Advance head towards end

---2.5. Sort range [head, end of nodes) (comparison function below)

-3. Return built maze

When comparing, it is important to put the most constraining nodes first. It will allow to exit early if the maze is impossible to generate. The most constraining node is a node which has more fill percentage ($frac{Current}{Required}$).

Note that instead of doing division, I do multiplication:

$frac{Current1}{Required1}<frac{Current2}{Required2}$

is the same as

$Current1*Required2<Current2*Required1$

What is different compared to previous solution?

Well, everything. I believe I included all suggestions by @Edward, but there might be some incompatibilities, due to the fact that algorithm is very different.

This solution won't break a sweat on 100'000 edges, but performance heavily depends on the node count, as the sorting step is the most time-consuming. It also doesn't duplicate edges, and doesn't crash due to stackoverflow, and is better in many other ways from end user's perspective. But the code is ... well, it is in the concerns section.

Code

#ifndef MAZE_GENERATOR_MAZE_HPP

#define MAZE_GENERATOR_MAZE_HPP



#include <algorithm>

#include <cstddef>

#include <vector>

#include <memory>

#include <optional>



class maze {

public:

    struct node {

        std::size_t index = 0;

        std::size_t* neighbor_indices = nullptr;

        std::size_t filled_count = 0;

    };



private:

    std::vector<node> nodes;

    std::unique_ptr<std::size_t> neighbors_storage;



    maze() = default;

    maze(std::vector<node>&& nodes, std::unique_ptr<std::size_t>&& neighbors_storage):

        nodes(std::move(nodes)),

        neighbors_storage(std::move(neighbors_storage)) {}

public:

    class maze_builder {

        std::size_t _node_count;

        std::size_t _border_count;

        std::size_t _border_edge_count;

        std::size_t _nonborder_edge_count;

    public:

        maze_builder& of_size(std::size_t node_count) {

            _node_count = node_count;

            return *this;

        }



        maze_builder& with_borders(std::size_t border_count, std::size_t border_edge_count) {

            _border_count = border_count;

            _border_edge_count = border_edge_count;

            return *this;

        }



        maze_builder& with_typical_nodes(std::size_t nonborder_edge_count) {

            _nonborder_edge_count = nonborder_edge_count;

            return *this;

        }



        std::optional<maze> try_build() {

            return maze::try_build(_node_count, _border_count, _border_edge_count, _nonborder_edge_count);

        }

    };



    const std::vector<node>& get_nodes() const {

        return nodes;

    }



    static std::optional<maze> try_build(std::size_t node_count, std::size_t border_count,

                                  std::size_t border_edge_count, std::size_t nonborder_edge_count) {

        auto is_border_index = [border_count](std::size_t index) {return index < border_count;};

        auto is_satisfied = [border_edge_count, nonborder_edge_count, is_border_index](node& n) {

            if (is_border_index(n.index)) {

                return n.filled_count == border_edge_count;

            } else {

                return n.filled_count == nonborder_edge_count;

            }

        };

        auto is_over_satisfied = [border_edge_count, nonborder_edge_count, is_border_index](node& n) {

            if (is_border_index(n.index)) {

                return n.filled_count > border_edge_count;

            } else {

                return n.filled_count > nonborder_edge_count;

            }

        };

        auto node_cmp = [is_border_index, border_edge_count, nonborder_edge_count](const node& lhs, const node& rhs) {

            bool is_lhs_border = is_border_index(lhs.index);

            bool is_rhs_border =  is_border_index(rhs.index);

            auto required_lhs = is_lhs_border ? border_edge_count : nonborder_edge_count;

            auto required_rhs = is_rhs_border ? border_edge_count : nonborder_edge_count;

            return lhs.filled_count * required_rhs > rhs.filled_count * required_lhs;

        };





        std::vector<node> nodes(node_count);

        const std::size_t nonborder_count = nodes.size() - border_count;

        const std::size_t total_neighbor_count =

                nonborder_count * nonborder_edge_count + border_count * border_edge_count;

        auto neighbors_storage = std::make_unique<std::size_t>(total_neighbor_count);

        std::size_t* storage = neighbors_storage.get();

        for (std::size_t i = 0; i < nodes.size(); ++i) {

            nodes[i].index = i;

            nodes[i].neighbor_indices = storage;

            storage += (is_border_index(i)) ?

                    border_edge_count :

                    nonborder_edge_count;

        }



        auto head = nodes.begin();

        while (head != nodes.end()) {

            auto neighbor = std::prev(nodes.end());

            while (neighbor != head && !is_satisfied(*head)) {

                if (is_over_satisfied(*neighbor)) {

                    throw std::logic_error("oversatisfied node found");

                }

                add_edge(*head, *neighbor);

                --neighbor;

            }

            if (!is_satisfied(*head)) {

                return {};

            }

            ++head;

            std::sort(head, nodes.end(), node_cmp);

        }



        std::sort(nodes.begin(), nodes.end(), (const node& lhs, const node& rhs) {

            return lhs.index < rhs.index;

        });

        std::optional<maze> result;

        result = maze(std::move(nodes), std::move(neighbors_storage));

        return result;

    }



    maze_builder builder() {

        return {};

    }



private:

    static void add_edge(node& from, node& to) {

        from.neighbor_indices[from.filled_count++] = to.index;

        to.neighbor_indices[to.filled_count++] = from.index;

    }

};



#endif //MAZE_GENERATOR_MAZE_HPP

#include <unordered_set>

#include <chrono>

#include <iostream>

#include <queue>



void add_all_neighbors(std::queue<std::size_t>& to_visit, const maze::node& node) {

    for (std::size_t i = 0; i < node.filled_count; ++i) {

        to_visit.push(node.neighbor_indices[i]);

    }

}



bool is_minimally_connected(const maze& m) {

    const auto& nodes = m.get_nodes();

    std::vector<char> visited(nodes.size());

    visited[0] = true;

    std::queue<std::size_t> to_visit;

    add_all_neighbors(to_visit, nodes[0]);



    while (!to_visit.empty()) {

        auto visit_target = to_visit.front();

        to_visit.pop();

        if (visited[visit_target]) {

            continue;

        }

        visited[visit_target] = true;

        add_all_neighbors(to_visit, nodes[visit_target]);

    }



    return std::all_of(visited.begin(), visited.end(), (char flag){return flag;});

}







bool repeats_connections(const maze& m) {

    const auto& nodes = m.get_nodes();

    for (const auto& node: nodes) {

        std::unordered_set<std::size_t> unique_indices;

        for (std::size_t i = 0; i < node.filled_count; ++i) {

            unique_indices.insert(node.neighbor_indices[i]);

        }

        if (unique_indices.size() != node.filled_count) {

            return true;

        }

    }

    return false;

}



int main(int argc, char* argv) {

    if (argc != 5) {

        std::cerr << "usage: program node_count border_count border_edge_count non_border_edge_count " 

                  << 'n';

        return -1;

    }



    std::size_t node_count = std::stoul(argv[1]);

    std::size_t border_count = std::stoul(argv[2]);

    std::size_t border_edge_count = std::stoul(argv[3]);

    std::size_t non_border_edge_count = std::stoul(argv[4]); //sometimes also referred as just node edge count



    namespace ch = std::chrono;

    auto start_time = ch::system_clock::now();

    auto solution = maze::try_build(node_count, border_count, border_edge_count, non_border_edge_count);

    auto end_time = ch::system_clock::now();

    if (solution.has_value()) {

        std::cout << "found!n";

        if (!is_minimally_connected(solution.value())) {

            std::cout << "false positive, maze is not minimally connectedn";

        }

        if (repeats_connections(solution.value())) {

            std::cout << "false positive, some nodes duplicate connectionsn";

        }

    } else {

        std::cout << "not found!n";

    }

    std::cout << "completed in "

              << ch::duration_cast<ch::milliseconds>(end_time - start_time).count() << " millisecondsn";



}

Concerns

• 
  

  Too many lambdas hanging around

  
  
  

  They can't be static functions, as they require current arguments. I thought about using javascript style function that returns a lambda which stores current state, but it looked weird.

  
  


• 
  

  Unusable interface

  
  
  

  I tried to change it in some places, but in the end I end up either not being able to have necessary control (create, access all nodes), or unable to test the code. At the moment testing the code is very hard and requires intrusion.

  
  

Any other comments are welcome!

std::size_t node_count = std::stoul(argv[1]);

I agree with the commenter who said (more or less) "don't write std::size_t when size_t will do." And I'll go further, and point out that most of your uses of size_t are unnecessary. For example, above, you're using std::stoul, which returns an unsigned long; so implicitly converting it to size_t is maybe a little sketchy. What if size_t is smaller than unsigned long? (Unlikely.) What if it's bigger? (Possible.)

As soon as you start thinking about boundary conditions, you realize that actually it's highly unlikely that your program will ever be called upon to deal with 2 billion nodes at a time. So you can just use int and std::stoi (or even atoi). And then:

struct node {

    int index = 0;

    int* neighbor_indices = nullptr;

    int filled_count = 0;

};

Boom, you've just cut your memory usage in half!

You write:

Memory for neighbor indices is managed semi-manually, because I believe that on smaller neighbor count standard memory allocator becomes less efficient (to be checked).

Nope, you definitely believe incorrectly. Just use std::vector<int>. It'll save you a lot of grief.

struct node {

    int index = 0;

    std::vector<int> neighbor_indices;

    // "filled_count" becomes "neighbor_indices.size()"

};

And then you can get rid of all this stuff:

auto neighbors_storage = std::make_unique<std::size_t>(total_neighbor_count);

std::size_t* storage = neighbors_storage.get();

because each node will be managing its own vector. Grief: saved.

            if (is_over_satisfied(*neighbor)) {

                throw std::logic_error("oversatisfied node found");

            }

Nit: You spell it oversatisfied in the error message, but over_satisfied (two words) in the function name. Pick a spelling and stick to it! (I recommend oversatisfied, one word.)

    auto node_cmp = [is_border_index, border_edge_count, nonborder_edge_count](const node& lhs, const node& rhs) {

        bool is_lhs_border = is_border_index(lhs.index);

        bool is_rhs_border =  is_border_index(rhs.index);

        auto required_lhs = is_lhs_border ? border_edge_count : nonborder_edge_count;

        auto required_rhs = is_rhs_border ? border_edge_count : nonborder_edge_count;

        return lhs.filled_count * required_rhs > rhs.filled_count * required_lhs;

    };

Because this lambda is only ever used in one place, you can move its definition in-line. And because it doesn't escape upward from the current scope, you don't need it to capture anything by-copy. Lambdas that are used as callbacks (but do not escape upward) should always capture [&] and nothing else. So:

    std::sort(head, nodes.end(), [&](const node& lhs, const node& rhs) {

        bool is_lhs_border = is_border_index(lhs.index);

        bool is_rhs_border =  is_border_index(rhs.index);

        auto required_lhs = is_lhs_border ? border_edge_count : nonborder_edge_count;

        auto required_rhs = is_rhs_border ? border_edge_count : nonborder_edge_count;

        return lhs.filled_count * required_rhs > rhs.filled_count * required_lhs;

    });

Finally, we can remove some error-prone code duplication by factoring out the "key function." I haven't really thought this through, but I think the following is equivalent to what you had. (It's tricky because you were multiplying parts of lhs with parts of rhs. I'm not intuitively convinced that the function you had defined a consistent ordering at all!)

    auto key = [&](const node& n) {

        return n.filled_count * (is_border_index(n.index) ? nonborder_edge_count : border_edge_count);

    };

    std::sort(head, nodes.end(), [&](const node& lhs, const node& rhs) {

        return key(lhs) > key(rhs);

    });

Alternatively, pull out each sort-predicate and give it a descriptive name. For example, instead of

    std::sort(nodes.begin(), nodes.end(), (const node& lhs, const node& rhs) {

        return lhs.index < rhs.index;

    });

I might write

    auto by_index = (const node& lhs, const node& rhs) { return lhs.index < rhs.index; };

    // ...

    std::sort(nodes.begin(), nodes.end(), by_index);

Rigorously following this style can force you to clarify your thinking process. When you sort using the predicate above — the one with the multiplication involving both lhs and rhs — what are you sorting by? If you can't name it, you probably don't understand it.

std::size_t _node_count;

How come maze_builder's private data members get decorated with underscores, but maze's private data members don't? That seems inconsistent. Also, the traditional C++ style is to put the underscore at the end of the identifier, not at the beginning. (Avoid leading underscores!)

std::vector<char> visited(nodes.size());

visited[0] = true;

If you're storing true and false in this vector, it should probably be a vector<bool>, not a vector<char>. Or if you're deliberately avoiding vector<bool> because of how wacky it is, you should leave a comment explaining that that's what's happening — and also, explain what would go wrong if you used vector<bool>.

    std::optional<maze> result;

    result = maze(std::move(nodes), std::move(neighbors_storage));

    return result;

This is a very verbose way of writing

    return maze(std::move(nodes), std::move(neighbors_storage));

In fact, it sure looks like you don't need to be returning optional<maze> from this function at all! There's no way for it to return std::nullopt; it invariably returns a maze object (or throws).

...ooh. Actually, there's a return {}; hiding in the middle, which in the case of optional actually means "return the empty optional," i.e. return std::nullopt;. That's quite sneaky. I strongly recommend (A) throwing an exception instead, since you're already using exceptions to report errors in this function; or at least (B) spelling out std::nullopt instead of hiding it in punctuation.

maze_builder builder() {

    return {};

}

This is dead code. Remove it.

    auto is_border_index = [border_count](std::size_t index) {return index < border_count;};

    auto is_satisfied = [border_edge_count, nonborder_edge_count, is_border_index](node& n) {

        if (is_border_index(n.index)) {

            return n.filled_count == border_edge_count;

        } else {

            return n.filled_count == nonborder_edge_count;

        }

    };

    auto is_over_satisfied = [border_edge_count, nonborder_edge_count, is_border_index](node& n) {

        if (is_border_index(n.index)) {

            return n.filled_count > border_edge_count;

        } else {

            return n.filled_count > nonborder_edge_count;

        }

    };

Same comment as above, about lambdas that should be capturing [&]. Also, it would be easier to follow the logic if you identified the duplicated code snippets and factored them out. So for example:

auto edge_count = [&](const node& n) { return (n.index < border_count) ? border_edge_count : nonborder_edge_count; };

auto is_satisfied = [&](const node& n) { return n.filled_count == edge_count(n); };

auto is_oversatisfied = [&](const node& n) { return n.filled_count > edge_count(n); };

And remember your const-correctness!

    maze_builder& of_size(std::size_t node_count) {

        _node_count = node_count;

        return *this;

    }

Interesting, and correct enough; but I don't see this function actually getting used anywhere. In fact, I guess this entire maze_builder thing is dead code, right? Remove it.

maze(std::vector<node>&& nodes, std::unique_ptr<std::size_t>&& neighbors_storage):

    nodes(std::move(nodes)),

    neighbors_storage(std::move(neighbors_storage)) {}

Two things:

• Never pass smart pointers (or regular pointers, or iterators, or allocators) by reference. Pass by value. Well-written C++ code looks like Python; if you see yourself writing lots of &&, you might be doing it wrong.




• Always make your constructors explicit, unless you have a specific reason to enable the implicit conversion.

These are small things, but they make a big difference.

explicit maze(std::vector<node> nodes, std::unique_ptr<std::size_t> neighbors_storage):

    nodes(std::move(nodes)),

    neighbors_storage(std::move(neighbors_storage)) {}

This has gone on long enough, so I'll stop. I think the biggest problem with this program as presented here is that about half of it is dead code. The second-biggest problem (a distant second) is a tie between all those lambdas that unnecessarily capture things-that-aren't-[&], and all those std::size_ts that should be int.