Adjacency Class Reference

Public Member Functions
void	setNbVertices (const size_t &s)
void	reserve (const size_t &s)
void	addEdge (const int &a, const int &b)
Vint	CuthillMckee () const
void	printStats (const Vint &perm) const
void	printPermutation (const vector< int > &perm) const

Private Member Functions
size_t	degree (const size_t &i) const
size_t	pickRoot (const Vint &mask, size_t &lower_bound) const

Private Attributes
vector< Vint >	_Adj
size_t	_N

Detailed Description

Definition at line 84 of file cpp_reorder_elements.cpp.

Member Function Documentation

addEdge()

void Adjacency::addEdge ( const int & a, const int & b )

inline

Definition at line 181 of file cpp_reorder_elements.cpp.

    {
        _Adj[a].push_back(b);
    }

CuthillMckee()

Vint Adjacency::CuthillMckee ( ) const

inline

Definition at line 188 of file cpp_reorder_elements.cpp.

    {
        Vint dist(_N,-1);
        Vint order(_N,-1);
        size_t lowerBound = 0;
        size_t nextIndex = 0;
 
        while (nextIndex < _N)
        {
            const size_t root = pickRoot(order, lowerBound);
            //assert(dist[root] == -1);
            //assert(order[root] == -1);
            dist[root] = 0;
            order[root] = nextIndex++;
            size_t currentDist = 0;
            deque<int> currentVertices(1, root);
            while(currentVertices.size() > 0)
            {
                const int current = currentVertices.front();
                currentVertices.pop_front();
                currentDist = dist[current] + 1;
                multiset<pair<int, int>> nextVertices;
                for (const auto &next : _Adj[current])
                {
                    if (dist[next] == -1)
                    {
                        dist[next] = currentDist;
                        nextVertices.insert(make_pair(degree(next), next));
                    }
                }
                for(const auto &next : nextVertices)
                {
                    order[next.second] = nextIndex++;
                    currentVertices.push_back(next.second);
                }
            }
        }
        // order["old"] = "new"
        return order;
    }

degree()

size_t Adjacency::degree ( const size_t & i ) const

inlineprivate

Definition at line 91 of file cpp_reorder_elements.cpp.

    {
        return _Adj[i].size();
    }

pickRoot()

size_t Adjacency::pickRoot ( const Vint & mask, size_t & lower_bound ) const

inlineprivate

Definition at line 101 of file cpp_reorder_elements.cpp.

    {
        size_t root = 0;
 
        // pick next available root
        for (root = lower_bound; root < _N; root++)
        {
            if (mask[root] == -1)
            {
                break;
            }
        }
 
        int maxLevel = -1;
        bool continueLoop = true;
        size_t iter = 0;
 
        while(continueLoop && iter < _N)
        {
            iter++;
            size_t currentDist = 0;
            Vint level(_N, -1); // level[i] = distance to root  or -1 if not visited yet
            deque<int> currentVertices(1, root);
            level[root] = 0;
            while(currentVertices.size() > 0)
            {
 
                const int current = currentVertices.front();
                if (level[current] > level[root] || (level[current] == level[root] && degree(current) > degree(root)))
                {
                    //the new root is the vertex with the highest level
                    // with level > -1 (i.e. reachable from the current root)
                    root = current;
                } else if(level[current] == level[root] && degree(current) == degree(root))
                {
                    if(current < root)
                    {
                        root = current;
                    }
                }
 
                currentVertices.pop_front();
                currentDist = level[current] + 1;
                for(const auto &next : _Adj[current])
                {
                    if (level[next] == -1)
                    {
                        level[next] = currentDist;
                        currentVertices.push_back(next);
                    }
                }
            }
 
            if(maxLevel < level[root])
            { // continue if we have found a new root
                maxLevel = level[root];
            }else
            { // stop if we have not found a new root
                continueLoop = false;
            }
        }
 
        //assert(mask[root] == -1);
        return root;
    }

printPermutation()

void Adjacency::printPermutation ( const vector< int > & perm ) const

inline

Definition at line 258 of file cpp_reorder_elements.cpp.

    {
        ofstream outfile;
        outfile.open("spy_matrices.m");
        outfile << "clear all; \n";
        outfile << " A = sparse(" << _N << "," << _N << "); \n";
        outfile << " P = zeros(" << _N << ",1); \n";
        for (size_t i = 0; i < _N; ++i)
        {
            outfile << "P(" << perm[i] + 1 << ")=" << i + 1 << "; \n";
        }
        for (size_t i = 0; i < _N; ++i)
        {
            for (const auto &j : _Adj[i])
            {
                outfile << "A(" << i + 1 << "," << j + 1 << ") = 1; \n";
            }
        }
        outfile.close();
    }

printStats()

void Adjacency::printStats ( const Vint & perm ) const

inline

Definition at line 229 of file cpp_reorder_elements.cpp.

    {
        int newMaxBandwidth = 0;
        long long int newSumBandwidth = 0;
        int oldMaxBandwidth = 0;
        long long int oldSumBandwidth = 0;
        Vint iperm(perm.size());
        for (size_t i = 0; i < perm.size(); ++i)
        {
            iperm[perm[i]] = i;
        }
        for (size_t i = 0; i < _N; ++i)
        {
            for (const auto &j : _Adj[i])
            {
                const int newBandwidth = abs(perm[i] - perm[j]);
                newMaxBandwidth = max(newMaxBandwidth, newBandwidth);
                newSumBandwidth += newBandwidth;
                const int oldBandwidth = abs(((int)i) - j);
                oldMaxBandwidth = max(oldMaxBandwidth, oldBandwidth);
                oldSumBandwidth += oldBandwidth;
            }
        }
        if (_N > 1)
        {
            cout << "n:" << _N << " Old/New Max: " << ((double)oldMaxBandwidth)<<"/"<<((double)newMaxBandwidth);
            cout << " Sum: " << ((double)oldSumBandwidth)<<"/"<<((double)newSumBandwidth) << endl;
        }
    }

reserve()

void Adjacency::reserve ( const size_t & s )

inline

Definition at line 173 of file cpp_reorder_elements.cpp.

    {
        for (auto &a : _Adj)
        {
            a.reserve(s);
        }
    }

setNbVertices()

void Adjacency::setNbVertices ( const size_t & s )

inline

Definition at line 168 of file cpp_reorder_elements.cpp.

    {
        _N = s;
        _Adj.resize(_N);
    }

Field Documentation

_Adj

vector<Vint> Adjacency::_Adj

private

Definition at line 87 of file cpp_reorder_elements.cpp.

_N

size_t Adjacency::_N

private

Definition at line 88 of file cpp_reorder_elements.cpp.

---

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

• starter/source/spmd/cpp_reorder_elements.cpp