GraphColoring/GraphOrdering.h

Go to the documentation of this file.

/************************************************************************************
    Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen,
    Alex Pothen

    This file is part of ColPack.

    ColPack is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    ColPack 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 Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with ColPack.  If not, see <http://www.gnu.org/licenses/>.
************************************************************************************/

#ifndef GRAPHORDERING_H
#define GRAPHORDERING_H

using namespace std;

namespace ColPack
{
        class GraphOrdering : public GraphInputOutput
        {
        public:

                int GetMaxBackDegree();

                int OrderVertices(string s_OrderingVariant);

        private:


                int GetBackDegree(int index);

                //Private Function 1301
                int CheckVertexOrdering(string s_VertexOrderingVariant);

                int printVertexEdgeMap(vector< vector< pair< int, int> > > &vvpii_VertexEdgeMap);

        protected:

                double m_d_OrderingTime;

                string m_s_VertexOrderingVariant;

                vector<int> m_vi_OrderedVertices; // m_vi_OrderedVertices.size() = m_vi_Vertices.size() - 1

        public:

                //Public Constructor 1351
                GraphOrdering();

                //Public Destructor 1352
                ~GraphOrdering();

                //Virtual Function 1353
                virtual void Clear();

                //Public Function 1354
                int NaturalOrdering();

                int RandomOrdering();

                int ColoringBasedOrdering(vector<int> &vi_VertexColors);

                //Public Function 1355
                int LargestFirstOrdering();

                //Public Function 1357
                int DistanceTwoLargestFirstOrdering();

                //Public Function 1356
                int DynamicLargestFirstOrdering();

                int DistanceTwoDynamicLargestFirstOrdering();

                //Public Function 1358
                int SmallestLastOrdering();

                //Public Function 1359
                int DistanceTwoSmallestLastOrdering();

                //Public Function 1360
                int IncidenceDegreeOrdering();

                //Public Function 1361
                int DistanceTwoIncidenceDegreeOrdering();

                //Public Function 1362
                string GetVertexOrderingVariant();

                //Public Function 1363
                void GetOrderedVertices(vector<int> &output);

                void PrintVertexOrdering();

                //Public Function 1364
                double GetVertexOrderingTime();
        };
}
#endif