Раздел «Образование».FIVTLecturesTerm3Lecture7:
<< Список лекций ФИВТ, 3-й семестр, 2009 г.

Лекция 7. Класс, соответствующий ориентированному графу.

Простая реализация

Реализация с итераторами

#include <map>
#include <vector>
#include <set>

using namespace std;

typedef int Name;

// template<typename Name>
class BiGraph {
public: 
    class Vertex;
    class Edge;
   
    class Vertex {
    public:
        friend class BiGraph;
        class out_edge_iterator {
        public:
            out_edge_iterator();
            out_edge_iterator(map<Vertex*, Edge*>::iterator);
            bool operator ==(const out_edge_iterator &right) const;
            bool operator !=(const out_edge_iterator &right) const;
            out_edge_iterator& operator ++();
            out_edge_iterator operator ++(int i);
            Edge& operator *();
            friend ostream& operator <<(ostream &stream, const BiGraph::Vertex &e);
            friend istream& operator >>(ostream &stream, BiGraph::Vertex &e);
        
        private:
            map<Vertex*, Edge*>::iterator m_it;
        };
        Vertex(Name name);
        Name name() const;
        std::pair<out_edge_iterator,out_edge_iterator> out_edges();
        size_t out_degree() const;
    private:
        Name m_name;
        map<Vertex*, Edge*> m_out_edges;
    };
    
    class Edge {
  
    public:
        friend class BiGraph;
        Vertex& src() const;
        Vertex& dest() const;
        double weight();
    
    friend ostream& operator <<(ostream &stream, const BiGraph::Edge &e);
    friend istream& operator >>(ostream &stream, BiGraph::Edge &e);
    
    private:
        Edge(Vertex* src, Vertex* dest, double weight);

        Vertex *m_src, *m_dest;
        double m_weight;
    };
    
    class vertex_iterator {

        public:
        
        vertex_iterator();
        vertex_iterator(map<Name, Vertex*>::iterator it);
        bool operator ==(const vertex_iterator &right) const;
        bool operator !=(const vertex_iterator &right) const;
        vertex_iterator& operator ++();
        vertex_iterator operator ++(int i);
        Vertex& operator *();
        Vertex* operator ->();
        
        private:
        map<Name, Vertex*>::iterator m_it;
    };

    BiGraph();
    ~BiGraph();
    
    Edge* add_edge(Name v, Name w, double weight);
    
    std::pair<vertex_iterator, vertex_iterator>  vertices();
    
    size_t vertices_count() const;
    
    size_t edges_count() const;
    
    void clear();
    // Edge::edge_iterator find_path(Name src, Name dest);

private:
    map<Name, Vertex*> m_vertices;
    set<Edge*> m_edges;

    Vertex* find_or_create_vertex(Name name);
};

/* IMPLEMENTATION */


/* BiGraph::BiGraph */
BiGraph::BiGraph() : m_vertices(), m_edges() {
}


BiGraph::~BiGraph() {
    clear();
}

void
BiGraph::clear() {
  for ( map<Name, Vertex*>::iterator v_it = m_vertices.begin();
        v_it != m_vertices.end();
        v_it++ ) 
    {
        //delete (&*v_it);
    }
    m_vertices.clear();
    
    for ( set<Edge*>::iterator e_it = m_edges.begin();
        e_it != m_edges.end();
        e_it++ ) 
    {
        //delete (&*e_it);
    }
    m_edges.clear();
}

size_t
BiGraph::vertices_count() const {
    return m_vertices.size();
}

size_t
BiGraph::edges_count() const {
    return m_edges.size();
}

std::pair<BiGraph::vertex_iterator, BiGraph::vertex_iterator>  
BiGraph::vertices() {
    return make_pair(vertex_iterator(m_vertices.begin()), vertex_iterator(m_vertices.end()));
}

BiGraph::Edge*
BiGraph::add_edge(Name src_name, Name dest_name, double weight) {
    Vertex* src = find_or_create_vertex(src_name);
    Vertex* dest = find_or_create_vertex(dest_name);
    Edge* edge;
    if ( src->m_out_edges.find(dest) == src->m_out_edges.end() ) {  
        edge = new Edge(src, dest, weight);
        m_edges.insert(edge);
        src->m_out_edges[dest] = edge;
    } else {
        edge = src->m_out_edges[dest];
        edge->m_weight = weight;
    }
    return edge;
}

BiGraph::Vertex* 
BiGraph::find_or_create_vertex(Name name) {
    if ( m_vertices.find(name) == m_vertices.end() ) {
        return m_vertices[name] = new Vertex(name);
  } else {
    return m_vertices[name];
  }
}

/* BiGraph::vertex_iterator */

BiGraph::vertex_iterator::vertex_iterator(): m_it() {
}

BiGraph::vertex_iterator::vertex_iterator(map<Name, Vertex*>::iterator it): m_it(it) {
}

bool 
BiGraph::vertex_iterator::operator ==(const vertex_iterator &right) const {
    return m_it == right.m_it; 
};

bool 
BiGraph::vertex_iterator::operator !=(const vertex_iterator &right) const {
    return m_it != right.m_it; 
}

BiGraph::vertex_iterator& 
BiGraph::vertex_iterator::operator ++() { 
    ++m_it; 
    return *this;
}

BiGraph::vertex_iterator 
BiGraph::vertex_iterator::operator ++(int i) { 
    vertex_iterator old_it(m_it); 
    m_it++; 
    return old_it; 
}

BiGraph::Vertex& 
BiGraph::vertex_iterator::operator *() { 
    return *(m_it->second); 
}

BiGraph::Vertex* 
BiGraph::vertex_iterator::operator ->() { 
    return m_it->second; 
}

/* BiGraph::Edge */

BiGraph::Edge::Edge(BiGraph::Vertex* src, BiGraph::Vertex* dest, double weight) :
    m_src(src), m_dest(dest), m_weight(weight) {
}


BiGraph::Vertex&
BiGraph::Edge::src() const {
    return *m_src;
}

BiGraph::Vertex&
BiGraph::Edge::dest() const {
    return *m_dest;
}


/* BiGraph::Vertex */

BiGraph::Vertex::Vertex(Name name) : m_name(name) {
    
}

std::pair<BiGraph::Vertex::out_edge_iterator, BiGraph::Vertex::out_edge_iterator> 
BiGraph::Vertex::out_edges() {
    return make_pair( out_edge_iterator(m_out_edges.begin()), 
        out_edge_iterator(m_out_edges.end()) );
}

Name
BiGraph::Vertex::name() const {
    return m_name;
}

size_t
BiGraph::Vertex::out_degree() const {
    return m_out_edges.size();
}


/* BiGraph::Vertex::out_edge_iterator */

BiGraph::Vertex::out_edge_iterator::out_edge_iterator(): m_it() {
}

BiGraph::Vertex::out_edge_iterator::out_edge_iterator(map<Vertex*, Edge*>::iterator it): m_it(it) {
}

bool 
BiGraph::Vertex::out_edge_iterator::operator ==(const out_edge_iterator &right) const {
    return m_it == right.m_it; 
}

bool 
BiGraph::Vertex::out_edge_iterator::operator !=(const out_edge_iterator &right) const {
    return m_it != right.m_it; 
}

BiGraph::Vertex::out_edge_iterator& 
BiGraph::Vertex::out_edge_iterator::operator ++() { 
    ++m_it; 
    return *this;
}

BiGraph::Vertex::out_edge_iterator
BiGraph::Vertex::out_edge_iterator::operator ++(int i) { 
    out_edge_iterator old_it = out_edge_iterator(m_it); 
    m_it++; 
    return old_it; 
}

BiGraph::Edge& 
BiGraph::Vertex::out_edge_iterator::operator *() { 
    return *(m_it->second); 
}



#include <iostream>

ostream& operator <<(ostream &stream, const BiGraph::Edge &e) {
    return stream << "Edge: "  << e.src().name() << " " << e.dest().name();
};

ostream& operator <<(ostream &stream, const BiGraph::Vertex &v) {
    return stream << "Vertex: "  << v.name();
};

int main() {
    BiGraph g;
    g.add_edge(1, 2, 100);
    g.add_edge(1, 3, 100);
    g.add_edge(3, 2, 100);
    g.add_edge(3, 4, 100);
    pair<BiGraph::vertex_iterator, BiGraph::vertex_iterator> range = g.vertices();
    BiGraph::vertex_iterator b = range.first;
    BiGraph::vertex_iterator e = range.second;
    
    for ( ; b != e; ++b) {
        cout << *b << endl;   
    }

    return 0;
}

Задачи

-- ArtemVoroztsov - 25 Mar 2010