TopoSort< T, C > Struct Template Reference

#include <utils.h>

Public Member Functions
	TopoSort ()
void	node (T n)
void	edge (T left, T right)
void	sort_worker (const T &n, std::set< T, C > &marked_cells, std::set< T, C > &active_cells, std::vector< T > &active_stack)
bool	sort ()

Data Fields
bool	analyze_loops
bool	found_loops
std::map< T, std::set< T, C >, C >	database
std::set< std::set< T, C > >	loops
std::vector< T >	sorted

Detailed Description

template<typename T, typename C = std::less<T>>
struct TopoSort< T, C >

Definition at line 132 of file utils.h.

Constructor & Destructor Documentation

template<typename T, typename C = std::less<T>>

TopoSort< T, C >::TopoSort ( )

inline

Definition at line 139 of file utils.h.

    {
        analyze_loops = true;
        found_loops = false;
    }

Member Function Documentation

template<typename T, typename C = std::less<T>>

void TopoSort< T, C >::edge ( T  left, T  right  )

inline

Definition at line 151 of file utils.h.

    {
        node(left);
        database[right].insert(left);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T, typename C = std::less<T>>

void TopoSort< T, C >::node ( T  n )

inline

Definition at line 145 of file utils.h.

    {
        if (database.count(n) == 0)
            database[n] = std::set<T, C>();
    }

Here is the caller graph for this function:

template<typename T, typename C = std::less<T>>

bool TopoSort< T, C >::sort ( )

inline

Definition at line 194 of file utils.h.

    {
        loops.clear();
        sorted.clear();
        found_loops = false;

        std::set<T, C> marked_cells;
        std::set<T, C> active_cells;
        std::vector<T> active_stack;

        for (auto &it : database)
            sort_worker(it.first, marked_cells, active_cells, active_stack);

        log_assert(GetSize(sorted) == GetSize(database));
        return !found_loops;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T, typename C = std::less<T>>

void TopoSort< T, C >::sort_worker ( const T &  n, std::set< T, C > &  marked_cells, std::set< T, C > &  active_cells, std::vector< T > &  active_stack  )

inline

Definition at line 157 of file utils.h.

    {
        if (active_cells.count(n)) {
            found_loops = true;
            if (analyze_loops) {
                std::set<T, C> loop;
                for (int i = GetSize(active_stack)-1; i >= 0; i--) {
                    loop.insert(active_stack[i]);
                    if (active_stack[i] == n)
                        break;
                }
                loops.insert(loop);
            }
            return;
        }

        if (marked_cells.count(n))
            return;

        if (!database.at(n).empty())
        {
            if (analyze_loops)
                active_stack.push_back(n);
            active_cells.insert(n);

            for (auto &left_n : database.at(n))
                sort_worker(left_n, marked_cells, active_cells, active_stack);

            if (analyze_loops)
                active_stack.pop_back();
            active_cells.erase(n);
        }
        
        marked_cells.insert(n);
        sorted.push_back(n);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

template<typename T, typename C = std::less<T>>

bool TopoSort< T, C >::analyze_loops

Definition at line 134 of file utils.h.

template<typename T, typename C = std::less<T>>

std::map<T, std::set<T, C>, C> TopoSort< T, C >::database

Definition at line 135 of file utils.h.

template<typename T, typename C = std::less<T>>

bool TopoSort< T, C >::found_loops

Definition at line 134 of file utils.h.

template<typename T, typename C = std::less<T>>

std::set<std::set<T, C> > TopoSort< T, C >::loops

Definition at line 136 of file utils.h.

template<typename T, typename C = std::less<T>>

std::vector<T> TopoSort< T, C >::sorted

Definition at line 137 of file utils.h.

---

The documentation for this struct was generated from the following file:

• utils.h