graph.h

Go to the documentation of this file.

 
#pragma once
 
#include <robin_hood.h>
#include <vector>
#include <Edge.h>
#include <Node.h>
#include <Eigen>
#include <iostream>
 
namespace Eigen {
}
 
namespace HF::SpatialStructures {
    using EdgeMatrix = Eigen::SparseMatrix<float, 1>; 
    using TempMatrix = Eigen::Map<const EdgeMatrix>;  
 
    enum class COST_AGGREGATE : int {
        SUM = 0,
        AVERAGE = 1,
        COUNT = 2
    };
 
    enum class Direction : int {
        INCOMING = 0, //< Use the child node's attribute for the cost.
        OUTGOING = 1, //< Use the parent node's attribute as the cost.
        BOTH = 2    //< Add the parent and child's attributes for the cost.
    };
 
 
    struct CSRPtrs {
        int nnz;    
        int rows;   
        int cols;   
 
        float* data;            
        int* outer_indices;     
        int* inner_indices;     
 
 
        inline bool AreValid() {
            return (data && outer_indices && inner_indices);
        }
 
 
 
        inline float* CSRPtrs::data_begin() const {
            return data ? data : nullptr;
        }
 
 
        // If the data field has not been given an address, and/or the nnz field has not been given
        // a value, data_end will return nullptr.
 
        inline float* CSRPtrs::data_end() const {
            if (nnz > 0) {
                return data ? data + nnz : nullptr;
            }
 
            return nullptr;
        }
 
 
        // If the inner_indices field has not been given an address, inner_begin will return nullptr.
 
        inline int* CSRPtrs::inner_begin() const {
            return inner_indices ? inner_indices : nullptr;
        }
 
 
        inline int* CSRPtrs::inner_end() const {
            if (nnz > 0) {
                return inner_indices ? inner_indices + nnz : nullptr;
            }
 
            return nullptr;
        }
 
 
        // If the outer_indices field has not been given an address, outer_begin will return nullptr.
 
        inline int* CSRPtrs::outer_begin() const {
            return outer_indices ? outer_indices : nullptr;
        }
 
 
        // If the outer_end field has not been given an address, and/or the rows field has not been
        // given a value, outer_end will return nullptr.
 
        inline int* CSRPtrs::outer_end() const {
            if (rows > 0) {
                return outer_indices ? outer_indices + rows : nullptr;
            }
 
            return nullptr;
        }
 
 
        // If the data field has not been given an address, or the rows field has not been given a
        // value, or row_number >= rows, row_begin will return nullptr.
 
        inline float* CSRPtrs::row_begin(int row_number) const {
            float* begin = nullptr;
 
            if (data && rows > 0) {
                if (row_number >= 0 && row_number < rows) {
                    begin = data + outer_indices[row_number];
                }
            }
 
            return begin;
        }
 
 
        // If the data field has not been given an address, or the rows field has not been given a
        // value, or row_number >= rows, row_end will return nullptr.
 
        inline float* CSRPtrs::row_end(int row_number) const {
            float* end = nullptr;
            const int next_row = row_number + 1;
 
            if (data && rows > 0) {
                if (next_row > 0 && next_row < rows) {
                    end = data + outer_indices[next_row];
                }
                else if (next_row > 0 && next_row == rows) {
                    end = data_end();
                }
            }
 
            return end;
        }
 
 
        // If the inner_indices and/or outer_indices field have not been given addresses, or
        // row_number >= rows, col_begin will return nullptr.
 
        inline int* CSRPtrs::col_begin(int row_number) const {
            int* begin = nullptr;
 
            if (inner_indices && outer_indices) {
                if (row_number >= 0 && row_number < rows) {
                    begin = inner_indices + outer_indices[row_number];
                }
            }
 
            return begin;
        }
 
 
        // If the inner_indices and/or outer_indices field have not been given addresses, or
        // row_number >= rows, col_end will return nullptr.
 
        inline int* CSRPtrs::col_end(int row_number) const {
            int* end = nullptr;
            const int next_row = row_number + 1;
 
            if (inner_indices && outer_indices) {
                if (next_row > 0 && next_row < rows) {
                    end = inner_indices + outer_indices[next_row];
                }
                else if (next_row > 0 && next_row == rows) {
                    end = inner_end();
                }
            }
            return end;
        }
    };
 
    struct Subgraph {
        Node m_parent;                      
        std::vector<Edge> m_edges;          
    };
 
    class EdgeCostSet {
    private:
        std::vector<float> costs; 
 
    public:
        EdgeCostSet() { this->costs.resize(0); };
 
        inline EdgeCostSet(int size) { this->ResizeIfNeeded(size); }
 
        inline int size() const { return this->costs.size(); };
 
        inline void ResizeIfNeeded(int new_size) {
            const int old_size = this->size();
            if (this->size() < new_size)
            {
                // resize the cost array
                this->costs.resize(new_size);
 
                // fill new values with NAN
                const auto start_offset = costs.begin() + old_size;
                std::fill(start_offset, costs.end(), NAN);
            }
        };
 
        inline void Clear() { this->costs.clear(); }
 
        inline float& operator[](int i) { 
            assert(this->bounds_check(i));
            return this->costs[i]; 
        }
 
        inline bool bounds_check(int i) const {
            return !(i >= this->size()) || (i < 0);
        }
 
        inline float operator[](int i) const { 
            assert(this->bounds_check(i));
            return this->costs[i]; 
        }
 
        inline float* GetPtr() {
            assert(this->costs.size() > 0);
            return this->costs.data();
        }
        
        inline const float* GetPtr() const { 
            assert(this->costs.size() > 0);
            return this->costs.data(); 
        }
 
    };
 
    class Graph {
        using NodeAttributeValueMap = robin_hood::unordered_map<int, std::string>;
 
    private:
        int next_id = 0;                                
        std::vector<Node> ordered_nodes;                
 
        //robin_hood::unordered_map<int, int> id_to_ordered_node; ///< Maps ids to indexes in ordered_nodes.
        robin_hood::unordered_map<Node, int> idmap;     
 
        std::vector<Eigen::Triplet<float>> triplets;    
        bool needs_compression = true;                  
 
        robin_hood::unordered_map<std::string, NodeAttributeValueMap> node_attr_map; 
 
        std::string active_cost_type;                               
        EdgeMatrix edge_matrix;             
 
        std::string default_cost = "Distance";
        std::unordered_map<std::string, EdgeCostSet> edge_cost_maps; 
 
        bool has_cost_arrays = false;
 
        bool nodes_out_of_order = false;
 
        int getOrAssignID(const Node & input_node);
 
        int getOrAssignID(int input_int);
 
        bool checkForEdge(int parent, int child) const;
 
        void CSRAddOrUpdateEdge(int parent_id, int child_id, float cost);
 
        void TripletsAddOrUpdateEdge(int parent_id, int child_id, float cost);
 
        void ResizeIfNeeded();
 
        bool hasKey(int id) const;
 
        bool HasCostArray(const std::string & key) const;
 
        EdgeCostSet& GetCostArray(const std::string& key);
 
        EdgeCostSet& GetOrCreateCostType(const std::string& name);
 
        EdgeCostSet& CreateCostArray(const std::string& name);
 
        const EdgeCostSet& GetCostArray(const std::string& key) const;
 
        bool IsDefaultName(const std::string& name) const;
 
        int FindValueArrayIndex(int parent_id, int child_id) const;
 
        void InsertEdgeIntoCostSet(int parent_id, int child_id, float score, EdgeCostSet& cost_set);
 
        void InsertEdgesIntoCostSet(EdgeCostSet& cost_set, const std::vector<EdgeSet>& es);
 
        void InsertOrUpdateEdge(int parent_id, int child_id, float score, const std::string& cost_type);
 
        float GetCostForSet(const EdgeCostSet& set, int parent_id, int child_id) const;
 
        std::vector<Edge> GetEdgesForNode(
            int parent_id,
            bool undirected = false,
            const std::string& cost_type = ""
        ) const;
 
        TempMatrix MapCostMatrix(const std::string& cost_type) const;
 
        bool HasNodeAttribute(const std::string & key) const;
 
    public:
        Graph(
            const std::vector<std::vector<int>>& edges,
            const std::vector<std::vector<float>>& distances,
            const std::vector<Node>& Nodes,
            const std::string& default_cost = "Distance"
        );
 
        Graph(const std::string& default_cost_name = "Distance");
 
        bool HasEdge(
            const std::array<float, 3>& parent,
            const std::array<float, 3>& child,
            bool undirected = false
        ) const;
 
        bool HasEdge(
            const Node& parent,
            const Node& child,
            const bool undirected = false,
            const std::string cost_type = ""
        ) const;
 
        /* \brief Determine if the graph has an edge from parent to child.
 
            \param parent Parent of the edge to check for.
            \param child Child of the edge to check for.
            \param undirected If true, look for an edge from child to parent as well.
            \returns True if an edge between parentand child exists
            (also child and parent if undirected is true).
 
            \exception std::exception if the graph is uncompressed.
 
            \code
                // be sure to #include "graph.h"
 
                // Create the nodes
                HF::SpatialStructures::Node node_0(1.0f, 1.0f, 2.0f);
                HF::SpatialStructures::Node node_1(2.0f, 3.0f, 4.0f, 5);
                HF::SpatialStructures::Node node_2(11.0f, 22.0f, 140.0f);
 
                // Create a container (vector) of nodes
                std::vector<HF::SpatialStructures::Node> nodes = { node_0, node_1, node_2 };
 
                // Create matrices for edges and distances, edges.size() == distances().size()
                std::vector<std::vector<int>> edges = { { 1, 2 }, { 2 }, { 1 } };
                std::vector<std::vector<float>> distances = { { 1.0f, 2.5f }, { 54.0f }, { 39.0f } };
 
                // Now you can create a Graph - note that nodes, edges, and distances are passed by reference
                HF::SpatialStructures::Graph graph(edges, distances, nodes);
 
                // last argument can be true/false for undirected/directed graph respectively
                bool has_edge = graph.HasEdge(0, 1, true);
            \endcode
        */
        bool HasEdge(int parent, int child, bool undirected = false, const std::string& cost_type = "") const;
 
 
        std::vector<Node> Nodes() const;
 
 
        std::vector<Edge> GetUndirectedEdges(const Node& N, const std::string& cost_type = "") const;
 
 
        std::vector<EdgeSet> GetEdges() const;
    
        std::vector<IntEdge> GetIntEdges(int parent) const;
 
 
        std::vector<float> AggregateGraph(COST_AGGREGATE agg_type, bool directed = true, const std::string& cost_type = "") const;
        const std::vector<Edge> operator[](const Node& n) const;
 
 
        void addEdge(const Node& parent, const Node& child, float score = 1.0f, const std::string& cost_type = "");
 
 
        void addEdge(int parent_id, int child_id, float score, const std::string& cost_type = "");
 
 
        bool hasKey(const Node& n) const;
 
 
        std::vector<std::array<float, 3>> NodesAsFloat3() const;
 
 
        int size() const;
 
        int MaxID() const;
 
 
        int getID(const Node& node) const;
 
        void Compress();
 
 
        CSRPtrs GetCSRPointers(const std::string& cost_type = "");
 
 
        Node NodeFromID(int id) const;
 
 
        void Clear();
 
 
        std::vector<Node> GetChildren(const Node& n) const;
 
 
        std::vector<Node> GetChildren(const int parent_id) const;
 
        Subgraph GetSubgraph(const Node& parent_node, const std::string& cost_type = "") const;
 
        Subgraph GetSubgraph(int parent_id, const std::string & cost_type = "") const;
 
 
        void AddNodeAttribute(int id, const std::string & attribute, const std::string & score);
 
 
        void AddNodeAttributes(const std::vector<int> & id, const std::string &  name, const std::vector<std::string> & scores);
 
 
        std::vector<std::string> GetNodeAttributes(std::string attribute) const;
 
 
        void ClearNodeAttributes(std::string name);
 
        bool DumpToJson(const std::string & path);
 
        void AddEdges(const EdgeSet& edges, const std::string& cost_name = "");
 
        void AddEdges(const std::vector<EdgeSet>& edges, const std::string& cost_name = "");
 
        std::vector<EdgeSet> GetEdges(const std::string& cost_name) const;
 
        std::vector<std::string> GetCostTypes() const;
        
        float GetCost(int parent_id, int child_id, const std::string& cost_type = "") const;
 
        void Graph::AddEdges(const std::vector<std::vector<IntEdge>>& edges, const std::string& cost_type);
 
        void ClearCostArrays(const std::string & cost_name = "");
 
        void AttrToCost(
            const std::string & node_attribute,
            const std::string & cost_to_store_as,
            Direction consider = Direction::INCOMING);
        
    };
}