---

edge.h

/****************************************************
 *  Bachelor Project:                               *
 *  External Memory Minimum Spanning Trees          *
 *  by Dominik Schultes <mail@dominik-schultes.de>  *
 *                                                  *
 *                edge.h                            *
 *                                                  *
 *  April 13, 2003                                  *
 ****************************************************/


#ifndef EDGE_H
#define EDGE_H

#include <iostream>

typedef unsigned int NodeID;
typedef unsigned int EdgeWeight;
typedef unsigned long long int EdgeWeightBig; // used for the sum of edge weights

class EdgeWithoutSource
{
    friend bool operator<(const EdgeWithoutSource &e1,
                          const EdgeWithoutSource &e2) {
        return e1._weight<e2._weight;
    }

    friend bool operator==(const EdgeWithoutSource &e1,
                           const EdgeWithoutSource &e2) {
        return (e1._target == e2._target) && (e1._weight == e2._weight);
    }
    
    friend std::ostream& operator<<( std::ostream& os, const EdgeWithoutSource &e ) {
        os << e.target() << " " << e.weight();
        return os;
    }
    
 public:
    static EdgeWithoutSource minWeight() {return EdgeWithoutSource(0,0);}

    static EdgeWithoutSource maxWeight() {return EdgeWithoutSource(0,0xffffffff);}
    
    EdgeWithoutSource( NodeID target = 0, EdgeWeight weight = 0 )
        : _target( target ), _weight( weight )
        {}
    
    NodeID target() const {return _target;}
    
    EdgeWeight weight() const {return _weight;}
      
 protected:
    void setTarget(NodeID target) {_target = target;}
    
 private:
    NodeID _target;
    EdgeWeight _weight; 
};

class Edge : public EdgeWithoutSource
{
    friend bool operator==(const Edge &e1, const Edge &e2) {
        return ( e1.source()==e2.source() ) && ( e1.target()==e2.target() );
    }

    friend std::ostream& operator<<( std::ostream& os, const Edge &e ) {
        os << e.source() << " " << e.target() << " " << e.weight();
        return os;
    }
    
 public:
    typedef EdgeWeight key_type;

    
    static Edge minWeight() {return Edge(0,0,0);}

    static Edge maxWeight() {return Edge(0,0,0xffffffff);}
    

    Edge(NodeID source = 0, NodeID target = 0, EdgeWeight weight = 0)
        : _source( source ), EdgeWithoutSource( target, weight )
        {}

    NodeID source() const {return _source;}

    void swap() {NodeID tmp = _source; _source = target(); setTarget(tmp);}

    bool isSelfLoop() const {return (source() == target());}


 private:
    NodeID _source;
};



template <typename EdgeType = Edge>
class GetWeight
{
public:
    typedef Edge::key_type key_type;
    key_type operator() (const EdgeType & obj)
        {
            return obj.weight();
        }
    static EdgeType min_value(){ return EdgeType::minWeight(); }
    static EdgeType max_value(){ return EdgeType::maxWeight(); }
};



template <typename EdgeType = Edge>
class WeightOrdering
{
 public:
    bool operator() (const EdgeType &e1, const EdgeType &e2) const
        {
            if (e1.weight() < e2.weight()) return true;
            return false;
        }
    static EdgeType min_value(){ return EdgeType::minWeight(); }
    static EdgeType max_value(){ return EdgeType::maxWeight(); }
};


class SourceTargetWeightOrdering
{
 public:
    bool operator() (const Edge &e1, const Edge &e2) const
        {
            // first, compare by source
            if (e1.source() < e2.source()) return true;
            if (e1.source() > e2.source()) return false;

            // then, by target
            if (e1.target() < e2.target()) return true;
            if (e1.target() > e2.target()) return false;

            // finally, by weight
            if (e1.weight() < e2.weight()) return true;
            return false;
        }

    static Edge min_value() {return Edge(0,0,0);}
    static Edge max_value() {return Edge(0xffffffff,0xffffffff,0xffffffff);}
};


template <typename EdgeType = Edge>
class SourceWeightOrdering
{
 public:
    bool operator() (const EdgeType &e1, const EdgeType &e2) const
        {
            // first, compare by source
            if (e1.source() < e2.source()) return true;
            if (e1.source() > e2.source()) return false;

            // then, by weight
            if (e1.weight() > e2.weight()) return true;
            return false;
        }
    
    static EdgeType min_value(){ return EdgeType::minWeight(); }
    static EdgeType max_value(){ return EdgeType::maxWeight(); }
};

#endif // EDGE_H

---