Graph.h

Go to the documentation of this file.

// Copyright (c) 2009-2013 University of Twente
// Copyright (c) 2009-2013 Michael Weber <michaelw@cs.utwente.nl>
// Copyright (c) 2009-2013 Maks Verver <maksverver@geocities.com>
// Copyright (c) 2009-2013 Eindhoven University of Technology
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
 
#ifndef MCRL2_PG_GRAPH_H
#define MCRL2_PG_GRAPH_H
 
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
 
// Note: these should be unsigned types; some algorithms depend on it!
typedef std::size_t verti;    
typedef std::size_t edgei;    
 
#define NO_VERTEX ((verti)-1)
 
class StaticGraph;
 
class StaticGraph
{
#if 0
public:
    class EdgeIterator
    {
    public:
        EdgeIterator() { }
        EdgeIterator(const EdgeIterator &ei) : g(ei.g), v(ei.v), e(ei.e) { }
        inline EdgeIterator &operator=(const EdgeIterator &ei);
        inline std::pair<verti, verti> operator*();
        inline std::pair<verti, verti> operator++();
        inline std::pair<verti, verti> operator++(int);
 
        edgei operator-(const EdgeIterator &ei) { return e - ei.e; }
 
    protected:
        EdgeIterator(const StaticGraph *g, verti v, edgei e) : g(g), v(v), e(e) { }
 
    private:
        const StaticGraph *g;  
        verti v;               
        edgei e;               
 
        friend class StaticGraph;
    };
#endif
 
public:
    typedef const verti *const_iterator;
 
#if 0
    typedef EdgeIterator const_edge_iterator;
#endif
 
    typedef std::vector<std::pair<verti, verti> > edge_list;
 
    enum EdgeDirection
    {
        EDGE_NONE           = 0,  /* for internal use only! */
        EDGE_SUCCESSOR      = 1,
        EDGE_PREDECESSOR    = 2,
        EDGE_BIDIRECTIONAL  = 3
    };
 
    StaticGraph();          
    ~StaticGraph();         
    void clear();
 
    void make_random(verti V, unsigned outdeg, EdgeDirection edge_dir,
                     bool scc);
 
    void make_random_clustered(verti cluster_size, verti V,
                               unsigned outdeg, EdgeDirection edge_dir);
 
    void shuffle_vertices();
 
    void shuffle_vertices(const std::vector<verti> &perm);
 
    void assign(const StaticGraph &graph);
 
    void assign(edge_list edges, EdgeDirection edge_dir);
 
    edge_list get_edges() const;
 
    template<class ForwardIterator>
    void make_subgraph( const StaticGraph &graph,
                        ForwardIterator vertices_begin,
                        ForwardIterator vertices_end,
                        bool proper,
                        EdgeDirection edge_dir = EDGE_NONE );
 
    void make_subgraph_threads( const StaticGraph &graph,
                                const verti *verts,
                                const verti nvert,
                                bool proper,
                                EdgeDirection edge_dir = EDGE_NONE );
 
    void remove_edges(edge_list &edges);
 
    void write_raw(std::ostream &os) const;
 
    void read_raw(std::istream &is);
 
    void swap(StaticGraph &g);
 
    bool empty() const { return V_ == 0; }
 
    verti V() const { return V_; }
 
    edgei E() const { return E_; }
 
    EdgeDirection edge_dir() const { return edge_dir_; }
 
    const_iterator succ_begin(verti v) const {
        return &successors_[successor_index_[v]];
    }
 
    const_iterator succ_end(verti v) const {
        return &successors_[successor_index_[v + 1]];
    }
 
    const_iterator pred_begin(verti v) const {
        return &predecessors_[predecessor_index_[v]];
    }
 
    const_iterator pred_end(verti v) const {
        return &predecessors_[predecessor_index_[v + 1]];
    }
 
    bool has_succ(verti v, verti w) const {
        return std::binary_search(succ_begin(v), succ_end(v), w);
    }
 
    bool has_pred(verti w, verti v) const {
        return std::binary_search(pred_begin(w), pred_end(w), v);
    }
 
    edgei degree(verti v) const {
        return indegree(v) + outdegree(v);
    }
 
    edgei outdegree(verti v) const {
        return succ_end(v) - succ_begin(v);
    }
 
    edgei indegree(verti v) const {
        return pred_end(v) - pred_begin(v);
    }
 
#if 0
    const_edge_iterator edges_begin(verti v = 0) const {
        return EdgeIterator(this, v, successor_index_[v]);
    }
 
    const_edge_iterator edges_end() const {
        return EdgeIterator(this, V_, E_);
    }
#endif
 
protected:
    void make_random_scc(edge_list &edges);
 
    void reset(verti V, edgei E, EdgeDirection edge_dir);
 
    template<class ForwardIterator, class VertexMapT>
    void make_subgraph( const StaticGraph &graph,
                        ForwardIterator vertices_begin,
                        ForwardIterator vertices_end,
                        VertexMapT &vertex_map,
                        bool proper,
                        EdgeDirection edge_dir = EDGE_NONE );
 
private:
    explicit StaticGraph(const StaticGraph &graph);
    StaticGraph &operator=(const StaticGraph &graph);
 
private:
    verti V_;  
    edgei E_;  
    verti *successors_, *predecessors_;
 
    edgei *successor_index_, *predecessor_index_;
 
    EdgeDirection edge_dir_;
 
private:
    /* This is a bit of a hack to allow the small progress measures code to
       do a preprocessing pass for nodes with self-loops. */
    friend class SmallProgressMeasures;
 
    friend class EdgeIterator;
};
 
 
inline void swap(StaticGraph &a, StaticGraph &b)
{
    a.swap(b);
}
 
#include "Graph_impl.h"
 
#endif /* ndef MCRL2_PG_GRAPH_H */