UndirectedGraph.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_UndirectedGraph_h
#define GlobeEngine_UndirectedGraph_h
#include "VBOVertex.h"
#include "OpenGL_Includes.h"
#include <iostream>

#include "UndirectedEdge.h"
#include "GraphNode.h"
#include "Graph.h"

namespace geGraph {
    
    template <class NODETYPE, class EDGETYPE, class U> class UndirectedGraph : public Graph < NODETYPE, EDGETYPE, U>
    {
    public:
        UndirectedGraph(){}

        /*
         * add an undirected edge by their indices
         */
        unsigned int addUndirectedEdge(unsigned int _nodeIdx1, unsigned int _nodeIdx2){
            return this->addWeightedUndirectedEdge(_nodeIdx1, _nodeIdx2, 1.0f);
        }
            
        unsigned int addWeightedUndirectedEdge(unsigned int _nodeIdx1, unsigned int _nodeIdx2, float _weight){
            unsigned int newEdgeID = this->edges.size();
            std::pair<U , U > fwcomb(_nodeIdx1, _nodeIdx2);
            std::pair<U , U > bwcomb(_nodeIdx2, _nodeIdx1);
            
            typename std::map< std::pair < U , U >, U >::const_iterator edgeFWItr = this->forwardEdges.find(fwcomb);
            if(edgeFWItr != this->forwardEdges.end()) {
                //std::cout << " found a doubled edge in FW edges" << edgeFWItr->second << std::endl;
                return UINT_MAX;
            }else{
                typename std::map< std::pair < U , U >, U >::const_iterator edgeBWItr = this->forwardEdges.find(bwcomb);
                if(edgeBWItr != this->forwardEdges.end()) {
                    //std::cout << " found a doubled edge in BW edges: " << edgeBWItr->second << std::endl;
                    return UINT_MAX;
                }else{
                    // edge can be added
                    EDGETYPE newUEdge(newEdgeID, _nodeIdx1, _nodeIdx2, _weight);
                    this->edges.push_back(newUEdge);
                    this->nodes[_nodeIdx1].addEdge(newEdgeID);
                    this->nodes[_nodeIdx2].addEdge(newEdgeID);
                    
                    this->forwardEdges.insert(std::pair< std::pair< U , U > , U >(fwcomb, newEdgeID));
                    this->backwardEdges.insert(std::pair< std::pair< U , U >, U >(bwcomb, newEdgeID));
                    return newEdgeID;
                }
            }
            return UINT_MAX;
        }
        
        U getEdgeByNodeIDs(unsigned int _nodeIdx1, unsigned int _nodeIdx2){
            std::pair<U , U > edgeToSearch(_nodeIdx1, _nodeIdx2);
            typename std::map< std::pair < U , U >, U >::const_iterator edgeItr = this->forwardEdges.find(edgeToSearch);
            if(edgeItr != this->forwardEdges.end()) {
                return edgeItr->second;
            }else{
                //std::pair<U , U > oppositeEdgeToSearch(_nodeIdx2, _nodeIdx1);
                typename std::map< std::pair < U , U >, U >::const_iterator edgeBWItr = this->backwardEdges.find(edgeToSearch);
                if(edgeBWItr != this->backwardEdges.end()) {
                    return edgeBWItr->second;
                }else{
                    std::cout << "No edge for NodeIDs found."  << std::endl;
                    return UINT_MAX;
                }
            }
        }
        
        friend std::ostream& operator<< (std::ostream &out, const UndirectedGraph< NODETYPE, EDGETYPE, U> &graph) {
            out << "graph has "<< graph.nodes.size() << " nodes: " << std::endl;
            for (int i = 0; i < graph.nodes.size(); i++)
            {
                out << graph.nodes[i] << std::endl;
            }
            return out;
        }
    };
    
    /* graphs with a maximum of 4'294'967'295 Edges */
    typedef UndirectedGraph<ge::Vertex2d, UndirectedEdgeui, unsigned int > Graph2Dd;
    typedef UndirectedGraph<ge::Vertex3d, UndirectedEdgeui, unsigned int > Graph3Dd;
    
    typedef UndirectedGraph<ge::Vertex2d, UndirectedEdgeui, unsigned int > UndirectedGraph2Dd;
    typedef UndirectedGraph<ge::Vertex3d, UndirectedEdgeui, unsigned int > UndirectedGraph3Dd;
    
}
#endif