Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <set>
- /* using std::set */
- #include <map>
- /* using std::map */
- #include <array>
- /* using std::array */
- #include <memory>
- /* using std::shared_ptr, std::make_shared, std::enable_shared_from_this,
- * std::weak_ptr */
- #include <utility>
- /* using std::move, std::pair, std::make_pair */
- #include <cassert>
- /* using assert */
- #include <iostream>
- /* using std::cout */
- namespace graph {
- class vertex;
- struct vertexcmp
- {
- bool operator()(const std::shared_ptr<vertex>& first,
- const std::shared_ptr<vertex>& second) const noexcept;
- bool operator()(const std::weak_ptr<vertex>& first,
- const std::weak_ptr<vertex>& second) const noexcept
- {
- return (*this)(first.lock(), second.lock());
- }
- };
- using vertexset = std::set<std::shared_ptr<vertex>, vertexcmp>;
- using backrefset = std::set<std::weak_ptr<vertex>, vertexcmp>;
- struct vertex: std::enable_shared_from_this<vertex>
- {
- vertexset children;
- backrefset parents;
- const int id;
- vertex(int id) noexcept
- : id(id)
- {}
- vertex(const vertex&) = delete;
- vertex(vertex&&) = default;
- bool add_child(const std::shared_ptr<vertex>& child)
- {
- assert(child);
- if(! children.insert(child).second)
- return false; /* already a child */
- std::weak_ptr<vertex> self(this->shared_from_this());
- bool newparent = child->parents.insert(std::move(self)).second;
- assert(newparent);
- return true;
- }
- bool remove_child(const std::shared_ptr<vertex>& child) noexcept
- {
- assert(child);
- if(! children.erase(child))
- return false;
- std::weak_ptr<vertex> self(this->shared_from_this());
- bool wasparent = child->parents.erase(std::move(self));
- assert(wasparent);
- return true;
- }
- };
- bool vertexcmp::operator()(const std::shared_ptr<vertex>& first,
- const std::shared_ptr<vertex>& second) const noexcept
- {
- assert(first && second);
- return first->id < second->id;
- }
- using edge = std::pair<int, int>;
- using edgeset = std::set<edge>;
- void walk_graph(const std::shared_ptr<vertex>& node, edgeset& walked) noexcept
- {
- assert(node);
- const vertexset& children = node->children;
- int id = node->id;
- for(const std::shared_ptr<vertex>& child: children) {
- assert(child);
- int childid = child->id;
- bool notvisited = walked.insert(std::make_pair(id, childid)).second;
- if(notvisited) {
- std::cout << id << " -> " << childid << "\n";
- walk_graph(child, walked);
- }
- }
- }
- using vertexmap = std::map<int, std::shared_ptr<vertex> >;
- struct graphset
- {
- vertexmap vertexes;
- std::shared_ptr<vertex>& operator[](int id)
- {
- std::shared_ptr<vertex>& node = vertexes[id];
- if(node)
- assert(node->id == id);
- else
- node = std::make_shared<vertex>(id);
- return node;
- }
- bool add_edge(int from, int to)
- {
- std::shared_ptr<vertex>& parent = (*this)[from];
- std::shared_ptr<vertex>& child = (*this)[to];
- return parent->add_child(child);
- }
- };
- template<std::size_t n>
- using edge_array = std::array<edge, n>;
- }
- int main()
- {
- graph::graphset testgraph;
- static constexpr graph::edge_array<6> edges {
- graph::edge{0, 1},
- graph::edge{0, 4},
- graph::edge{1, 2},
- graph::edge{1, 3},
- graph::edge{1, 4},
- graph::edge{2, 3},
- };
- for(const graph::edge& e: edges)
- testgraph.add_edge(e.first, e.second);
- graph::edgeset walked;
- graph::walk_graph(testgraph[0], walked);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement