Krdytkyu

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!