A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://scip.zib.de/doc/html/compute__symmetry__nauty_8c_source.php below:

SCIP Doxygen Documentation: src/symmetry/compute_symmetry_nauty.c Source File

39#pragma GCC diagnostic ignored "-Wunused-variable" 40#pragma GCC diagnostic ignored "-Wredundant-decls" 41#pragma GCC diagnostic ignored "-Wpedantic" 44#include "nauty/nauty.h" 45#include "nauty/nausparse.h" 47#include "nauty/traces.h" 50#pragma GCC diagnostic warning "-Wunused-variable" 51#pragma GCC diagnostic warning "-Wredundant-decls" 52#pragma GCC diagnostic warning "-Wpedantic" 62#include "tinycthread/tinycthread.h" 82#if defined(_Thread_local) 113

nauty_kill_request = 1;

129 for

(

int

j = 0; j < permlen; ++j)

131 if

( (

int

) p[j] != j )

191 "symmetry computation terminated early, because number of cells %d in Nauty exceeds limit of %d\n"

,

194 "for running full symmetry detection, increase value of parameter propagating/symmetry/nautymaxncells\n"

);

200 "symmetry computation terminated early, because number of" 203 "for running full symmetry detection, increase value of" 204 " parameter propagating/symmetry/nautymaxnnodes\n"

);

210

nauty_kill_request = 1;

236

nauty_kill_request = 1;

252 for

(j = 0; j < permlen; ++j)

254 if

( (

int

) p[j] != j )

305

assert(symgraph !=

NULL

);

315 if

( first < 0 && second < 0 )

321 if

( first < 0 || second < 0 )

327 if

( first >= 0 && second >= 0 )

335 else if

( first >= 0 )

365 int

** colorstostore,

366 int

* ncolorstostore,

382

assert( SG !=

NULL

|| determinesize );

383

assert( internodeid !=

NULL

);

384

assert( *internodeid >= 0 );

385

assert( degrees !=

NULL

);

386

assert( maxdegrees !=

NULL

);

387

assert( *maxdegrees > 0 );

389

assert( nedges !=

NULL

);

390

assert( neighbors !=

NULL

);

391

assert( colors !=

NULL

);

392

assert( naddednodes !=

NULL

);

393

assert( naddededges !=

NULL

);

394

assert( commonnodeidx <= *internodeid );

403

curcolor = colors[0];

405 for

(e = 1; e < nneighbors; ++e)

408 if

( colors[e] != curcolor )

414

(*degrees)[*internodeid] = 1;

415

++(*degrees)[commonnodeidx];

416

(*colorstostore)[*internodeid] = curcolor;

418 for

(f = curstart; f < e; ++f)

420

assert( neighbors[f] <= *internodeid );

421

++(*degrees)[*internodeid];

422

++(*degrees)[neighbors[f]];

427

SG->e[edgestartpos[commonnodeidx]++] = *internodeid;

428

SG->e[edgestartpos[*internodeid]++] = commonnodeidx;

430 for

(f = curstart; f < e; ++f)

432

SG->e[edgestartpos[neighbors[f]]++] = *internodeid;

433

SG->e[edgestartpos[*internodeid]++] = neighbors[f];

437

*naddededges += e - curstart + 1;

440

curcolor = colors[e];

451

(*degrees)[*internodeid] = 1;

452

++(*degrees)[commonnodeidx];

453

(*colorstostore)[*internodeid] = curcolor;

455 for

(f = curstart; f < nneighbors; ++f)

457

assert( neighbors[f] <= *internodeid );

458

++(*degrees)[*internodeid];

459

++(*degrees)[neighbors[f]];

464

SG->e[edgestartpos[commonnodeidx]++] = *internodeid;

465

SG->e[edgestartpos[*internodeid]++] = commonnodeidx;

467 for

(f = curstart; f < nneighbors; ++f)

469

SG->e[edgestartpos[*internodeid]++] = neighbors[f];

470

SG->e[edgestartpos[neighbors[f]]++] = *internodeid;

474

*naddededges += nneighbors - curstart + 1;

499 int

* groupfirsts =

NULL

;

500 int

* groupseconds =

NULL

;

501 int

* groupcolors =

NULL

;

503 int

edgebegincnt = 0;

515

assert( symgraph !=

NULL

);

516

assert( SG !=

NULL

|| determinesize );

518

assert( nedges !=

NULL

);

519

assert( degrees !=

NULL

);

520

assert( maxdegrees !=

NULL

);

521

assert( colors !=

NULL

);

522

assert( ncolors !=

NULL

);

523

assert( success !=

NULL

);

533

nvarnodestoadd = nsymvars;

537

nvarnodestoadd = 2 * nsymvars;

553 for

(j = 0; j < *

nnodes

; ++j)

560 for

(j = 0; j < nvarnodestoadd; ++j)

570 for

(j = 0; j < *

nnodes

; ++j)

572

SG->d[j] = (*degrees)[j];

573

SG->v[j] = (size_t) (

unsigned

) edgebegincnt;

574

pos[j] = edgebegincnt;

575

edgebegincnt += (*degrees)[j];

599

first += nvarnodestoadd;

601

second = -second - 1;

603

second += nvarnodestoadd;

615

groupfirsts[ngroupedges] = first;

616

groupseconds[ngroupedges] = second;

620

groupfirsts[ngroupedges] = second;

621

groupseconds[ngroupedges] = first;

628

assert(0 <= first && first < *

nnodes

);

629

assert(0 <= second && second < *

nnodes

);

639

++(*degrees)[second];

640

(*degrees)[internodeid] = 2;

648

assert( internodeid < *

nnodes

);

651

SG->e[pos[first]++] = internodeid;

652

SG->e[pos[internodeid]++] = first;

653

SG->e[pos[second]++] = internodeid;

654

SG->e[pos[internodeid]++] = second;

656

assert( first == *

nnodes

- 1 || pos[first] <= (

int

) SG->v[first+1] );

657

assert( second == *

nnodes

- 1 || pos[second] <= (

int

) SG->v[second+1] );

658

assert( internodeid == *

nnodes

- 1 || pos[internodeid] <= (

int

) SG->v[internodeid+1] );

668

++(*degrees)[second];

674

SG->e[pos[first]++] = second;

675

SG->e[pos[second]++] = first;

677

assert( first == *

nnodes

- 1 || pos[first] <= (

int

) SG->v[first+1] );

678

assert( second == *

nnodes

- 1 || pos[second] <= (

int

) SG->v[second+1] );

685 if

( ngroupedges > 0 )

694

firstnodeidx = groupfirsts[0];

696 for

(j = 1; j < ngroupedges; ++j)

699 if

( groupfirsts[j] != firstnodeidx )

702

degrees, maxdegrees, colors, ncolors,

nnodes

, nedges, firstnodeidx, &groupseconds[firstidx],

703

&groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );

706

firstnodeidx = groupfirsts[j];

711

*nedges += naddededges;

718

degrees, maxdegrees, colors, ncolors,

nnodes

, nedges, firstnodeidx, &groupseconds[firstidx],

719

&groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );

724

*nedges += naddededges;

738 for

(j = 0; j < nvarnodestoadd; ++j)

744 for

(j = 0; j < nsymvars; ++j)

746

SG->e[pos[j]++] = j + nsymvars;

747

SG->e[pos[j + nsymvars]++] = j;

749

assert( pos[j] <= (

int

) SG->v[j+1] );

750

assert( j + nsymvars == *

nnodes

- 1 || pos[j+nsymvars] <= (

int

) SG->v[j+nsymvars+1] );

794 int

* nnodesfromgraph1,

802 int

* nvarused1 =

NULL

;

803 int

* nvarused2 =

NULL

;

804 int

* varlabel =

NULL

;

805 int

* groupfirsts =

NULL

;

806 int

* groupseconds =

NULL

;

807 int

* groupcolors =

NULL

;

810 int

edgebegincnt = 0;

826

assert( graph1 !=

NULL

);

827

assert( graph2 !=

NULL

);

828

assert( SG !=

NULL

|| determinesize );

830

assert( nedges !=

NULL

);

831

assert( degrees !=

NULL

);

832

assert( maxdegrees !=

NULL

);

833

assert( colors !=

NULL

);

834

assert( ncolors !=

NULL

);

835

assert( nusedvars !=

NULL

);

836

assert( ! determinesize || nnodesfromgraph1 !=

NULL

);

837

assert( success !=

NULL

);

860

nvarnodestoadd = nsymvars;

864

nvarnodestoadd = 2 * nsymvars;

872 for

(e = 0; e < nsymedges; ++e)

877

nvarused1[-first - 1] += 1;

879

nvarused1[-second - 1] += 1;

884

nvarused2[-first - 1] += 1;

886

nvarused2[-second - 1] += 1;

889 for

(j = 0; j < nvarnodestoadd; ++j)

892 if

( nvarused1[j] != nvarused2[j] )

903

varlabel[j] = nusdvars++;

924 for

(j = 0; j < *

nnodes

; ++j)

926

SG->d[j] = (*degrees)[j];

927

SG->v[j] = (size_t) (

unsigned

) edgebegincnt;

928

pos[j] = edgebegincnt;

929

edgebegincnt += (*degrees)[j];

943 for

(i = 0; i < 2; ++i)

946

symgraph = i == 0 ? graph1 : graph2;

953 for

(j = 0; j < nvarnodestoadd; ++j)

955 if

( varlabel[j] >= 0 )

958

(*degrees)[nodeshift + varlabel[j]] = 0;

969

(*degrees)[nodeshift + nusdvars + j] = 0;

978 for

(j = 0; j < nvarnodestoadd; ++j)

980 if

( varlabel[j] >= 0 )

987

internodeid = nodeshift + curnnodes;

988 for

(e = 0; e < nsymedges; ++e)

995

first = varlabel[-first - 1];

997

first = nusdvars + first;

999

second = varlabel[-second - 1];

1001

second = nusdvars + second;

1011

groupfirsts[ngroupedges] = nodeshift + first;

1012

groupseconds[ngroupedges] = nodeshift + second;

1016

groupfirsts[ngroupedges] = nodeshift + second;

1017

groupseconds[ngroupedges] = nodeshift + first;

1024

assert(0 <= first && first < *

nnodes

);

1025

assert(0 <= second && second < *

nnodes

);

1030 if

( determinesize )

1035

++(*degrees)[nodeshift + first];

1036

++(*degrees)[nodeshift + second];

1037

(*degrees)[internodeid] = 2;

1040

(*colors)[internodeid] = nusdvars + color;

1047

assert( internodeid < *

nnodes

);

1049

SG->e[pos[internodeid]++] = nodeshift + first;

1050

SG->e[pos[internodeid]++] = nodeshift + second;

1051

SG->e[pos[nodeshift + first]++] = internodeid;

1052

SG->e[pos[nodeshift + second]++] = internodeid;

1054

assert( internodeid == *

nnodes

- 1

1055

|| pos[internodeid] <= (

int

) SG->v[internodeid+1] );

1056

assert( nodeshift + first == *

nnodes

- 1

1057

|| pos[nodeshift + first] <= (

int

) SG->v[nodeshift+first+1] );

1058

assert( nodeshift + second == *

nnodes

- 1 ||

1059

pos[nodeshift + second] <= (

int

) SG->v[nodeshift+second+1] );

1066 if

( determinesize )

1068

++(*degrees)[nodeshift + first];

1069

++(*degrees)[nodeshift + second];

1074

SG->e[pos[nodeshift + first]++] = nodeshift + second;

1075

SG->e[pos[nodeshift + second]++] = nodeshift + first;

1077

assert( nodeshift+first == *

nnodes

- 1 || pos[nodeshift+first] <= (

int

) SG->v[nodeshift+first+1] );

1078

assert( nodeshift+second == *

nnodes

- 1 || pos[nodeshift+second] <= (

int

) SG->v[nodeshift+second+1] );

1085 if

( ngroupedges > 0 )

1094

firstnodeidx = groupfirsts[0];

1096 for

(j = 1; j < ngroupedges; ++j)

1099 if

( groupfirsts[j] != firstnodeidx )

1102

degrees, maxdegrees, colors, ncolors,

nnodes

, nedges, firstnodeidx,

1103

&groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );

1106

firstnodeidx = groupfirsts[j];

1108 if

( determinesize )

1111

*nedges += naddededges;

1113

curnnodes += naddednodes;

1119

degrees, maxdegrees, colors, ncolors,

nnodes

, nedges, firstnodeidx,

1120

&groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );

1122 if

( determinesize )

1125

*nedges += naddededges;

1127

curnnodes += naddednodes;

1133 if

( determinesize )

1135 for

(j = 0; j < nusdvars; ++j)

1136

++(*degrees)[nodeshift + j];

1137

(*nedges) += nusdvars / 2;

1141 for

(j = 0; j < nusdvars/2; ++j)

1143

SG->e[pos[nodeshift+j]++] = nodeshift + j + nusdvars/2;

1144

SG->e[pos[nodeshift + j + nusdvars/2]++] = nodeshift + j;

1146

assert( pos[nodeshift+j] <= (

int

) SG->v[nodeshift+j+1] );

1147

assert( nodeshift+j+nusdvars/2 == *

nnodes

- 1

1148

|| pos[nodeshift+j+nusdvars/2] <= (

int

) SG->v[nodeshift+j+nusdvars/2+1] );

1152

nodeshift = curnnodes;

1155 if

( determinesize && i == 0 )

1156

*nnodesfromgraph1 = *

nnodes

;

1160 if

( determinesize )

1166 for

(j = 0; j < *

nnodes

- 1; ++j)

1169

(*nedges) += *

nnodes

- 1;

1170

(*colors)[*

nnodes

- 1] = 8;

1174 for

(j = 0; j < *

nnodes

- 1; ++j)

1176

SG->e[pos[j]++] = *

nnodes

- 1;

1177

SG->e[pos[*

nnodes

-1]++] = j;

1191 if

( determinesize )

1192

*nusedvars = nusdvars;

1205static const char nautyname

[] = {

'N'

,

'a'

,

'u'

,

't'

,

'y'

,

' '

, NAUTYVERSIONID/10000 +

'0'

,

'.'

, (NAUTYVERSIONID%10000)/1000 +

'0'

,

'.'

, (NAUTYVERSIONID%1000)/10 +

'0'

,

'\0'

};

1207static const char nautyname

[] = {

'T'

,

'r'

,

'a'

,

'c'

,

'e'

,

's'

,

' '

, NAUTYVERSIONID/10000 +

'0'

,

'.'

, (NAUTYVERSIONID%10000)/1000 +

'0'

,

'.'

, (NAUTYVERSIONID%1000)/10 +

'0'

,

'\0'

};

1220 return "Computing Graph Automorphism Groups by Brendan D. McKay (https://users.cecs.anu.edu.au/~bdm/nauty/)"

;

1222 return "Computing Graph Automorphism Groups by Adolfo Piperno (https://pallini.di.uniroma1.it/)"

;

1267

DEFAULTOPTIONS_SPARSEGRAPH(options);

1270 static

DEFAULTOPTIONS_TRACES(options);

1278

*log10groupsize = 0;

1284

options.writeautoms =

FALSE

;

1286

options.defaultptn =

FALSE

;

1290

options.writeautoms =

FALSE

;

1291

options.userautomproc = traceshook;

1292

options.defaultptn =

FALSE

;

1299

&degrees, &maxdegrees, &colors, &ncolors, &success) );

1304 "Stopped symmetry computation: Symmetry graph would become too large.\n"

);

1311

SG_ALLOC(SG, (

size_t

)

nnodes

, 2 * (

size_t

)(

unsigned

) nedges,

"malloc"

);

1314

SG.nde = (size_t) (

unsigned

) (2 * nedges);

1318

&degrees, &maxdegrees, &colors, &ncolors, &success) );

1328 for

(v = 0; v <

nnodes

; ++v)

1335 for

(v = 0; v <

nnodes

; ++v)

1337 if

( v <

nnodes

-1 && colors[v] == colors[v+1] )

1359

sparsenauty(&SG, lab, ptn, orbits, &options, &stats,

NULL

);

1361

Traces(&SG, lab, ptn, orbits, &options, &stats,

NULL

);

1391

*log10groupsize = log10(stats.grpsize1 * pow(10.0, (

SCIP_Real

) stats.grpsize2));

1416

assert( G1 !=

NULL

);

1417

assert( G2 !=

NULL

);

1425

&colors, &ncolors, &nusedvars, &nnodesfromG1, &success) );

1442

DEFAULTOPTIONS_SPARSEGRAPH(options);

1445 static

DEFAULTOPTIONS_TRACES(options);

1452

options.writeautoms =

FALSE

;

1454

options.defaultptn =

FALSE

;

1457

options.writeautoms =

FALSE

;

1458

options.userautomproc = traceshook;

1459

options.defaultptn =

FALSE

;

1465

SG_ALLOC(SG, (

size_t

)

nnodes

, 2 * (

size_t

)(

unsigned

) nedges,

"malloc"

);

1468

SG.nde = (size_t) (

unsigned

) (2 * nedges);

1472

&colors, &ncolors, &nusedvars,

NULL

, &success) );

1477#ifdef SCIP_DISABLED_CODE 1482 for

(v = 0; v < SG.nv; ++v)

1487 for

(v = 0; v < SG.nv; ++v)

1492 for

(v = 0; v < SG.nv; ++v)

1494 for

(

int w

= 0;

w

< SG.d[v]; ++

w

)

1507 for

(v = 0; v <

nnodes

; ++v)

1514 for

(v = 0; v <

nnodes

; ++v)

1516 if

( v <

nnodes

-1 && colors[v] == colors[v+1] )

1522#ifdef SCIP_DISABLED_CODE 1525 for

(v = 0; v < SG.nv; ++v)

1546

sparsenauty(&SG, lab, ptn, orbits, &options, &stats,

NULL

);

1548

Traces(&SG, lab, ptn, orbits, &options, &stats,

NULL

);

1566 for

(

int

i = 0; i < nnodesfromG1; ++i)

interface for symmetry computations

static _Thread_local NAUTY_DATA data_

SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)

const char * SYMsymmetryGetName(void)

static const char nautyname[]

static void nautyhook(int count, int *p, int *orbits, int numorbits, int stabvertex, int n)

const char * SYMsymmetryGetAddName(void)

SCIP_Bool SYMcanComputeSymmetry(void)

const char * SYMsymmetryGetDesc(void)

static SCIP_RETCODE createOrDetermineSizeGraphCheck(SCIP *scip, SYM_GRAPH *graph1, SYM_GRAPH *graph2, SCIP_Bool determinesize, sparsegraph *SG, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int **colors, int *ncolors, int *nusedvars, int *nnodesfromgraph1, SCIP_Bool *success)

static void nautyterminationhook(graph *g, int *lab, int *ptn, int level, int numcells, int tc, int code, int m, int n)

static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges(SCIP *scip, sparsegraph *SG, int *edgestartpos, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int **colorstostore, int *ncolorstostore, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)

static SCIP_RETCODE createOrDetermineSizeGraph(SCIP *scip, SYM_GRAPH *symgraph, SCIP_Bool determinesize, sparsegraph *SG, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int **colors, int *ncolors, SCIP_Bool *success)

static SCIP_Bool isEdgeGroupable(SYM_GRAPH *symgraph, int edgeidx, SCIP_Bool groupbycons)

const char * SYMsymmetryGetAddDesc(void)

SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *symgraph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)

Constraint handler for linear constraints in their most general form, .

constraint handler for nonlinear constraints specified by algebraic expressions

#define SCIP_CALL_ABORT(x)

private functions to work with algebraic expressions

power and signed power expression handlers

variable expression handler

void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)

void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)

SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)

#define SCIPfreeBlockMemoryArray(scip, ptr, num)

#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)

#define SCIPallocClearBufferArray(scip, ptr, num)

int SCIPcalcMemGrowSize(SCIP *scip, int num)

#define SCIPallocBufferArray(scip, ptr, num)

#define SCIPfreeBufferArray(scip, ptr)

#define SCIPallocBlockMemoryArray(scip, ptr, num)

#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)

#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)

#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)

SCIP_Real SCIPgetSolvingTime(SCIP *scip)

void SCIPsortIntInt(int *intarray1, int *intarray2, int len)

void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)

SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)

int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)

SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)

int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)

int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)

SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)

int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)

int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)

int SCIPgetSymgraphNVars(SYM_GRAPH *graph)

SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)

int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)

int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)

int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)

public methods for memory management

methods for dealing with symmetry detection graphs

enum SCIP_Retcode SCIP_RETCODE

enum SYM_Symtype SYM_SYMTYPE

enum SYM_Nodetype SYM_NODETYPE

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4