Գրաֆի գագաթների տոպոլոգիական թվարկման մասին

Նախ նկարագրեմ ուղղորդված գրաֆի (directed graph, digraph) մոդելը որպես digraph դասի կաղապար։ Այս կաղապարի պարամետրն այն տիպն է, որ նմուշը գրառվելու է գրավի գագաթում։ Այդ տիպի վրա դրված մակ պահանջն այն է, որ նրա համար սահմանված լինի հավասարության ստուգման == գործողությունը։ Այդ գործողությունն օգտագործելու եմ տրված տվյալը պարունակող գագաթի ինդեքսը որոնելու համար։

template<typename Y>
class digraph {
    /// ...
};

Գրաֆի ներքին ներկայացման համար ընտրել եմ գագաթների հարևանության ցուցակների եղանակը։ Գագաթները հերթականությամբ ավելացնում եմ միաչափ զանգվածում (vector): Իսկ ամեն մի գագաթի (vertex) համապատասխանեցնում եմ նրան հարևան գագաթների ինդեքսների ցուցակը։ Քանի որ որոշել եմ գագաթում գրառել կաղապարի պարամետրով տրված ցանկացած տիպի օբյեկտ, մի գագաթի նկարագրությունը սահմանել եմ vertex տիպով.

using index = int;
using index_list = std::vector<index>;
using vertex = std::pair<Y,index_list>;

Դե իսկ գրաֆի գագաթների ցուցակն էլ արդեն կսահմանեմ հետևյալ կերպ.

std::vector<vertex> _vertices;

Գրաֆը կառուցելու եմ կողերը հաջորդաբար ավելացնելով։ add_edge մեթոդը ստանում է կաղապարի Y տիպի երկու արժեք և գրաֆում կոդ է ավելացնում այդ արժեքները պարունակող գագաթների միջև։ Եթե այդպիսի գագաթներ դեռ չկան, ապա գրաֆում ավելացնում է նաև գագաթները։

void add_vertex(const Y& u, const Y& v)
{
    auto ui = add_vertex(u);
    auto vi = add_vertex(v);
    _vertices[ui].second.push_back(vi);
}

Այստեղ օգտագործված add_vertex մեթոդը գրաֆում ավելացնում է տրված արժեքը պարունակող գագաթ։ Եթե այդպիսին արդեն կա, ապա վերադարձնում է դրա ինդեքսը։

index add_vertex(const Y& v)
{
    // որոնել
    for( index ix = 0; ix < _vertices.size(); ++ix )
        if( _vertices[ix].first == v )
            return ix;

    // ավելացնել
    _vertices.push_back(v, {});
    return _vertices.size() - 1;
}

Այսքանը լրիվ հերիք է գրաֆի կառուցման համար։ Թերևս կարելի է ավելացնել to_string մեթոդը, որը կվերադարձնի գրաֆի ինչ-որ տեքստային ներկայացում. պարզապես շտկումների համար։

std::string to_string()
{
    std::ostringstream oss;
    for( auto& e : _vertices ) {
        oss << e.first << " -> { ";
        for( auto& i : e.second )
            oss << _vertices[i].first << ' ';
        oss << '}' << std::endl;
    }
    return oss.str();
}

Այս մեթոդը պահանջում է, որ կաղապարի Y տիպի համար սահմանված լինի արտածման հոսքի մեջ ուղարկելու գործողությունը՝ operator<<։ Անցնեմ գրաֆի գագաթների տոպոլոգիական թվարկման իրականացմանը։ Տոպոլոգիական կարգավորման մասին բան չեմ գրի. կարելի է կարդալ, օրինակ, Ուիքիփեդիայի Topological Sorting էջը։ Միայն ասեմ, որ իրականացման համար ընտրել եմ Kahn-ի ալգորիթմը։ Մի քանի բառով դրա էությունը հետևյալն է. ամենասկզբում ստեկի մեջ են ավելացնում (push) բոլոր այն գագաթները, որոնք նախորդող չունեն (աղեղները դրանցից միայն դուրս են գալիս)։ Այնուհետև, քանի դեռ ստեկը դատարկ չէ, ստեկից հանում ենք u գագաթը, ապա գրաֆից հեռացնում ենք (pop) u գագաթից դուրս եկող բոլոր կողերը։ Եթե այս գործողության արդյունքում հայտնվում է գագաթ, որը դեպի իրեն եկող կող չունի, ապա այդ գագաթն ավելացնում ենք (push) ստեկում։ Քանի որ գրաֆից կող հեռացնելը կվնասեր մեր սկզբնական գրաֆը, այդ «կող հեռացնել» գործողությունը մոդելավորվում է մի վեկտորով, որում ամեն մի գագաթի համար պահվում է դեպի իրեն եկող կողերի քանակը։ Գրաֆի գագաթների՝ տոպոլոգիական կարգով թվարկումը իրականացրել եմ enumerate մեթոդում, որի պարամետրը ֆունկցիա է։ Այս ֆունկցիայով տրվում է այն գործողությունը, որը պետք է կատարվի գրաֆի թվարկվող հերթական գագաթի հետ։ Ավելի մանրամասն՝ մեկնաբանություններում.

void enumerate(std::function f)
{
    // գրաֆի գագաթների քանակը
    const std::size_t sz = _vertices.size();

    // degrees զանգվածում գրաֆի ամեն մի գագաթի համար
    // հաշվում ենք դեպի այն եկող կողերի քանակը
    std::vector<std::size_t> degrees(sz);
    for( auto& e : _vertices )
        for( auto& n : e.second )
            degrees[n] += 1;

    // նախապես S ստեկում ավելացնում ենք այն գագաթները,
    // որոնք նախորդող չունեն
    std::stack<index> S;
    for( std::size_t i = 0; i < degrees.size(); ++i )
        if( degrees[i] == 0 )
            S.push(i);

    // իտերացիա գագաթներով
    while( !S.empty() ) { // քանի դեռ ստեկը դատարկ չէ
        // վերցնել գագաթի տարրը
        index ix = S.top();
        S.pop();

        // տրված գործողությունը կատարել գագաթում գրառված
        // տվյալների հետ
        f(_vertices[ix].first);

        // դիտարկվող գագաթի բոլոր հարևանների համար...
        for( auto& vi : _vertices[ix].second ) {
            // ... եթե այդ հարևանը նախորդոնղեր չունի, ապա
            // այն արդեն մասնակցել է թվարկմանը, ...
            if( degrees[vi] == 0 )
                continue;

            // «կողը հեռացնելու» գործողության մոդելը.
            // պակասեցնում ենք հաշվիչը, ...
            degrees[vi] -= 1;
            // ... եթե հաշվիչը դառնում է զրո, ապա այդ գագաթը
            // ավելացնում ենք ստեկում
            if( degrees[vi] == 0 )
                S.push(vi);
        }
    }
}

Փորձարկենք ալգորիթմը ստորև բերված գրաֆի վրա՝ որպես թվարկման գործողություն տալով պարզապես գագաթի պարունակությունը տպող որևէ ֆունկցիա։ Սահմանում եմ գրաֆ, դրանում ավելացնում եմ նկարի գրաֆի կողերը, հետո to_string մեթոդով տպում եմ գրաֆի տեքստային ներկայացումը։ Թեսթավորման համար պարզապես ուզում եմ տպել գագաթները տոպոլոգիական կարգով։ Դրա համար enumerate մեթոդի արգումենտում տալիս եմ լամբդա-ֆունկցիա, որը պարզապես արտածում է իր արգումենտը։

int main()
{
    graphs::digraph<std::string> g0;
    g0.add_edge("a", "q0");
    g0.add_edge("b", "q0");
    g0.add_edge("b", "q1");
    g0.add_edge("c", "q1");
    g0.add_edge("q0", "x");
    g0.add_edge("q1", "x");
    g0.add_edge("q0", "y");
    g0.add_edge("q1", "y");

    std::cout << "Graph: " << std::endl << g0.to_string() << std::endl;

    std::cout << "Topological order of vertices: " << std::endl;
    g0.enumerate([&](auto& s) {std::cout << s << ' '; });
}

Կատարման արդյունքում արտածվում է հետևյալը.

Graph:
a -> { q0 }
q0 -> { x y }
b -> { q0 q1 }
q1 -> { x y }
c -> { q1 }
x -> { }
y -> { }

Topological order of vertices:
c b q1 a q0 y x

Լավ է։ Բայց ես ուզում եմ գրաֆի համար իրականացնել նրա գանաթերը տոպոլոգիական կարգով թվարկող իտերատոր. այնպիսին, ինչպիսիք սահմանված են STL-ում։ Այդ տիպի իտերատորի առկայության դեպքում կարող եմ գրել այսպիսի կոդ.

for( auto& v : g0 )
    std::cout << v << ' ';

Պարզ է, որ այդ իտերատորի մեթոդների իրականացումը պետք է արտացոլի նույն enumerate մեթոդի վարքը։ digraph դասում սահմանում եմ ներդրված iterator դասը։ range-for-ի աշխատանքն ապահովելու համար իտերատորում պետք է իրականացնել operator*, operator++ և operator!= գործողությունները։ Իտերատորի կոնստրուկտորում հաշվարկվում են բոլոր գագաթների մուտքային կիսաաստիճանները՝ տվյալ գագաթին ուղղված կողերի քանակը, ապա ստեկի մեջ են ավելացվում այն գագաթների ինդեքսները, դեպի որոնց եկող կողեր չկան։ operator*-ը վերադարձնում է հղում հերթական գագաթում գրառված տվյալին։ operator++-ը իտերատորը փոխանցում է հաջորդ գագաթին։ operator!=-ը համեմատում է երկու իտերատորների հերթական գագաթները։ Նորից՝ մանրամասները կոդի մեկնաբանություններում։

template
class digraph {
    // ...
    public:
        class iterator {
        public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = Y;

            //
            iterator(const digraph& g, bool init)
                : _ref{g}
            {
                if( init ) {
                    // հաշվարկվում են մուտքային կիսաաստիճանները
                    _degrees.resize(_ref._vertices.size());
                    for( auto& e : _ref._vertices )
                        for( auto& n : e.second )
                            _degrees[n] += 1;

                    // ստեկում ավելացնել բոլոր «սկզբնական» գագաթների ինդեքսները
                    for( std::size_t i = 0; i < _degrees.size(); ++i )
                        if( _degrees[i] == 0 )
                            _S.push(i);

                    // կատարել առաջին քայլը՝ արժեքավորել դիտարկվող գագաթի ինդեքսը
                    this->operator++();
                }
            }

            //
            iterator& operator++()
            {
                // եթե ստեկը դատարկ չէ, ապա անցնել հերթական գագաթին, հակառակ
                // դեպքում հերթական գագաթի ինդեքսին վերագրել -1
                if( !_S.empty() ) {
                    _current = _S.top();
                    _S.pop();

                    for( auto& vi : _ref._vertices[_current].second ) {
                        if( _degrees[vi] == 0 )
                            continue;

                        _degrees[vi] -= 1;
                        if( _degrees[vi] == 0 )
                            _S.push(vi);
                    }
                }
                else
                    _current = -1;

                return *this;
            }

            //
            bool operator!=(const iterator& other)
            {
                // համեմատել երկու իտերատորներում ընթացիկ գագաթի ինդեքսը
                return _current != other._current;
            }

            //
            const value_type& operator*() const
            {
                // վերադարձնել ընթացիկ գագաթում պահվող տվյալը
                return _ref._vertices[_current].first;
            }

        private:
            const digraph& _ref; // հղում գրաֆին
            index _current = -1; // հերթական դիտարկվող գագաթի ինդեքսը
            std::vector<std::size_t> _degrees; // գագափթների մուտքային կիսաաստիճանները
            std::stack<index> _S; // ինդեքսների ստեկը
        };
};

Մնում է հիմա digraph դասի համար իրականացնել իտերատոր վերադարձնող begin և end մեթոդները։

iterator begin()
{
    return iterator(*this, true);
}

iterator end()
{
    return iterator(*this, false);
}

Իտերատորի բերված իրականացումը և digraph դասի begin և end մեթոդներն այն նվազագույնն են, որոնք ապահովում են range-for տիպի ցիկլի աշխատանքը։