29 #define DHEAP_MAX_KEY (1e20) 30 #define DHEAP_MIN_KEY -(1e20) 68 int* RESTRICT stackarr;
72 for(
int i = 0; i <
nnodes; i++ )
73 nodevisited[i] =
FALSE;
75 nodevisited[start] =
TRUE;
77 if( g->
grad[start] == 0 )
84 stackarr[stacksize++] = start;
87 while( stacksize != 0 )
89 const int node = stackarr[--stacksize];
94 const int head = g->
head[
a];
96 if( !nodevisited[head] )
101 nodevisited[head] =
TRUE;
102 stackarr[stacksize++] = head;
121 for(
int i = 0; i <= csr->
nnodes; i++ )
123 if( csr->
start[i] < 0 )
126 printf(
"CSR not set: unset start pointer for entry %d \n", i);
135 if(
LT(csr->
cost[i], 0.0) )
138 printf(
"CSR not set: negative cost for entry %d \n", i);
146 if( csr->
head[i] < 0 )
149 printf(
"CSR not set: unset head for entry %d \n", i);
165 for(
int i = 0; i <= csr->
nnodes; i++ )
168 for(
int i = 0; i < csr->nedges_max; i++ )
224 weight += csr->
cost[i];
237 const int topindex = depository->
ncsrs_curr - 1;
267 assert(index >= 0 && index < depository->
ncsrs_curr);
272 assert(nnodes == depository->
csr_nnodes[index]);
288 assert(index >= 0 && index < depository->
ncsrs_curr);
293 assert(nedges == depository->
csr_nedges[index]);
315 assert(ptr_start >= 0);
316 assert(ptr_data >= 0);
343 assert(g && scip && nodevisited);
344 assert(start >= 0 && start < g->knots);
360 assert(g && scip && nodevisited);
361 assert(start >= 0 && start < g->knots);
363 trail(scip, g, start,
TRUE, nodevisited);
380 assert(reachable !=
NULL);
387 for(
int k = 0; k <
nnodes; k++ )
426 double maximum = 0.0;
434 *central_term = g->
source;
452 for( i = 0; i <
nnodes; i++ )
464 *central_term = center;
473 assert(path !=
NULL);
474 assert(cost !=
NULL);
476 for( i = 0; i <
nnodes; i++ )
479 for( i = 0; i < g->edges; i++ )
482 for( i = 0; i <
nnodes; i++ )
495 for( k = 0; k <
nnodes; k++ )
497 assert((path[k].edge >= 0) || (k == i));
498 assert((path[k].edge >= 0) || (path[k].dist == 0));
504 if( path[k].dist > max )
550 center, minimum, maximum, oldval);
553 *central_term = center;
570 for(
int i = 0; i <
nnodes; i++ )
572 if( g->
grad[i] == 0 )
578 map[i] = nodescount++;
600 assert(ncsrs_max >= 1);
601 assert(ncsrs_max < datasize_max);
644 assert(scip && depository && *depository);
673 assert(depository && csr);
674 assert(index >= 0 && index < depository->
ncsrs_curr);
679 assert(csr->
start[0] == 0);
689 assert(depository && csr);
700 assert(
EQ(weight_org, weight_real));
725 const int datasize_edges = depository->
csr_ptrsData[top_index] + top_nedges;
726 const int datasize_nodes = depository->
csr_ptrsStart[top_index] + top_nnodes + 1;
727 const int datasize =
MAX(datasize_edges, datasize_nodes);
730 assert(top_nedges >= 0);
731 assert(top_nnodes >= 0);
787 for(
int i = depository->
ncsrs_curr - 1; i >= 0; --i )
809 assert(nnodes >= 1 && nedges >= 0);
823 assert(-1 == depository->
csr_nnodes[topindex]);
824 assert(-1 == depository->
csr_nedges[topindex]);
841 const int nedges = 2 * (nnodes - 1);
882 assert(topindex >= 0 && topindex < depository->
ncsrs_max);
915 printf(
"csrdepo (size=%d) contains: \n", ncsrs);
917 for(
int i = 0; i < ncsrs; ++i )
943 int*
const position = heap->
position;
944 const int capacity = heap->
capacity;
946 assert(heap && position);
952 for(
int i = 0; i < capacity; i++ )
966 const int*
const position = heap->
position;
967 const int capacity = heap->
capacity;
969 assert(heap && position);
971 if( heap->
size != 0 )
977 for(
int i = 0; i < capacity; i++ )
1003 assert(scip && heap);
1004 assert(capacity >= 1);
1009 position_heap = position;
1014 entries_heap = entries;
1018 (*heap)->capacity = capacity;
1019 (*heap)->position = position_heap;
1020 (*heap)->entries = entries_heap;
1041 assert(scip && heap);
1080 int*
const RESTRICT position = heap->
position;
1087 const int lastentry = heap->
size--;
1089 assert(heap && position && entries);
1090 assert(heap->
size >= 0);
1092 node = entries[1].node;
1094 assert(position[node] == 1);
1099 while( child < lastentry )
1101 const SCIP_Real key1 = entries[child].key;
1102 const SCIP_Real key2 = entries[child + 1].key;
1109 entries[hole].key = key2;
1114 entries[hole].key = key1;
1117 assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1119 entries[hole].node = entries[child].node;
1120 position[entries[hole].node] = hole;
1128 fill = entries[lastentry].key;
1133 while( entries[parent].
key > fill )
1137 entries[hole] = entries[parent];
1139 assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1141 position[entries[hole].node] = hole;
1149 entries[hole].key = fill;
1150 entries[hole].node = entries[lastentry].node;
1152 assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1154 if( hole != lastentry )
1155 position[entries[hole].node] = hole;
1172 int*
const RESTRICT position = heap->
position;
1178 assert(heap && position && entries);
1181 assert(node >= 0 && node <= heap->capacity);
1182 assert(position[node] !=
CONNECT);
1185 if( position[node] ==
UNKNOWN )
1188 hole = ++(heap->
size);
1192 assert(position[node] >= 1);
1193 hole = position[node];
1195 assert(entries[hole].node == node);
1196 assert(
GE(entries[hole].
key, newkey));
1200 parentkey = entries[parent].key;
1205 while( parentkey > newkey )
1209 entries[hole].key = parentkey;
1210 entries[hole].node = entries[parent].node;
1211 position[entries[hole].node] = hole;
1214 parentkey = entries[parent].key;
1219 entries[hole].key = newkey;
1220 entries[hole].node = node;
1221 position[node] = hole;
1241 assert(nnodes >= 1 && nedges >= 0);
1304 int* RESTRICT start_csr;
1307 const int*
const gOeat = g->
oeat;
1308 const int*
const gHead = g->
head;
1311 assert(csr && edgecosts);
1312 assert(nnodes >= 1);
1313 assert(csr->
nnodes == nnodes);
1316 start_csr = csr->
start;
1317 cost_csr = csr->
cost;
1319 assert(0 == start_csr[0]);
1321 for(
int k = 0; k <
nnodes; k++ )
1323 int pos = start_csr[k];
1327 for(
int e = g->
outbeg[k]; e >= 0; e = gOeat[e] )
1333 assert(gHead[e] == csr->
head[pos] );
1336 cost_csr[pos++] = edgecosts[e];
1340 assert((pos == start_csr[k] + g->
grad[k]) || pcmw);
1341 assert(start_csr[k + 1] == pos);
1344 assert(start_csr[nnodes] <= g->
edges);
1357 int* RESTRICT start_csr;
1358 int* RESTRICT head_csr;
1359 int* RESTRICT edgeid_csr;
1362 const int*
const gOeat = g->
oeat;
1363 const int*
const gHead = g->
head;
1367 assert(csr && edgecosts);
1368 assert(nnodes >= 1);
1369 assert(csr->
nnodes == nnodes);
1372 start_csr = csr->
start;
1373 head_csr = csr->
head;
1374 cost_csr = csr->
cost;
1377 hasEdgeId = (edgeid_csr !=
NULL);
1383 for(
int k = 0; k <
nnodes; k++ )
1385 int pos = start_csr[k];
1389 for(
int e = g->
outbeg[k]; e >= 0; e = gOeat[e] )
1391 const int ehead = gHead[e];
1400 head_csr[pos] = ehead;
1402 edgeid_csr[pos] = e;
1403 cost_csr[pos++] = edgecosts[e];
1407 assert((pos == start_csr[k] + g->
grad[k]) || pcmw);
1409 start_csr[k + 1] = pos;
1412 assert(start_csr[nnodes] <= g->
edges);
1425 const int*
const edgeid = csr->
edge_id;
1430 assert(nnodes >= 1);
1431 assert(csr->
nnodes == nnodes);
1432 assert(nedges <= csr->nedges_max);
1434 assert(edgecosts_csr && edgecosts_g);
1436 for(
int i = 0; i < nedges; i++ )
1438 const int edge_g = edgeid[i];
1440 assert(0 <= edge_g && edge_g < g->edges);
1442 edgecosts_csr[i] = edgecosts_g[edge_g];
1455 const int*
const edgeid = csr->
edge_id;
1460 assert(nnodes >= 1);
1461 assert(csr->
nnodes == nnodes);
1462 assert(nedges <= csr->nedges_max);
1464 assert(edgecosts_csr && edgecosts_g);
1466 for(
int i = 0; i < nedges; i++ )
1468 const int edge_g = edgeid[i];
1470 assert(0 <= edge_g && edge_g < g->edges);
1472 if( !
EQ(edgecosts_csr[i], edgecosts_g[edge_g]) )
1488 assert(csr_in && csr_out);
1523 for(
int k = 0; k < csr->
nnodes; k++ )
1525 for(
int j = csr->
start[k]; j != csr->
start[k + 1]; ++j )
1527 const int head = csr->
head[j];
1530 printf(
" %d->%d, c=%f \n", k, head, cost);
1546 assert(nnodes >= 0);
1547 assert(csr->
start[nnodes] >= 0);
1561 assert(scip && csr);
1566 assert(csrd->
nnodes >= 1);
1569 assert(csrd->
start);
1587 assert(g->
knots >= 1);
1609 assert(g->
knots >= 1);
1642 const int* start = csr->
start;
1644 const int nedges = start[
nnodes];
1645 const int* head = csr->
head;
1652 printf(
"CSR: start first corrupted \n");
1660 printf(
"CSR: start last corrupted %d!=%d \n", start[nnodes], nedges);
1665 for(
int i = 0; i <
nnodes; i++ )
1667 if( start[i] > start[i + 1] )
1670 printf(
"CSR: ranges corrupted \n");
1676 for(
int i = 0; i < nedges; i++ )
1678 const int v = head[i];
1680 if( v < 0 || v >= nnodes )
1683 printf(
"CSR: neighbor entry corrupted \n");
1701 assert(csr && csr->
head && csr->
cost);
1706 printf(
"CSR: wrong node/edge count \n");
1732 const int nedges = g->
edges;
1737 assert(nnodes >= 1);
1753 dcsr->
range = range_csr;
1754 dcsr->
head = head_csr;
1755 dcsr->
edgeid = edgeid_csr;
1757 dcsr->
cost = cost_csr;
1765 for(
int e = 0; e < nedges; e++ )
1768 range_csr[0].
start = 0;
1770 for(
int k = 0; k <
nnodes; k++ )
1772 int pos = range_csr[k].
start;
1774 if( !pcmw || g->
mark[k] )
1778 const int ehead = g->
head[e];
1780 if( pcmw && !g->
mark[ehead] )
1785 id2csr_csr[e] = pos;
1786 head_csr[pos] = ehead;
1787 edgeid_csr[pos] = e;
1788 cost_csr[pos++] = g->
cost[e];
1792 assert(pos == range_csr[k].start + g->
grad[k] || pcmw);
1794 range_csr[k].
end = pos;
1796 if( k != nnodes - 1 )
1797 range_csr[k + 1].
start = range_csr[k].
end;
1800 assert(range_csr[nnodes - 1].end <= nedges);
1836 assert(0 &&
"implement");
1847 int*
const head = dcsr->
head;
1848 int*
const edgeid = dcsr->
edgeid;
1856 assert(tail >= 0 && tail < dcsr->
nnodes);
1857 assert(e_csr >= 0 && e_csr < dcsr->nedges);
1858 assert(range[tail].start <= e_csr && e_csr < range[tail].end);
1860 last = --(range[tail].
end);
1863 id2csredge[edgeid[e_csr]] = -1;
1869 head[e_csr] = head[last];
1870 edgeid[e_csr] = edgeid[last];
1871 id2csredge[edgeid[last]] = e_csr;
1872 cost[e_csr] = cost[last];
1875 cost2[e_csr] = cost2[last];
1878 cost3[e_csr] = cost3[last];
1900 int*
const head = dcsr->
head;
1901 int*
const edgeid = dcsr->
edgeid;
1903 const int erev_csr = id2csredge[
flipedge(edgeid[e_csr])];
1904 const int i1 = head[erev_csr];
1905 const int i2 = head[e_csr];
1907 assert(scip && dcsr);
1908 assert(e_csr >= 0 && edgeid[e_csr] >= 0);
1909 assert(erev_csr >= 0);
1926 const int*
const head = dcsr->
head;
1927 const int*
const edgeid = dcsr->
edgeid;
1928 const int*
const id2csredge = dcsr->
id2csredge;
1930 const int nedges = dcsr->
nedges;
1932 assert(g && dcsr && range && head && edgeid && id2csredge);
1934 if( nnodes != g->
knots || nedges != g->
edges )
1937 printf(
"DCSR: wrong node/edge cound \n");
1941 for(
int i = 0; i <
nnodes; i++ )
1943 const int start = range[i].
start;
1944 const int end = range[i].
end;
1949 printf(
"DCSR: ranges corrupted \n");
1954 for(
int e = start; e < end; e++ )
1956 const int ordedge = edgeid[e];
1958 assert(ordedge >= 0 && ordedge < nedges);
1960 if( id2csredge[ordedge] != e )
1963 printf(
"DCSR: id assignment corrupted \n");
1968 if( head[e] != g->
head[ordedge] || i != g->
tail[ordedge] )
1971 printf(
"DCSR: edge assignment corrupted \n");
1973 printf(
" %d == %d %d == %d \n", head[e], g->
head[ordedge], i, g->
tail[ordedge]);
2000 assert(scip && g && dijkdata);
2020 for(
int k = 0; k <
nnodes; k++ )
2042 assert(scip && dijkdata);
2051 for(
int k = 0; k <
nnodes; k++ )
2059 if( g->
tail[e] == pseudoroot )
2062 if( costs[e] < mincost )
2066 pc_costshift[k] = mincost;
2068 assert(
GT(pc_costshift[k], 0.0));
2074 pc_costshift[k] = 0.0;
2094 for(
int k = 0; k <
nnodes; k++ )
2110 const int*
const visitlist = dijkdata->
visitlist;
2114 const int nvisits = dijkdata->
nvisits;
2116 assert(dijkdata && g);
2117 assert(nvisits >= 0);
2119 for(
int k = 0; k < nvisits; k++ )
2121 const int node = visitlist[k];
2122 assert(node >= 0 && node < g->knots);
2124 visited[node] =
FALSE;
2132 for(
int k = 0; k < g->
knots; k++ )
2134 assert(visited[k] ==
FALSE);
2136 assert(distance[k] ==
FARAWAY);
2148 DIJK* dijk = *dijkdata;
int graph_get_nEdges(const GRAPH *)
static int csrdepoGetTopIndex(const CSRDEPO *depository)
void graph_csrdepo_free(SCIP *scip, CSRDEPO **depository)
SCIP_Bool graph_typeIsDirected(const GRAPH *)
void graph_csr_print(const CSR *csr)
void graph_heap_deleteMin(int *node, SCIP_Real *key, DHEAP *heap)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
#define SCIPfreeMemoryArray(scip, ptr)
void graph_csrdepo_emptyTopSetMarked(CSRDEPO *depository)
SCIP_RETCODE graph_csrdepo_init(SCIP *scip, int ncsrs_max, int datasize_max, CSRDEPO **depository)
#define SCIPallocMemoryArray(scip, ptr, num)
static void csrdepoFillCSR(const CSRDEPO *depository, int index, CSR *csr)
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
SCIP_RETCODE graph_findCentralTerminal(SCIP *scip, const GRAPH *g, int centertype, int *central_term)
static SCIP_RETCODE trail(SCIP *scip, const GRAPH *g, int start, SCIP_Bool costAware, SCIP_Bool *nodevisited)
SCIP_RETCODE graph_init_csrWithEdgeId(SCIP *scip, GRAPH *g)
void graph_csr_buildCosts(const GRAPH *g, const CSR *csr, const SCIP_Real *edgecosts_g, SCIP_Real *RESTRICT edgecosts_csr)
void graph_heap_free(SCIP *scip, SCIP_Bool freePositions, SCIP_Bool freeEntries, DHEAP **heap)
enum SCIP_Retcode SCIP_RETCODE
includes various files containing graph methods used for Steiner tree problems
static void csrdepoCsrUnsetDebug(CSR *csr)
void graph_csrdepo_addEmptyTop(CSRDEPO *depository, int nnodes, int nedges)
void graph_dijkLimited_free(SCIP *scip, DIJK **dijkdata)
void graph_csrdepo_getTopCSR(const CSRDEPO *depository, CSR *csr)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Real csrdepoCsrWeight(const CSR *csr)
#define SCIPfreeBufferArray(scip, ptr)
void graph_csrdepo_print(const CSRDEPO *depository)
void graph_csrdepo_removeTop(CSRDEPO *depository)
static void csrdepoCleanDebug(CSRDEPO *depository)
SCIP_Real * node_distance
SCIP_RETCODE graph_dijkLimited_init(SCIP *scip, const GRAPH *g, DIJK **dijkdata)
SCIP_Bool graph_valid_dcsr(const GRAPH *g, SCIP_Bool verbose)
void graph_free_csr(SCIP *scip, GRAPH *g)
void graph_csr_copy(const CSR *csr_in, CSR *csr_out)
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
SCIP_Bool graph_heap_isClean(const DHEAP *heap)
void graph_dcsr_deleteEdge(DCSR *dcsr, int tail, int e_csr)
SCIP_RETCODE graph_csr_allocWithEdgeId(SCIP *scip, int nnodes, int nedges, CSR **csr)
void graph_csr_build(const GRAPH *g, const SCIP_Real *edgecosts, CSR *csr)
SCIP_RETCODE graph_dijkLimited_initPcShifts(SCIP *scip, const GRAPH *g, DIJK *dijkdata)
void graph_heap_correct(int node, SCIP_Real newkey, DHEAP *heap)
static int csrdepoGetNnodes(const CSRDEPO *depository, int index)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Real csrdepoGetTopWeight(const CSRDEPO *depository)
void graph_csr_chgCosts(const GRAPH *g, const SCIP_Real *edgecosts, CSR *csr)
SCIP_Bool graph_valid_csr(const GRAPH *g, SCIP_Bool verbose)
void graph_csrdepo_getEmptyTop(const CSRDEPO *depository, CSR *csr)
SCIP_RETCODE graph_heap_create(SCIP *scip, int capacity, int *position, DENTRY *entries, DHEAP **heap)
static SCIP_Bool csrdepoCsrIsSet(const CSR *csr, SCIP_Bool verbose)
void graph_buildOrgNodesToReducedMap(const GRAPH *g, int *map)
static int csrdepoGetNedges(const CSRDEPO *depository, int index)
void graph_dcsr_deleteEdgeBi(SCIP *scip, DCSR *dcsr, int e_csr)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void graph_dijkLimited_reset(const GRAPH *g, DIJK *dijkdata)
void graph_csrdepo_addEmptyTopTree(CSRDEPO *depository, int nnodes)
SCIP_RETCODE graph_trail_costAware(SCIP *scip, const GRAPH *g, int start, SCIP_Bool *nodevisited)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Bool graph_csrdepo_hasEmptyTop(const CSRDEPO *depository)
SCIP_Bool graph_csr_costsAreInSync(const GRAPH *g, const CSR *csr, const SCIP_Real *edgecosts_g)
SCIP_RETCODE graph_csr_alloc(SCIP *scip, int nnodes, int nedges, CSR **csr)
void graph_dijkLimited_clean(const GRAPH *g, DIJK *dijkdata)
int graph_csrdepo_getDataSize(const CSRDEPO *depository)
SCIP_Bool graph_csr_isValid(const CSR *csr, SCIP_Bool verbose)
void graph_csrdepo_getCSR(const CSRDEPO *depository, int index, CSR *csr)
void graph_heap_clean(SCIP_Bool cleanposition, DHEAP *heap)
#define BMScopyMemoryArray(ptr, source, num)
void graph_csrdepo_clean(CSRDEPO *depository)
void graph_csr_free(SCIP *scip, CSR **csr)
SCIP_Bool graph_pc_isPc(const GRAPH *)
SCIP_RETCODE graph_init_csr(SCIP *scip, GRAPH *g)
SCIP_Bool graph_csrdepo_isEmpty(const CSRDEPO *depository)
int graph_csrdepo_getNcsrs(const CSRDEPO *depository)
#define SCIPfreeMemory(scip, ptr)
int graph_heap_deleteMinReturnNode(DHEAP *heap)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
void graph_update_dcsr(SCIP *scip, GRAPH *g)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_RETCODE graph_trail_arr(SCIP *scip, const GRAPH *g, int start, SCIP_Bool *nodevisited)
int graph_get_nNodes(const GRAPH *)
SCIP_RETCODE graph_termsReachable(SCIP *scip, const GRAPH *g, SCIP_Bool *reachable)
#define SCIPallocMemory(scip, ptr)
void graph_free_dcsr(SCIP *scip, GRAPH *g)
SCIP_RETCODE graph_init_dcsr(SCIP *scip, GRAPH *g)
includes various reduction methods for Steiner tree problems
int graph_csr_getNedges(const CSR *csr)
void graph_heap_deleteMinGetNode(int *node, DHEAP *heap)