Список Смежности На C++14


Я хотел бы создать библиотеку графа для развлечений, так и запускать различные алгоритмы поиска на нем. Сейчас у меня есть список смежности, который я бросил вместе. В настоящее время список смежности поддерживает только неориентированные графы.

узел.ч

#ifndef SN_GRAPH_NODE_H
#define SN_GRAPH_NODE_H

#include <ostream>
#include <istream>

/////////////////
// struct Node //
/////////////////
//
// A simple graph node, just holds data.
// Can have counts, colors, is_visited, and other attributes later.
template <typename T>
struct Node
{
    T data;

    Node(const T &data) : data(data)
    {
    }
};

template <typename T>
bool operator<(const Node<T> &lhs, const Node<T> &rhs)
{
    return lhs.data < rhs.data;
}

template <typename T>
bool operator==(const Node<T> &lhs, const Node<T> &rhs)
{
    return lhs.data == rhs.data;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const Node<T> &node)
{
    os << node.data;
    return os;
}

template <typename T>
std::istream& operator>>(std::istream& is, Node<T> &node)
{
    is >> node.data;
    return is;
}

#endif

края.ч

#ifndef SN_GRAPH_EDGE_H
#define SN_GRAPH_EDGE_H

#include "node.h"
#include <stdexcept>

template <typename T>
struct Edge
{
    using node_type = Node<T>;
    node_type &n1;
    node_type &n2;
    int cost = 1;

    Edge(node_type &node1, node_type &node2)
        : n1(node1), n2(node2)
    {
    }

    Edge(node_type &node1, node_type &node2, int cost)
        : n1(node1), n2(node2), cost(cost)
    {
    }

    auto other(const node_type& node) -> node_type&
    {
        if (node == n1) {
            return n2;
        }

        else if (node == n2) {
            return n1;
        }

        throw std::invalid_argument("[Edge::other] Cannot find node.");
    }

    auto other(const node_type& node) const -> const node_type&
    {
        if (node == n1) {
            return n2;
        }

        else if (node == n2) {
            return n1;
        }

        throw std::invalid_argument("[Edge::other] Cannot find node.");
    }
};

#endif

adjacency_list.ч

#ifndef SN_GRAPH_ADJACENCY_LIST_H
#define SN_GRAPH_ADJACENCY_LIST_H

#include "node.h"
#include "edge.h"
#include <ostream>
#include <stdexcept>
#include <vector>

// Assumes undirected graphs.
template <typename T>
class AdjacencyList
{
public:
    using node_type = Node<T>;
    using edge_type = Edge<T>;

    AdjacencyList()
    {
    }

    AdjacencyList(const std::vector<node_type> &vertices, const std::vector<edge_type> &edges)
    {
        create(vertices, edges);
    }

    auto getNeighbors(const Node<T> &node) const -> std::vector<Edge<T>>
    {
        auto &entry = find(node);
        return entry.neighbors;
    }

private:
    struct Entry
    {
        node_type node;
        std::vector<Edge<T>> neighbors;

        Entry(const node_type &node) : node(node)
        {
        }
    };

    friend std::ostream& operator<<(std::ostream& os, const Entry &entry)
    {
        os << entry.node << ": ";
        for (auto &&e : entry.neighbors) {
            auto other = e.other(entry.node);
            os << "(" << other << ", " << e.cost << "), ";
        }

        return os;
    }

    std::vector <Entry> entries;

    auto create(const std::vector<node_type> &vertices, const std::vector<edge_type> &edges) -> void
    {
        // Create entries for each vertex.
        for (auto &&v : vertices) {
            entries.emplace_back(v);
        }

        // Add neighbors to each vertex.
        for (auto &e : edges) {
            auto &entry1 = find(e.n1);
            entry1.neighbors.emplace_back(e);

            auto &entry2 = find(e.n2);
            entry2.neighbors.emplace_back(e);
        }

    }

    auto find(const node_type &node) -> Entry&
    {
        for(auto &entry : entries) {
            if (node == entry.node) {
                return entry;
            }
        }

        throw std::invalid_argument("[AdjacencyList::find] Could not find node.");
    }


    auto find(const node_type &node) const -> const Entry&
    {
        for(auto &entry : entries) {
            if (node == entry.node) {
                return entry;
            }
        }

        throw std::invalid_argument("[AdjacencyList::find] Could not find node.");
    }

    friend std::ostream& operator<<(std::ostream& os, const AdjacencyList &adjacencyList)
    {
        for (auto &&entry : adjacencyList.entries) {
            os << entry << '\n';
        }

        return os;
    }
};

#endif

Ниже приведен пример драйвера, который использует список смежности. Я положил его в поддиректории, поэтому включают в себя заявления, ссылается на родительский каталог.

test_adjacency_list.cpp

#include "../node.h"
#include "../edge.h"
#include "../adjacency_list.h"
#include <iostream>
#include <vector>

void test_create()
{
    Node<int> n1{1};
    Node<int> n2{2};
    Node<int> n3{3};
    Node<int> n4{4};

    Edge<int> e1(n1, n2);
    Edge<int> e2(n1, n3);
    Edge<int> e3(n2, n3);
    Edge<int> e4(n3, n4);

    auto adjacencyList = AdjacencyList<int> ({n1, n2, n3, n4}, {e1, e2, e3, e4});
    std::cout << adjacencyList << '\n';
}

int main()
{
    test_create();
}

Ожидаемые результаты:

1: (2, 1), (3, 1),
2: (1, 1), (3, 1),
3: (1, 1), (2, 1), (4, 1),
4: (3, 1),

Проблемы

  • Мой Edge класс хранит ссылки на два NodeС. Это кажется неправильным, но я не уверен, как еще это сделать. Я не чувствую себя Edge должны взять Nodes, так что я могу хранить ссылки или указатели. Я чувствую, что с помощью указателей это неправильно, хотя, потому что я не нужна ситуация, когда один из NodeЫ когда-нибудь nullptr.

  • Мой смежности список записи хранить Node и вектор Edgeдля этого Node. Это не как списки смежности, как правило, работают, но я хочу, чтобы хранить каким-то краем стоимость. Я мог бы создать структуру, NeighborEntry, который хранит соседа Node и стоимость, но я не уверен, если я набирает много от этого.

  • Я планирую выкинуть все в пространство имен позже.



207
1
задан 12 марта 2018 в 03:03 Источник Поделиться
Комментарии