ReducableUndirectedGraph.h

Go to the documentation of this file.

//
//  VBOVertex.h
//  GlobeEngine
//
//  Created by Mathias Thöny on 27.12.11.
//  Copyright (c) 2011 University of Zurich. All rights reserved.
//

#ifndef GlobeEngine_ReducableUndirectedGraph_h
#define GlobeEngine_ReducableUndirectedGraph_h
#include "VBOVertex.h"
#include "OpenGL_Includes.h"
#include <iostream>

#include "UndirectedEdge.h"
#include "WeightedUndirectedEdge.h"
#include "WeightedUndirectedPolylineEdge.h"
#include "GraphNode.h"
#include "Graph.h"
#include "UndirectedGraph.h"

namespace geGraph {
    
    template <class NODETYPE, class EDGETYPE, class U> class ReducableUndirectedGraph : public UndirectedGraph < NODETYPE, EDGETYPE, U>
    {
    public:
        ReducableUndirectedGraph(){}
        
        //
        // reduces all edges so that just non-connector nodes are used.
        //
        void reduceEdges(){
            // Start from Endpoints, not from edges
            for (unsigned int i=0; i < this->nodes.size();i++)
            {
                if (this->nodes[i].isEndpoint()) {
                    reduceFromEndpoint(i);
                }else{
                    if (this->nodes[i].isCrossing()) {
                        reduceFromCrossing(i);
                    }
                    else{
                        // node is connector. No change
                    }
                }
            }
        }
        
        void reduceFromEndpoint(unsigned int _nodeID){
            unsigned int tmpEdgeID = this->nodes[_nodeID].getNeighbors()[0];
            unsigned int tmpNodeID = this->edges[tmpEdgeID].getOppositeNode(_nodeID);
            // weight of the edge
            float weight = this->edges[tmpEdgeID].getWeight();

            if(this->edges[tmpEdgeID].isMarked()) {
                return; // this route is already reduced;
            }
            std::vector< U > markedEdges;
            while (this->nodes[tmpNodeID].isConnector())
            {
                this->edges[tmpEdgeID].mark();
                markedEdges.push_back(tmpEdgeID);
                tmpEdgeID = this->nodes[tmpNodeID].getOppositeEdge(tmpEdgeID);
                tmpNodeID = this->edges[tmpEdgeID].getOppositeNode(tmpNodeID);
                // add weight of this edge also
                weight += this->edges[tmpEdgeID].getWeight();
            }
            // mark last segment
            this->edges[tmpEdgeID].mark();
            markedEdges.push_back(tmpEdgeID);
            
            EDGETYPE newUEdge(tmpEdgeID, _nodeID, tmpNodeID, weight);
            unsigned int tmpRedEdgeID = this->reducedEdges.size();
            reducedEdgeToGraphEdge.insert(std::pair< U , std::vector< U > >(tmpRedEdgeID, markedEdges));
            this->reducedEdges.push_back(newUEdge);
            // since the _nodeID is an endpoint there is just one
            // associated reduced edge
            std::vector< U > edgesAssociatedToNode;
            edgesAssociatedToNode.push_back(tmpRedEdgeID);
            nodeIDToReducedEdge.insert(std::pair< U , std::vector< U > >(_nodeID, edgesAssociatedToNode));
            
            // it is necessary to add this connection also to the new opposite node
            typename std::map< U, std::vector< U > >::iterator nodeCheckItr = nodeIDToReducedEdge.find(tmpNodeID);
            if(nodeCheckItr != nodeIDToReducedEdge.end()) {
                nodeCheckItr->second.push_back(tmpRedEdgeID);
            }else{
                nodeIDToReducedEdge.insert(std::pair< U , std::vector< U > >(tmpNodeID, edgesAssociatedToNode));
            }
        }
        
        void reduceFromCrossing(unsigned int _nodeID){
            //std::cout << "Neigbor count: " << this->nodes[_nodeID].getNeighborCount() << std::endl;
            std::vector< U > edgesAssociatedToNode;
            for (unsigned int i=0;i<this->nodes[_nodeID].getNeighborCount();i++)
            {
                unsigned int tmpEdgeID = this->nodes[_nodeID].getNeighbors()[i];
                unsigned int tmpNodeID = this->edges[tmpEdgeID].getOppositeNode(_nodeID);
                float weight = this->edges[tmpEdgeID].getWeight();

                if(this->edges[tmpEdgeID].isMarked()) {
                    // this route is already reduced;
                }else{
                    std::vector< U > markedEdges;
                    while (this->nodes[tmpNodeID].isConnector())
                    {
                        this->edges[tmpEdgeID].mark();
                        markedEdges.push_back(tmpEdgeID);
                        tmpEdgeID = this->nodes[tmpNodeID].getOppositeEdge(tmpEdgeID);
                        tmpNodeID = this->edges[tmpEdgeID].getOppositeNode(tmpNodeID);
                        // add weight of this edge also
                        weight += this->edges[tmpEdgeID].getWeight();
                    }
                    this->edges[tmpEdgeID].mark();
                    markedEdges.push_back(tmpEdgeID);
                    unsigned int tmpRedEdgeID = this->reducedEdges.size();
                    EDGETYPE newUEdge(tmpEdgeID, _nodeID, tmpNodeID, weight);
                    this->reducedEdges.push_back(newUEdge);
                    reducedEdgeToGraphEdge.insert(std::pair< U , std::vector< U > >(tmpRedEdgeID, markedEdges));
                    edgesAssociatedToNode.push_back(tmpRedEdgeID);
                    
                    // it is necessary to add this connection also to the new opposite node
                    typename std::map< U, std::vector< U > >::iterator nodeCheckItr = nodeIDToReducedEdge.find(tmpNodeID);
                    if(nodeCheckItr != nodeIDToReducedEdge.end()) {
                        nodeCheckItr->second.push_back(tmpRedEdgeID);
                    }else{
                        nodeIDToReducedEdge.insert(std::pair< U , std::vector< U > >(tmpNodeID, edgesAssociatedToNode));
                    }
                }
            }
            // it is necessary to add this connection also to the new opposite node
            typename std::map< U, std::vector< U > >::iterator nodeCheckItr = nodeIDToReducedEdge.find(_nodeID);
            if(nodeCheckItr != nodeIDToReducedEdge.end()) {
                for(int i=0;i < edgesAssociatedToNode.size();i++) {
                    nodeCheckItr->second.push_back(edgesAssociatedToNode[i]);
                }
            }else{
                nodeIDToReducedEdge.insert(std::pair< U , std::vector< U > >(_nodeID, edgesAssociatedToNode));
            }
        }
        
        std::vector< U > getEdgesForReducedEdge(unsigned int _redEdgeID) {
            typename std::map< U, std::vector< U > >::const_iterator edgesByIDItr = reducedEdgeToGraphEdge.find(_redEdgeID);
            if(edgesByIDItr != reducedEdgeToGraphEdge.end()) {
                return edgesByIDItr->second;
            }
            
            return std::vector<U>();
        }
        
        std::vector< U > getReducedEdgesForNodeID(unsigned int _nodeID) {
            typename std::map< U, std::vector< U > >::const_iterator edgesByIDItr = nodeIDToReducedEdge.find(_nodeID);
            if(edgesByIDItr != nodeIDToReducedEdge.end()) {
                return edgesByIDItr->second;
            }
            
            return std::vector<U>();
        }
        
        std::vector< U > getReducedNodesForNodeID(unsigned int _startNodeID, unsigned int _endNodeID) {
            std::vector< U > nodeIDs;
            typename std::map< U, std::vector< U > >::const_iterator edgeByIDItr = nodeIDToReducedEdge.find(_startNodeID);
            if(edgeByIDItr != nodeIDToReducedEdge.end()) {
                if(edgeByIDItr->second.size() == 0){
                    // no reduced nodes from this point
                    return nodeIDs;
                }
                if(edgeByIDItr->second.size() == 1){
                    return getReducedNodeIDsForReducedEdge(edgeByIDItr->second[0]);
                }else{
                    // search the right connection first
                    for (unsigned int i = 0; i < edgeByIDItr->second.size();i++)
                    {
                        
                        if (_endNodeID == this->reducedEdges[edgeByIDItr->second[i]].getOppositeNode(_startNodeID) || _startNodeID == this->reducedEdges[edgeByIDItr->second[i]].getOppositeNode(_endNodeID))
                        {
                            return getReducedNodeIDsForReducedEdge(edgeByIDItr->second[i]);
                        }
                    }
                    std::cout << "Error: EndNode not found." << std::endl;
                    //return nodeIDs;
                }
            }else{
                std::cout << "No reduced edge found." << std::endl;
            }
            return nodeIDs;
        }
        
        std::vector< U > getReducedNodeIDsForReducedEdge(unsigned int _redEdgeID) {
            std::vector< U > redNodeIds;
            std::vector< U > edgeIds = getEdgesForReducedEdge(_redEdgeID);
            if (edgeIds.size() > 0)
            {
                unsigned int prevNodeID = this->edges[edgeIds[0]].getNodes()[0];
                if (this->nodes[prevNodeID].isConnector()) {
                    prevNodeID = this->edges[edgeIds[0]].getNodes()[1];
                }
                
                redNodeIds.push_back(prevNodeID);
                for (unsigned int i = 0; i < edgeIds.size();i++)
                {
                    unsigned int tmpNodeID = this->edges[edgeIds[i]].getOppositeNode(prevNodeID);
                    redNodeIds.push_back(tmpNodeID);
                    prevNodeID = tmpNodeID;
                }
            }
            return redNodeIds;
        }
        
        EDGETYPE* getReducedEdge(unsigned int _redEdgeID) {
            return &reducedEdges[_redEdgeID];
        }
        
        unsigned int getReducedEdgesCount()
        {
            return reducedEdges.size();
        }
        
    private:
        std::vector< EDGETYPE > reducedEdges;
        std::map< U, std::vector< U > > reducedEdgeToGraphEdge;
        std::map< U, std::vector< U > > nodeIDToReducedEdge;
    };
    
    
    typedef ReducableUndirectedGraph<ge::Vertex2d, UndirectedEdgeui, unsigned int > ReducableGraph2Dd;
    typedef ReducableUndirectedGraph<ge::Vertex3d, UndirectedEdgeui, unsigned int > ReducableGraph3Dd;
    
    typedef ReducableUndirectedGraph<ge::Vertex2d, UndirectedEdgeui, unsigned int > ReducableUndirectedGraph2Dd;
    typedef ReducableUndirectedGraph<ge::Vertex3d, UndirectedEdgeui, unsigned int > ReducableUndirectedGraph3Dd;
    
    
    template <class NODETYPE, class EDGETYPE, class U> class ReducableWeightedUndirectedGraph  : public ReducableUndirectedGraph < NODETYPE, EDGETYPE, U>
    { 
    public:
        ReducableWeightedUndirectedGraph(){}
        
        void setReducedEdgeWheight(unsigned int _redEdgeID, float _weight)
        {
            this->reducedEdges[_redEdgeID].setWeight(_weight);
        }
        
        void setReducedEdgeWheightByID(unsigned int _nodeID, float _weight)
        {
            //reducedEdges[_redEdgeID].setWeight(_weight);
        }
    };
    
    typedef ReducableWeightedUndirectedGraph<ge::Vertex2d, WeightedUndirectedEdgeui, unsigned int > ReducableWeightedGraph2Dd;
    typedef ReducableWeightedUndirectedGraph<ge::Vertex3d, WeightedUndirectedEdgeui, unsigned int > ReducableWeightedGraph3Dd;
    
    typedef ReducableWeightedUndirectedGraph<ge::Vertex2d, WeightedUndirectedEdgeui, unsigned int > ReducableWeightedUndirectedGraph2Dd;
    typedef ReducableWeightedUndirectedGraph<ge::Vertex3d, WeightedUndirectedEdgeui, unsigned int > ReducableWeightedUndirectedGraph3Dd;
    
    typedef ReducableWeightedUndirectedGraph<ge::Vertex2d, WeightedUndirectedPolylineEdgeui, unsigned int > ReducableWeightedUndirectedPolylineGraph2Dd;
    typedef ReducableWeightedUndirectedGraph<ge::Vertex3d, WeightedUndirectedPolylineEdgeui, unsigned int > ReducableWeightedUndirectedPolylineGraph3Dd;
    
}
#endif