GraphAbstraction.h

Go to the documentation of this file.

/*
 *  $Id: GraphAbstraction.h
 *  hog2
 *
 *  Created by Nathan Sturtevant on 1/11/05.
 *  Modified by Nathan Sturtevant on 02/29/20.
 *
 * This file is part of HOG2. See https://github.com/nathansttt/hog2 for licensing information.
 *
 */
 
#include "Graph.h"
#include "Path.h"
#include "GLUtil.h"
#include <stdlib.h>
#include <stdio.h>
 
#ifndef GRAPHABSTRACTION_H
#define GRAPHABSTRACTION_H
#include <vector>
 
namespace GraphAbstractionConstants {
        enum {
                kAbstractionLevel = 0, // this is a LONG label
                kNumAbstractedNodes = 1, // nodes that we abstract; this is a LONG label
                kParent = 2, // node that abstracts us; this is a LONG label
                kNodeWidth = 3, // the maximum size object that can completely traverse this node; this is a LONG label
                kTemporaryLabel = 4, // for any temporary usage; this label can be LONG or FLOATING point
                kXCoordinate = 5, // cache for opengl drawing; this is a FLOATING POINT label
                kYCoordinate = 6,       // this is a FLOATING POINT label
                kZCoordinate = 7,       // this is a FLOATING POINT label
                kNodeBlocked = 8, // this is a LONG label
                kFirstData = 9
        };
        
        enum {
                kEdgeWidth = 1
        };
        
        
        enum {
                kEdgeCapacity=2
        };
        
        const double kUnknownPosition = -50.0;
}
 
class GraphAbstraction {
public:
        GraphAbstraction() :abstractions() {}
        virtual ~GraphAbstraction();
        
        // basic Graph functions
        virtual bool Pathable(node *from, node *to) = 0;
        void GetNumAbstractGraphs(node *from, node *to, std::vector<node *> &fromChain, std::vector<node *> &toChain);
        Graph* GetAbstractGraph(int level) { return abstractions[level]; }
        unsigned int getNumAbstractGraphs() { return (unsigned int)abstractions.size(); }
        virtual double h(node *a, node *b) = 0;
        double distance(path *p);
        node *GetNthParent(node *which, int n);
        bool IsParentOf(node *parent, node *child);
        
        inline node *GetParent(node *which) { return abstractions[GetAbstractionLevel(which)+1]->GetNode(which->GetLabelL(GraphAbstractionConstants::kParent)); }
        inline long GetNumChildren(node *which) { return which->GetLabelL(GraphAbstractionConstants::kNumAbstractedNodes); }
        inline node *GetNthChild(node *which, int n) { return abstractions[GetAbstractionLevel(which)-1]->GetNode(which->GetLabelL(GraphAbstractionConstants::kFirstData+n)); }
        
        node* GetRandomGroundNodeFromNode(node *n);
        
        inline long GetAbstractionLevel(node *which) { return which->GetLabelL(GraphAbstractionConstants::kAbstractionLevel); }
        inline Graph* GetAbstractGraph(node *which) { return abstractions[which->GetLabelL(GraphAbstractionConstants::kAbstractionLevel)]; }
        // utility functions
        virtual void VerifyHierarchy() = 0;
        // virtual void rebuild() = 0;
        //virtual int GetRevision() = 0;
        void ClearMarkedNodes();
        
        // hierarchical modifications
        virtual void RemoveNode(node *n) = 0;
        virtual void RemoveEdge(edge *e, unsigned int absLevel) = 0;
        virtual void AddNode(node *n) = 0;
        virtual void AddEdge(edge *e, unsigned int absLevel) = 0;
        virtual void RepairAbstraction() = 0;
        virtual int MeasureRepairHits() { return 0; }
        void MeasureAbstractionValues(int level, double &n, double &n_dev, double &c, double &c_dev);
        double MeasureAverageNodeWidth(int level);
        
        virtual void OpenGLDraw() const {}
        virtual recVec GetNodeLoc(node *) const { recVec v; v.x = v.y = v.z = 0; return v; }
protected:
        std::vector<Graph *> abstractions;
private:
        int ComputeWidth(node *n);
        int WidthBFS(node *child, node *parent);
        double MeasureExpectedNodeWidth(node *n);
        int GetNumExternalEdges(node *n, node *p);
        int CountEdgesAtDistance(node *child, node *parent, std::vector<int> &dists);
};
 
// this class can be defined if you want to solve multiple domains...
//
// class domainAbstraction : public GraphAbstraction {
//      void domainAbstraction(abstractableDomain *) = 0;
// };
 
#endif