1#ifndef JNGEN_INCLUDE_GRAPH_INL_H2#error File "graph_inl.h" must not be included directly.3#include "../graph.h" // for completion emgine4#endif56#include "../array.h"7#include "../common.h"8#include "../printers.h"910namespace jngen {1112namespace graph_detail {1314Graph BuilderProxy::g() const {15    return builder_(traits_);16}1718BuilderProxy::operator Graph() const {19    return g();20}2122class GraphRandom {23    using BuilderProxy = graph_detail::BuilderProxy;24    using Traits = graph_detail::Traits;2526public:27    GraphRandom() {28        static bool created = false;29        ensure(!created, "jngen::GraphRandom should be created only once");30        created = true;31    }3233    static BuilderProxy random(int n, int m) {34        ensure(35            n >= 0 && m >= 0,36            "Number of vertices and edges in the graph must be nonnegative");37        checkLargeParameter(n);38        checkLargeParameter(m);39        return BuilderProxy(Traits(n, m), &doRandom);40    }4142    static BuilderProxy complete(int n) {43        ensure(44            n >= 0,45            "Number of vertices and edges in the graph must be nonnegative");46        checkLargeParameter(n * n);47        return BuilderProxy(Traits(n), [](Traits t) {48            Graph g;49            g.setN(t.n);50            if (t.directed) {51                g.directed_ = true;52            }53            for (int i = 0; i < t.n; ++i) {54                for (int j = 0; j <= i; ++j) {55                    if (i == j) {56                        if (t.allowLoops) {57                            g.addEdge(i, j);58                        }59                        continue;60                    }6162                    if (t.directed) {63                        if (t.acyclic) {64                            g.addEdge(i, j);65                        } else if (t.allowAntiparallel) {66                            g.addEdge(i, j);67                            g.addEdge(j, i);68                        } else {69                            if (rnd.next(2)) {70                                g.addEdge(i, j);71                            } else {72                                g.addEdge(j, i);73                            }74                        }75                    } else {76                        g.addEdge(i, j);77                    }78                }79            }80            g.normalizeEdges();81            return g;82        });83    }8485    static BuilderProxy empty(int n) {86        ensure(87            n >= 0,88            "Number of vertices and edges in the graph must be nonnegative");89        checkLargeParameter(n);90        return BuilderProxy(Traits(n), [](Traits t) {91            ensure(92                t.n <= 1 || !t.connected,93                "Empty graph on >1 vertices cannot be connected");94            Graph g;95            if (t.directed) {96                g.directed_ = true;97            }98            g.setN(t.n);99            return g;100        });101    }102103    static BuilderProxy cycle(int n) {104        ensure(105            n >= 0,106            "Number of vertices and edges in the graph must be nonnegative");107        checkLargeParameter(n);108        return BuilderProxy(Traits(n), [](Traits t) {109            Graph g;110            if (t.directed) {111                g.directed_ = true;112                ensure(!t.acyclic, "Cannot generate acyclic cycle");113            }114            for (int i = 0; i < t.n; ++i) {115                g.addEdge(i, (i+1)%t.n);116            }117            g.normalizeEdges();118            return g;119        });120    }121122    static BuilderProxy randomStretched(123            int n, int m, int elongation, int spread)124    {125        ensure(126            n >= 0 && m >= 0,127            "Number of vertices and edges in the graph must be nonnegative");128        checkLargeParameter(n);129        checkLargeParameter(m);130        return BuilderProxy(Traits(n, m), [elongation, spread](Traits t) {131            return doRandomStretched(t, elongation, spread);132        });133    }134135    static BuilderProxy randomBipartite(int n1, int n2, int m) {136        ensure(137            n1 >= 0 && n2 >= 0 && m >= 0,138            "Number of vertices and edges in the graph must be nonnegative");139        checkLargeParameter(n1 + n2);140        checkLargeParameter(m);141        return BuilderProxy(Traits(0, m), [n1, n2](Traits t) {142                return doRandomBipartite(t, n1, n2);143        });144    }145146147    static BuilderProxy completeBipartite(int n1, int n2) {148        ensure(149            n1 >= 0 && n2 >= 0,150            "Number of vertices and edges in the graph must be nonnegative");151        checkLargeParameter(n1 * n2);152        return BuilderProxy(Traits(0, 0), [n1, n2](Traits t) {153            ensure(!t.directed, "Directed bipartite graphs are not supported");154155            Arrayp edges;156            edges.reserve(n1 * n2);157            for (int u = 0; u < n1; ++u) {158                for (int v = 0; v < n2; ++v) {159                    edges.emplace_back(u, v + n1);160                }161            }162163            Graph g;164            g.initWithEdges(n1 + n2, edges);165            return g;166        });167    }168169private:170    static Graph doRandom(Traits t) {171        int n = t.n;172        int m = t.m;173174        if (!t.allowMulti) {175            ensure(m <= maxEdges(n, t), "Too many edges in the graph");176        }177178        std::unordered_set<std::pair<int, int>> usedEdges;179180        if (t.connected) {181            ensure(m >= n - 1, "Not enough edges for a connected graph");182            auto treeEdges = Tree::random(n).edges();183            if (t.directed) {184                for (auto& edge: treeEdges) {185                    if (rnd.next(2)) {186                        std::swap(edge.first, edge.second);187                    }188                }189            }190            usedEdges.insert(treeEdges.begin(), treeEdges.end());191            ENSURE(usedEdges.size() == static_cast<size_t>(n - 1));192        }193194        auto edgeIsGood = [&usedEdges, t](std::pair<int, int> edge) {195            if (!t.allowMulti && usedEdges.count(edge)) {196                return false;197            }198            if (t.directed && !t.allowAntiparallel &&199                    usedEdges.count({edge.second, edge.first}))200            {201                return false;202            }203            return true;204        };205206        Arrayp result(usedEdges.begin(), usedEdges.end());207        result.reserve(m);208209        while (result.size() < static_cast<size_t>(m)) {210            auto edge = randomEdge(n, t);211            if (edgeIsGood(edge)) {212                usedEdges.insert(edge);213                result.push_back(edge);214            }215        }216217        Graph graph;218219        if (t.directed && t.acyclic) {220            makeAcyclic(result);221        }222        if (t.directed) {223            graph.directed_ = true;224        }225226        graph.initWithEdges(n, result);227        return graph;228    }229230    static Graph doRandomStretched(Traits t, int elongation, int spread) {231        Tree tree = Tree::randomPrim(t.n, elongation);232        Array parents = tree.parents(0);233        parents[0] = 0;234235236        auto treeEdges = tree.edges();237        if (t.directed && !t.acyclic) {238            for (auto& edge: treeEdges) {239                if (rnd.next(2)) {240                    std::swap(edge.first, edge.second);241                }242            }243        }244245        Arrayp edges = treeEdges;246        edges.reserve(t.m);247248        std::unordered_set<std::pair<int, int>> usedEdges(249            treeEdges.begin(), treeEdges.end());250251        auto edgeIsGood = [&usedEdges, t](std::pair<int, int> edge) {252            if (!t.allowMulti && usedEdges.count(edge)) {253                return false;254            }255            if (t.directed && !t.allowAntiparallel &&256                    usedEdges.count({edge.second, edge.first}))257            {258                return false;259            }260            return true;261        };262263        constexpr size_t MAX_ATTEMPTS = 1000;264        size_t attemptsToFail = MAX_ATTEMPTS;265266        while (static_cast<int>(edges.size()) != t.m) {267            if (--attemptsToFail == 0) {268                ensure(false, format("Cannot generate random stretched graph "269                    "with parameters %d, %d, %d, %d",270                    t.n, t.m, elongation, spread));271            }272            int u = rnd.next(t.n);273            int up = rnd.next(0, spread);274            int v = u;275            for (int iter = 0; iter < up; ++iter) {276                v = parents[v];277            }278279            ENSURE(v <= u);280281            if (!t.allowLoops && u == v) {282                continue;283            }284285            if (!edgeIsGood({v, u})) {286                continue;287            }288289            if (t.directed && !t.acyclic && rnd.next(2)) {290                std::swap(u, v);291            }292293            edges.emplace_back(v, u);294            attemptsToFail = MAX_ATTEMPTS;295        }296297        Graph graph;298        if (t.directed) {299            graph.directed_ = true;300        }301302        graph.initWithEdges(t.n, edges);303        return graph;304    }305306    static Graph doRandomBipartite(Traits t, int n1, int n2) {307        int m = t.m;308309        if (!t.allowMulti) {310            ensure(m <= static_cast<long long>(n1) * n2,311                    "Too many edges in the graph");312        }313314        ensure(!t.directed, "Directed bipartite graphs are not supported");315316        std::unordered_set<std::pair<int, int>> usedEdges;317318        if (t.connected) {319            ensure(m >= n1 + n2 - 1, "Not enough edges for a connected graph");320            auto pruferCode = Array::random(n2 - 1, 0, n1 - 1) +321                Array::random(n1 - 1, n1, n1 + n2 - 1);322            pruferCode.shuffle();323            auto treeEdges = Tree::fromPruferSequence(pruferCode).edges();324            usedEdges.insert(treeEdges.begin(), treeEdges.end());325            ENSURE(usedEdges.size() == static_cast<size_t>(n1 + n2 - 1));326        }327328        auto edgeIsGood = [&usedEdges, t](std::pair<int, int> edge) {329            if (!t.allowMulti && usedEdges.count(edge)) {330                return false;331            }332            if (t.directed && !t.allowAntiparallel &&333                    usedEdges.count({edge.second, edge.first}))334            {335                return false;336            }337            return true;338        };339340        Arrayp result(usedEdges.begin(), usedEdges.end());341        result.reserve(m);342343        while (result.size() < static_cast<size_t>(m)) {344            int u = rnd.next(0, n1 - 1);345            int v = rnd.next(n1, n1 + n2 - 1);346            std::pair<int, int> edge(u, v);347            if (edgeIsGood(edge)) {348                usedEdges.insert(edge);349                result.push_back(edge);350            }351        }352353        Graph graph;354355        graph.initWithEdges(n1 + n2, result);356        return graph;357    }358359    static std::pair<int, int> randomEdge(int n, const Traits& t) {360        return rnd.nextp(n, RandomPairTraits{!t.directed, !t.allowLoops});361    }362363    static long long maxEdges(int n, const Traits& t) {364        ENSURE(!t.allowMulti);365        long long res = static_cast<long long>(n) * (n-1);366        if (!(t.directed && t.allowAntiparallel)) {367            res /= 2;368        }369        if (t.allowLoops) {370            res += n;371        }372        return res;373    }374375    static void makeAcyclic(Arrayp& edges) {376        auto numbering = Array::id(edges.size()).shuffle();377        for (auto& edge: edges) {378            if (numbering[edge.first] > numbering[edge.second]) {379                std::swap(edge.first, edge.second);380            }381        }382    }383};384385} // namespace graph_detail386387Graph::BuilderProxy Graph::random(int n, int m) {388    return graph_detail::GraphRandom::random(n, m);389}390391Graph::BuilderProxy Graph::complete(int n) {392    return graph_detail::GraphRandom::complete(n);393}394395Graph::BuilderProxy Graph::empty(int n) {396    return graph_detail::GraphRandom::empty(n);397}398399Graph::BuilderProxy Graph::cycle(int n) {400    return graph_detail::GraphRandom::cycle(n);401}402403Graph::BuilderProxy Graph::randomStretched(404        int n, int m, int elongation, int spread) {405    return graph_detail::GraphRandom::randomStretched(n, m, elongation, spread);406}407408Graph::BuilderProxy Graph::randomBipartite(int n1, int n2, int m) {409    return graph_detail::GraphRandom::randomBipartite(n1, n2, m);410}411412Graph::BuilderProxy Graph::completeBipartite( int n1, int n2) {413    return graph_detail::GraphRandom::completeBipartite(n1, n2);414}415416} // namespace jngen