Net.hxx

Go to the documentation of this file.

/*
 * Copyright:: Copyright (c) 2013, 2014, 2015, 2016, 2017, Frank Fischer
 *
 * This file is part of DynG.
 *
 * DynG is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * DynG is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with DynG.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef __DYNG_NET_HXX__
#define __DYNG_NET_HXX__

#include <vector>
#include <memory>
#include <stdexcept>

namespace Dyng {

typedef int index_type;

class DyngError : public std::logic_error
{
public:
    DyngError(const std::string& msg) : std::logic_error(msg) {}

    DyngError(const char* msg) : std::logic_error(msg) {}
};

class Net
{
public:
    typedef index_type Group;

    typedef index_type BaseNode;

    typedef index_type BaseArc;

    typedef index_type Node;

    typedef index_type Arc;

    typedef index_type Time;

    typedef index_type RunTime;

    static const Node nonode = -1;
    static const Arc noarc = -2;

    enum class Result {
        Solved=1,
        Expanded=2
    };

    template <typename It, typename Node, typename Arc,
              Arc (Net::*First) (Node) const,
              Arc (Net::*Next) (Arc) const>
    class ArcIterator:
        public std::iterator<std::forward_iterator_tag, const Arc>
    {
    public:
        typedef Node node_type;
        typedef Arc arc_type;

    public:
        ArcIterator(const Net* net) :
            _net(net), _arc(Net::noarc)
        {}

        ArcIterator(const Net* net, Node node) :
            _net(net), _arc((net->*First)(node))
        {}

        Arc operator*() const { return _arc; }

        bool operator==(const It& it) const {
            return _arc == it._arc;
        }

        bool operator!=(const It& it) const {
            return _arc != it._arc;
        }

        It& operator++() {
            _arc = (_net->*Next)(_arc);
            return static_cast<It&>(*this);
        }

    private:
        const Net* _net;
        Arc _arc;
    };

    template <typename It>
    class ArcList
    {
    public:
        ArcList(const Net* net, typename It::node_type node):
            _net(net), _node(node)
        {}

        It begin() const {
            return It(_net, _node);
        }

        It end() const {
            return It(_net);
        }

    private:
        const Net* _net;
        typename It::node_type _node;
    };


public:
    Net();

    ~Net();

    Net(const Net& net) = delete;

    Net& operator=(const Net& net) = delete;

    Net(Net&& net);

    Net& operator=(Net&& net);


    index_type n_groups() const;

    Group add_group();

    Group add_groups(index_type ngroups);

    index_type n_basenodes() const;

    BaseNode add_basenode(Group group);

    Group base_group(BaseNode bnode) const;

    index_type base_groupidx(BaseNode bnode) const;

    bool base_waitnode(BaseNode bnode) const;

    BaseArc base_firstout(BaseNode bnode) const;

    BaseArc base_firstin(BaseNode bnode) const;

    index_type n_basearcs() const;

    BaseArc add_basearc(BaseNode bsrc, BaseNode bsnk);

    BaseArc base_arc(BaseNode bsrc, BaseNode bsnk) const;

    void add_runningtime(BaseArc arc, RunTime running_time);

    void add_runningtimes(BaseArc arc,
                          std::size_t ntimes,
                          const RunTime running_times[]);

    void add_runningtimes(BaseArc arc,
                          const std::vector<RunTime>& running_times)
    {
        add_runningtimes(arc, running_times.size(), &(running_times[0]));
    }

    BaseArc base_nextout(BaseArc arc) const;

    BaseArc base_nextin(BaseArc arc) const;

    BaseNode base_src(BaseArc arc) const;

    BaseNode base_snk(BaseArc arc) const;

    class BaseOutIterator:
        public Net::ArcIterator<BaseOutIterator,
                                BaseNode, BaseArc,
                                &Net::base_firstout, &Net::base_nextout>
    {
        using ArcIterator::ArcIterator;
    };

    class BaseOutList: public ArcList<BaseOutIterator> {
        using ArcList::ArcList;
    };

    BaseOutList base_outarcs(BaseNode bnode) const {
        return BaseOutList(this, bnode);
    }

    class BaseInIterator:
        public Net::ArcIterator<BaseInIterator,
                                BaseNode, BaseArc,
                                &Net::base_firstin, &Net::base_nextin>
    {
        using ArcIterator::ArcIterator;
    };

    class BaseInList: public ArcList<BaseInIterator> {
        using ArcList::ArcList;
    };

    BaseInList base_inarcs(BaseNode bnode) const {
        return BaseInList(this, bnode);
    }



    void init();

    Time group_mintime(Group group) const;

    Time basenode_mintime(BaseNode bnode) const;


    index_type n_nodes() const;


    Node node(BaseNode bnode, Time time) const;


    BaseNode basenode(Node node) const;


    Time time(Node node) const;


    Arc firstout(Node node) const;


    Arc firstin(Node node) const;


    index_type n_arcs() const;


    Arc arc(Node src, Node snk) const;


    Arc find_arc(BaseNode bsrc, Time srctime, BaseNode bsnk, Time snktime) const;

    bool isactive(Arc arc) const;

    Node src(Arc arc) const;


    Node snk(Arc arc) const;


    Arc nextout(Arc arc) const;


    Arc nextin(Arc arc) const;

    class OutIterator:
        public Net::ArcIterator<BaseOutIterator,
                                Node, Arc,
                                &Net::firstout, &Net::base_nextout>
    {
        using ArcIterator::ArcIterator;
    };

    class OutList: public ArcList<BaseOutIterator> {
        using ArcList::ArcList;
    };

    OutList outarcs(BaseNode bnode) const {
        return OutList(this, bnode);
    }

    class InIterator:
        public Net::ArcIterator<BaseInIterator,
                                Node, Arc,
                                &Net::firstin, &Net::base_nextin>
    {
        using ArcIterator::ArcIterator;
    };

    class InList: public ArcList<BaseInIterator> {
        using ArcList::ArcList;
    };

    InList inarcs(BaseNode bnode) const {
        return InList(this, bnode);
    }



    void force_active(Group grp, Time time_active);

    Time active_time(Group grp) const;

    Result shortest_path(const double basecosts[],
                         const double augcosts[],
                         index_type& nnodes,
                         index_type& narcs);

    Result shortest_path(const std::vector<double>& basecosts,
                         const std::vector<double>& augcosts,
                         index_type& nnodes,
                         index_type& narcs);

    Result shortest_path(const double basecosts[], const double augcosts[]);

    Result shortest_path(const std::vector<double>& basecosts,
                         const std::vector<double>& augcosts);

    index_type get_n_newnodes() const;

    index_type get_n_newarcs() const;

    index_type get_pathlen() const;

    double get_path(Arc path[]) const;

    double get_path(std::vector<Arc>& path) const;

    index_type get_num_new_active() const;

    void get_new_active(Arc active[]) const;

    void get_new_active(std::vector<Arc>& active) const;

private:
    struct Data;
    std::unique_ptr<Data> data;
};

}

#endif