Kylin/DataStructure/ListGraph.h

#ifndef LISTGRAPH_H
#define LISTGRAPH_H

#include "DynamicArray.h"
#include "Exception.h"
#include "Graph.h"
#include "LinkedList.h"

namespace Kylin {

template <typename VertexType, typename EdgeType>
class ListGraph : public Graph<VertexType, EdgeType> {
public:
    ListGraph(size_t n = 0) {
        for (unsigned int i = 0; i < n; i++) {
            addVertex();
        }
    }

    size_t addVertex() {
        auto v = new Vertex();
        if (v != nullptr) {
            m_vertexes.append(v);
            return m_vertexes.length() - 1;
        } else {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new vertex object ...");
        }
    }

    size_t addVertex(const VertexType &value) {
        auto ret = addVertex();
        setVertex(ret, value);
        return ret;
    }

    bool setVertex(size_t index, const VertexType &value) final {
        bool ret = ((0 <= index) && (index < vertexCount()));
        if (!ret) return false;
        auto vertex = m_vertexes.at(index);
        auto data = vertex->value;
        if (data == nullptr) data = new VertexType();
        if (data != nullptr) {
            *data = value;
            vertex->value = data;
        } else {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new vertex object ...");
        }
        return ret;
    }

    VertexType vertex(size_t index) const final {
        if (index >= vertexCount()) THROW_EXCEPTION(IndexOutOfBoundsException, "Index is out of bounds.");
        auto v = m_vertexes.at(index);
        if (v->value != nullptr) {
            return *(v->value);
        } else {
            THROW_EXCEPTION(InvalidOperationException, "No value assigned to this vertex ...");
        }
    }

    /**
     * @brief removeVertex 删除最近添加的Vertex和与之相关联的Edge
     */
    void removeVertex() {
        if (m_vertexes.size() <= 0)
            THROW_EXCEPTION(InvalidOperationException, "No vertex in current graph...");

        auto removeIndex = m_vertexes.length() - 1;
        auto removeVertex = m_vertexes.at(removeIndex);
        m_vertexes.removeAt(removeIndex);
        size_t index = 0;
        for (const auto &vertex : m_vertexes) {
            auto &edges = vertex->edges;
            auto pos = edges.indexOf(Edge<EdgeType>(index, removeIndex));
            if (pos != LinkedList<Vertex *>::npos) edges.removeAt(pos);
            index++;
        }
        delete removeVertex->value;
        delete removeVertex;
    }

    DynamicArray<size_t> adjacent(size_t index) const final {
        if ((0 <= index) && (index < vertexCount())) {
            auto vertex = m_vertexes.at(index);
            auto &edges = vertex->edges;
            DynamicArray<size_t> ret(edges.length());
            size_t index = 0;
            for (const auto &edge : edges) {
                ret[index++] = edge.end;
            }
            return ret;
        } else {
            THROW_EXCEPTION(InvalidParameterException, "Index is invalid...");
        }
    }

    std::optional<EdgeType> edge(size_t start, size_t end) const final {
        bool status = (start < vertexCount() && end < vertexCount());
        if (!status) return std::nullopt;
        auto &edges = m_vertexes.at(start)->edges;
        auto pos = edges.indexOf(Edge<EdgeType>(start, end));
        if (pos == LinkedList<Vertex *>::npos) return std::nullopt;
        return std::make_optional(edges.at(pos).value);
    }

    bool setEdge(size_t start, size_t end, const EdgeType &value) final {
        bool ret = ((0 <= start) && (start < vertexCount()) && (0 <= end) && (end < vertexCount()));
        if (!ret) return false;
        auto vertex = m_vertexes.at(start);
        auto &edges = vertex->edges;
        auto pos = edges.indexOf(Edge<EdgeType>(start, end));
        if (pos != LinkedList<Vertex *>::npos) {
            edges[pos] = Edge<EdgeType>(start, end, value);
        } else {
            edges.insert(0, Edge<EdgeType>(start, end, value));
        }
        return ret;
    }

    bool removeEdge(size_t start, size_t end) {
        bool ret = ((0 <= start) && (start < vertexCount()) && (0 <= end) && (end < vertexCount()));
        if (!ret) return false;
        auto vertex = m_vertexes.at(start);
        auto &edges = vertex->edges;
        auto pos = edges.indexOf(Edge<EdgeType>(start, end));
        if (pos != LinkedList<Vertex *>::npos) edges.removeAt(pos);
        return ret;
    }

    size_t vertexCount() const final { return m_vertexes.length(); }

    size_t edgeCount() const final {
        size_t ret = 0;
        for (const auto &vertex : m_vertexes) {
            ret += vertex->edges.length();
        }
        return ret;
    }

    size_t outDegree(size_t index) const final {
        size_t ret = 0;
        if ((0 <= index) && (index < vertexCount())) {
            ret = m_vertexes.at(index)->edges.length();
        } else {
            THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
        }
        return ret;
    }

    size_t inDegree(size_t index) const final {
        size_t ret = 0;
        if (index < 0 || index >= vertexCount())
            THROW_EXCEPTION(InvalidParameterException, "Index is invalid...");
        for (const auto &vertex : m_vertexes) {
            auto &edges = vertex->edges;
            for (const auto &edge : edges) {
                if (edge.end == index) {
                    ret++;
                    break;
                }
            }
        }
        return ret;
    }

    ~ListGraph() {
        while (m_vertexes.length() > 0) {
            auto toDel = m_vertexes.at(0);
            m_vertexes.removeAt(0);
            delete toDel->value;
            delete toDel;
        }
    }

protected:
    struct Vertex : public Object {
        VertexType *value = nullptr;
        LinkedList<Edge<EdgeType>> edges;
    };

    LinkedList<Vertex *> m_vertexes;
};

} // namespace Kylin

#endif // LISTGRAPH_H