directed_graph.hpp🔗

Classes🔗

	Name
class	DirectedGraph
Source code🔗

// Copyright (c) 2019 by Robert Bosch GmbH. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// SPDX-License-Identifier: Apache-2.0
#ifndef IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
#define IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP

#include "iceoryx_utils/cxx/vector.hpp"

#include <cstdint>
#include <limits>

// remark: only supports adding but no removal of vertices or edges
// and this graph is not necessarily acyclic
template <typename VertexType, int32_t VERTEX_LIMIT, int32_t DEGREE_LIMIT>
class DirectedGraph
{
  public:
    using Index_t = int32_t;
    using AdjacencyList = iox::cxx::vector<VertexType*, DEGREE_LIMIT>;

    static constexpr Index_t INVALID_INDEX = -1;

    virtual ~DirectedGraph() = default;

    bool addVertex(VertexType* vertex)
    {
        if (numberOfVertices() >= VERTEX_LIMIT)
        {
            return false;
        }

        if (findVertex(vertex) >= 0)
        {
            return false; // already exists
        }

        VertexData data(vertex);
        m_vertices.emplace_back(std::move(data));
        return true;
    }

    virtual bool addEdge(VertexType* fromVertex, VertexType* toVertex)
    {
        auto from = findVertex(fromVertex);
        auto to = findVertex(toVertex);
        if (from < 0 || to < 0 || from == to)
        {
            return false; // need to add vertices first (could do this here as well)
        }
        VertexData& fromData = m_vertices[from];
        VertexData& toData = m_vertices[to];

        if (static_cast<size_t>(fromData.successorIndices.size()) >= DEGREE_LIMIT
            || static_cast<size_t>(toData.predecessorIndices.size()) >= DEGREE_LIMIT)
        {
            return false; // degree limit of at least one vertex would be exceeded
        }

        // only store indices, value can be found at this index
        fromData.successorIndices.emplace_back(to);
        toData.predecessorIndices.emplace_back(from);

        // add to successor/predecessor lists to return on demand
        fromData.successors.emplace_back(toVertex);
        toData.predecessors.emplace_back(fromVertex);

        ++m_numEdges;

        return true;
    }

    Index_t getIndex(VertexType const* vertex)
    {
        return findVertex(vertex);
    }

    const AdjacencyList* getSuccessors(VertexType const* vertex)
    {
        return getSuccessors(findVertex(vertex));
    }

    const AdjacencyList* getPredecessors(VertexType const* vertex)
    {
        return getPredecessors(findVertex(vertex));
    }

    const AdjacencyList* getSuccessors(Index_t index)
    {
        if (index >= 0 && index < static_cast<Index_t>(numberOfVertices()))
        {
            return &m_vertices[index].successors;
        }
        return nullptr;
    }

    const AdjacencyList* getPredecessors(Index_t index)
    {
        if (index >= 0 && index < static_cast<Index_t>(numberOfVertices()))
        {
            return &m_vertices[index].predecessors;
        }
        return nullptr;
    }


    iox::cxx::vector<VertexType*, VERTEX_LIMIT> getSources()
    {
        iox::cxx::vector<VertexType*, VERTEX_LIMIT> result;
        for (auto& vertexData : m_vertices)
        {
            if (vertexData.predecessors.size() == 0u)
            {
                result.emplace_back(vertexData.vertex);
            }
        }
        return result;
    }

    iox::cxx::vector<VertexType*, VERTEX_LIMIT> getSinks()
    {
        iox::cxx::vector<VertexType*, VERTEX_LIMIT> result;
        for (auto& vertexData : m_vertices)
        {
            if (vertexData.successors.size() == 0)
            {
                result.emplace_back(vertexData.vertex);
            }
        }
        return result;
    }

    bool isSource(VertexType const* vertex)
    {
        auto index = findVertex(vertex);
        if (isValid(index))
        {
            if (m_vertices[index].predecessors.size() == 0)
            {
                return true;
            }
        }
        return false;
    }

    bool isSink(VertexType const* vertex)
    {
        auto index = findVertex(vertex);
        if (isValid(index))
        {
            if (m_vertices[index].successors.size() == 0)
            {
                return true;
            }
        }
        return false;
    }


    size_t numberOfVertices()
    {
        return m_vertices.size();
    }

    size_t numberOfEdges()
    {
        return m_numEdges;
    }

  protected:
    using AdjacencyIndexList = iox::cxx::vector<Index_t, DEGREE_LIMIT>;

    struct VertexData
    {
        explicit VertexData(VertexType* vertex)
            : vertex(vertex)
        {
        }

        VertexType* vertex;

        AdjacencyIndexList predecessorIndices; // indices to navigate the graph
        AdjacencyIndexList successorIndices;

        AdjacencyList predecessors; // values to provide references externally
        AdjacencyList successors;
    };

    iox::cxx::vector<VertexData, VERTEX_LIMIT> m_vertices;
    size_t m_numEdges{0};

    // static assert to check comparison operator?
    // requires ==operator
    Index_t findVertex(VertexType const* vertex) const
    {
        // linear search for now, could be improved using binary search if we store the vertices sorted
        // (but would require insertion in the middle)
        Index_t n = static_cast<Index_t>(m_vertices.size());
        for (Index_t i = 0; i < n; ++i)
        {
            const auto& compareVertex = m_vertices[i].vertex;
            if (vertex == compareVertex)
            {
                return i;
            }
        }
        return INVALID_INDEX; // not found
    }

    bool isValid(Index_t index)
    {
        return index >= 0 && index < static_cast<Index_t>(m_vertices.size());
    }
};

#endif // IOX_UTILS_GRAPHS_DIRECTED_GRAPH_HPP
Updated on 31 May 2022 at 15:29:15 CEST