Changeset 4ed84fc in git
 Timestamp:
 Apr 24, 2019, 6:24:28 PM (4 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 e8c12867734cd226cc02891d399506d4e198eb8f
 Parents:
 51b5853275964eb90183d3490cd0f77df75505c1
 Location:
 Singular
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/fpaprops.lib
r51b585 r4ed84fc 877 877 } 878 878 879 proc lpGkDim (ideal G)879 proc lpGkDim_lib(ideal G) 880 880 "USAGE: lpGkDim(G); G an ideal in a letterplace ring 881 881 RETURN: int 
Singular/dyn_modules/freealgebra/freealgebra.cc
r51b585 r4ed84fc 1 1 #include "Singular/libsingular.h" 2 #include <vector> 2 3 3 4 #ifdef HAVE_SHIFTBBA … … 124 125 else return TRUE; 125 126 } 127 128 static intvec ufnarovskiGraph(ideal G) 129 { 130 long l = 0; 131 for (int i = 0; i < IDELEMS(G); i++) 132 l = si_max(pTotaldegree(G>m[i]), l); 133 l; 134 if (l <= 0) 135 WerrorS("Ufnarovski graph not implemented for l <= 0"); 136 int lV = currRing>isLPring; 137 138 ideal words = idMaxIdeal(l); 139 ideal standardWords = kNF(G, currRing>qideal, words); 140 idSkipZeroes(standardWords); 141 142 int n = IDELEMS(standardWords); 143 intvec UG(n, n, 0); 144 for (int i = 0; i < n; i++) 145 { 146 for (int j = 0; j < n; j++) 147 { 148 poly v = standardWords>m[i]; 149 poly w = standardWords>m[j]; 150 151 // check whether v*x1 = x2*w (overlap) 152 bool overlap = true; 153 for (int k = 1; k <= (l  1) * lV; k++) 154 { 155 if (pGetExp(v, k + lV) != pGetExp(w, k)) { 156 overlap = false; 157 break; 158 } 159 } 160 161 if (overlap) 162 { 163 // create the overlap 164 poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing)); 165 166 // check whether the overlap is normal 167 bool normal = true; 168 for (int k = 0; k < IDELEMS(G); k++) 169 { 170 if (p_LPDivisibleBy(G>m[k], p, currRing)) 171 { 172 normal = false; 173 break; 174 } 175 } 176 177 if (normal) 178 { 179 IMATELEM(UG, i + 1, j + 1) = 1; 180 } 181 } 182 } 183 } 184 return UG; 185 } 186 187 static std::vector<int> countCycles(const intvec* _G, int v, std::vector<int> path, std::vector<BOOLEAN> visited, std::vector<BOOLEAN> cyclic, std::vector<int> cache) 188 { 189 intvec* G = ivCopy(_G); // modifications must be local 190 191 if (cache[v] != 2) return cache; // value is already cached 192 193 visited[v] = TRUE; 194 path.push_back(v); 195 196 int cycles = 0; 197 for (int w = 0; w < G>cols(); w++) 198 { 199 if (IMATELEM(*G, v + 1, w + 1)) // edge v > w exists in G 200 { 201 if (!visited[w]) 202 { // continue with w 203 cache = countCycles(G, w, path, visited, cyclic, cache); 204 if (cache[w] == 1) 205 { 206 cache[v] = 1; 207 return cache; 208 } 209 cycles = si_max(cycles, cache[w]); 210 } 211 else 212 { // found new cycle 213 int pathIndexOfW = 1; 214 for (int i = path.size()  1; i >= 0; i) { 215 if (cyclic[path[i]] == 1) { // found an already cyclic vertex 216 cache[v] = 1; 217 return cache; 218 } 219 cyclic[path[i]] = TRUE; 220 221 if (path[i] == w) { // end of the cycle 222 assume(IMATELEM(*G, v + 1, w + 1) != 0); 223 IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v > w 224 pathIndexOfW = i; 225 break; 226 } else { 227 assume(IMATELEM(*G, path[i  1] + 1, path[i] + 1) != 0); 228 IMATELEM(*G, path[i  1] + 1, path[i] + 1) = 0; // remove edge vi1 > vi 229 } 230 } 231 assume(pathIndexOfW != 1); // should never happen 232 for (int i = path.size()  1; i >= pathIndexOfW; i) { 233 cache = countCycles(G, path[i], path, visited, cyclic, cache); 234 if (cache[path[i]] == 1) 235 { 236 cache[v] = 1; 237 return cache; 238 } 239 cycles = si_max(cycles, cache[path[i]] + 1); 240 } 241 } 242 } 243 } 244 cache[v] = cycles; 245 246 delete G; 247 return cache; 248 } 249 250 // 1 is infinity 251 static int graphGrowth(intvec G) 252 { 253 // init 254 int n = G.cols(); 255 std::vector<int> path; 256 std::vector<BOOLEAN> visited; 257 std::vector<BOOLEAN> cyclic; 258 std::vector<int> cache; 259 visited.resize(n, FALSE); 260 cyclic.resize(n, FALSE); 261 cache.resize(n, 2); 262 263 // get max number of cycles 264 int cycles = 0; 265 for (int v = 0; v < n; v++) 266 { 267 cache = countCycles(&G, v, path, visited, cyclic, cache); 268 if (cache[v] == 1) 269 return 1; 270 cycles = si_max(cycles, cache[v]); 271 } 272 return cycles; 273 } 274 275 // 1 is infinity, 2 is error 276 static int id_LPGkDim(ideal G) 277 { 278 if (rField_is_Ring(currRing)) { 279 WerrorS("GKDim not implemented for rings"); 280 return 2; 281 } 282 283 idSkipZeroes(G); // remove zeros 284 for (int i=IDELEMS(G)1;i>=0; i) 285 { 286 G>m[i]>next = NULL; // G = LM(G) 287 if (pGetComp(G>m[i]) != 0) 288 { 289 WerrorS("GKDim not implemented for modules"); 290 return 2; 291 } 292 } 293 id_DelLmEquals(G, currRing); // remove duplicates 294 295 // get the max deg 296 long maxDeg = 0; 297 for (int i = 0; i < IDELEMS(G); i++) 298 { 299 maxDeg = si_max(maxDeg, pTotaldegree(G>m[i])); 300 301 // also check whether G = <1> 302 if (pIsConstantComp(G>m[i])) 303 { 304 WerrorS("GKDim not defined for 0ring"); 305 return 2; 306 } 307 } 308 309 // early termination if G \subset X 310 if (maxDeg <= 1) 311 { 312 int lV = currRing>isLPring; 313 if (IDELEMS(G) == lV) // V = {1} no edges 314 return 0; 315 if (IDELEMS(G) == lV  1) // V = {1} with loop 316 return 1; 317 if (IDELEMS(G) <= lV  2) // V = {1} with more than one loop 318 return 1; 319 } 320 321 intvec UG = ufnarovskiGraph(G); 322 return graphGrowth(UG); 323 } 324 325 326 static BOOLEAN lpGkDim(leftv res, leftv h) 327 { 328 const short t[]={1,IDEAL_CMD}; 329 if (iiCheckTypes(h,t,1)) 330 { 331 assumeStdFlag(h); 332 ideal G=(ideal)h>Data(); 333 res>rtyp = INT_CMD; 334 res>data = (void*)(long) id_LPGkDim(G); 335 if (errorreported) return TRUE; 336 return FALSE; 337 } 338 else return TRUE; 339 } 126 340 #endif 127 341 … … 134 348 p>iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides); 135 349 p>iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt); 350 p>iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim); 351 136 352 p>iiAddCproc("freealgebra.so","stest",TRUE,stest); 137 353 p>iiAddCproc("freealgebra.so","btest",TRUE,btest);
Note: See TracChangeset
for help on using the changeset viewer.