/usr/include/ColPack/GraphOrdering.h is in libcolpack-dev 1.0.9-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | /************************************************************************************
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
{
/** @ingroup group1
* @brief class GraphOrdering in @link group1@endlink.
This class stores the ordered vertices as a vector of vertex identifiers to be used by coloring methods.
*/
class GraphOrdering : public GraphInputOutput
{
public:
///Calculate and return the Maximum Back degree
/**
Precondition: OrderVertices() has been called, i.e. m_vi_OrderedVertices has been populated
Note: Back degree of a vertex is the degree of that vertex
in the subgraph consisting of vertices that had been ordered (i.e., the vertices that are ordered before the current vertex).
Depend on the ordering style, each vertex in vector m_vi_OrderedVertices may have different Back degree.
The Maximum Back degree of all vertices in the graph will be returned.
This is the UPPER BOUND for the number of colors needed to D1-color the graph.
//*/
int GetMaxBackDegree();
int OrderVertices(string s_OrderingVariant);
/// Test and make sure that the ordering is valid. Return 0 if the ordering is invalid, 1 if the ordering is valid.
/** This routine will test for:
- Duplicated vertices. If there is no duplicated vertex, this ordering is probably ok.
- Invalid vertex #. The vertex # should be between 0 and ordering.size()
Actually make a call to "bool isValidOrdering(vector<int> & ordering, int offset = 0);"
*/
int CheckVertexOrdering();
private:
/// Get Back Degree of vertex m_vi_OrderedVertices[index]
/**
Precondition: OrderVertices() has been called, i.e. m_vi_OrderedVertices has been populated
Note: This function is written quickly so it is not optimal
//*/
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();
void ClearOrderingONLY();
//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();
int SmallestLastOrdering_serial();
//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);
vector <int>* GetOrderedVerticesPtr(){ return &m_vi_OrderedVertices; }
void PrintVertexOrdering();
//Public Function 1364
double GetVertexOrderingTime();
};
}
#endif
|