1 /* ========================================================================== */ 2 /* === Include/Mongoose_EdgeCutProblem.hpp ================================== */ 3 /* ========================================================================== */ 4 5 /* ----------------------------------------------------------------------------- 6 * Mongoose Graph Partitioning Library Copyright (C) 2017-2018, 7 * Scott P. Kolodziej, Nuri S. Yeralan, Timothy A. Davis, William W. Hager 8 * Mongoose is licensed under Version 3 of the GNU General Public License. 9 * Mongoose is also available under other licenses; contact authors for details. 10 * -------------------------------------------------------------------------- */ 11 12 /** 13 * Graph data structure. 14 * 15 * Stores graph adjacency and weight information. Also used as a container for 16 * storing information about matching, coarsening, and partitioning. 17 */ 18 19 // #pragma once 20 #ifndef MONGOOSE_EDGECUTPROBLEM_HPP 21 #define MONGOOSE_EDGECUTPROBLEM_HPP 22 23 #include "Mongoose_CSparse.hpp" 24 #include "Mongoose_Graph.hpp" 25 #include "Mongoose_Internal.hpp" 26 #include "Mongoose_EdgeCutOptions.hpp" 27 28 namespace Mongoose 29 { 30 31 class EdgeCutProblem 32 { 33 public: 34 /** Graph Data ***********************************************************/ 35 Int n; /** # vertices */ 36 Int nz; /** # edges */ 37 Int *p; /** Column pointers */ 38 Int *i; /** Row indices */ 39 double *x; /** Edge weight */ 40 double *w; /** Node weight */ 41 double X; /** Sum of edge weights */ 42 double W; /** Sum of vertex weights */ 43 44 double H; /** Heuristic max penalty to assess */ 45 double worstCaseRatio; 46 47 /** Partition Data *******************************************************/ 48 bool *partition; /** T/F denoting partition side */ 49 double *vertexGains; /** Gains for each vertex */ 50 Int *externalDegree; /** # edges lying across the cut */ 51 Int *bhIndex; /** Index+1 of a vertex in the heap */ 52 Int *bhHeap[2]; /** Heap data structure organized by 53 boundaryGains descending */ 54 Int bhSize[2]; /** Size of the boundary heap */ 55 56 /** Cut Cost Metrics *****************************************************/ 57 double heuCost; /** cutCost + balance penalty */ 58 double cutCost; /** Sum of edge weights in cut set */ 59 Int cutSize; /** Number of edges in cut set */ 60 double W0; /** Sum of partition 0 vertex weights */ 61 double W1; /** Sum of partition 1 vertex weights */ 62 double imbalance; /** Degree to which the partitioning 63 is imbalanced, and this is 64 computed as (0.5 - W0/W). */ 65 66 /** Matching Data ********************************************************/ 67 EdgeCutProblem *parent; /** Link to the parent graph */ 68 Int clevel; /** Coarsening level for this graph */ 69 Int cn; /** # vertices in coarse graph */ 70 Int *matching; /** Linked List of matched vertices */ 71 Int *matchmap; /** Map from fine to coarse vertices */ 72 Int *invmatchmap; /** Map from coarse to fine vertices */ 73 Int *matchtype; /** Vertex's match classification 74 0: Orphan 75 1: Standard (random, hem, shem) 76 2: Brotherly 77 3: Community */ 78 Int singleton; 79 80 /* Constructor & Destructor */ 81 static EdgeCutProblem *create(const Int _n, const Int _nz, Int *_p = NULL, 82 Int *_i = NULL, double *_x = NULL, double *_w = NULL); 83 static EdgeCutProblem *create(const Graph *_graph); 84 static EdgeCutProblem *create(EdgeCutProblem *_parent); 85 ~EdgeCutProblem(); 86 void initialize(const EdgeCut_Options *options); 87 88 /** Matching Functions ****************************************************/ isMatched(Int vertex)89 inline bool isMatched(Int vertex) 90 { 91 return (matching[vertex] > 0); 92 } 93 getMatch(Int vertex)94 inline Int getMatch(Int vertex) 95 { 96 return (matching[vertex] - 1); 97 } 98 createMatch(Int vertexA,Int vertexB,MatchType matchType)99 inline void createMatch(Int vertexA, Int vertexB, MatchType matchType) 100 { 101 matching[vertexA] = (vertexB) + 1; 102 matching[vertexB] = (vertexA) + 1; 103 invmatchmap[cn] = vertexA; 104 matchtype[vertexA] = matchType; 105 matchtype[vertexB] = matchType; 106 matchmap[vertexA] = cn; 107 matchmap[vertexB] = cn; 108 cn++; 109 } 110 createCommunityMatch(Int vertexA,Int vertexB,MatchType matchType)111 inline void createCommunityMatch(Int vertexA, Int vertexB, 112 MatchType matchType) 113 { 114 Int vm[4] = { -1, -1, -1, -1 }; 115 vm[0] = vertexA; 116 vm[1] = getMatch(vm[0]); 117 vm[2] = getMatch(vm[1]); 118 vm[3] = getMatch(vm[2]); 119 120 bool is3Way = (vm[0] == vm[3]); 121 if (is3Way) 122 { 123 matching[vm[1]] = vertexA + 1; 124 createMatch(vm[2], vertexB, matchType); 125 } 126 else 127 { 128 matching[vertexB] = matching[vertexA]; 129 matching[vertexA] = vertexB + 1; 130 matchmap[vertexB] = matchmap[vertexA]; 131 matchtype[vertexB] = matchType; 132 } 133 } 134 135 /** Boundary Heap Functions ***********************************************/ BH_getParent(Int a)136 inline Int BH_getParent(Int a) 137 { 138 return ((a - 1) / 2); 139 } 140 BH_getLeftChild(Int a)141 inline Int BH_getLeftChild(Int a) 142 { 143 return (2 * a + 1); 144 } 145 BH_getRightChild(Int a)146 inline Int BH_getRightChild(Int a) 147 { 148 return (2 * a + 2); 149 } 150 BH_inBoundary(Int v)151 inline bool BH_inBoundary(Int v) 152 { 153 return (bhIndex[v] > 0); 154 } 155 BH_putIndex(Int v,Int pos)156 inline void BH_putIndex(Int v, Int pos) 157 { 158 bhIndex[v] = (pos + 1); 159 } 160 BH_getIndex(Int v)161 inline Int BH_getIndex(Int v) 162 { 163 return (bhIndex[v] - 1); 164 } 165 166 /** Mark Array Functions **************************************************/ mark(Int index)167 inline void mark(Int index) 168 { 169 markArray[index] = markValue; 170 } 171 unmark(Int index)172 inline void unmark(Int index) 173 { 174 markArray[index] = 0; 175 } 176 isMarked(Int index)177 inline bool isMarked(Int index) 178 { 179 return markArray[index] == markValue; 180 } 181 getMarkValue()182 inline Int getMarkValue() 183 { 184 return markValue; 185 } 186 187 void clearMarkArray(); 188 void clearMarkArray(Int incrementBy); 189 190 private: 191 EdgeCutProblem(); 192 193 /** Memory Management Flags ***********************************************/ 194 bool shallow_p; 195 bool shallow_i; 196 bool shallow_x; 197 bool shallow_w; 198 199 /** Mark Data *************************************************************/ 200 Int *markArray; /** O(n) mark array */ 201 Int markValue; /** Mark array can be cleared in O(k) 202 by incrementing markValue. 203 Implicitly, a mark value less than 204 markValue is unmarked. */ 205 void resetMarkArray(); 206 bool initialized; // Used to mark if the graph has been initialized 207 // previously. 208 }; 209 210 } // end namespace Mongoose 211 212 #endif 213