/** *************************************************************
strong_edge_reducible.cpp -- Written by Derrick Stolee
Last edited: 11/19/2014
To compile, place this file in the nauty/ folder after unpacking the
nauty source code, available at http://cs.anu.edu.au/~bdm/nauty/
Compile using the following command:
gcc -o strong_edge_reducible strong_edge_reducible.c nauty.o nausparse.o nautil.o gtools.o
Then, run :
strong_edge_reducible < inputfile.txt
or (for 6 colors) :
strong_edge_reducible -k 6 < inputfile.txt
This is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This 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 General Public License for more details.
You should have received a copy of the GNU General Public License
along with SearchLib. If not, see .
*************************************************************/
#include
#include
#include
#include "nausparse.h"
#include "gtools.h"
/**
* is_deletion_reducible : Given a graph g, the list of vertices to delete (deleting edges that have both endpoints in this set)
* and a number of colors, determine if this is reducible for strong k-edge-colorings!
*/
int is_deletion_reducible(sparsegraph* g, int* del_vert_list, int num_del_verts, int k);
/**
* Given a graph g and an ordering of (a subset of) its edges, return the graph on the edge list
* where two edges are adjacent if and only if they have common endpoints or endpoints that are adjacent.
*/
sparsegraph* strong_edge_graph(sparsegraph* g, int* edge_list, int num_edges);
/**
* the main executable
*
* optional parameter "-k #" allows you to change the number of colors.
*
* Reads from standard input until end-of-file or an empty line:
* - A label for the graph
* - A sparse 6 representation of a graph
* - A space-separated list of vertices in the deletion set
*
* Will check if each is reducible or not.
*/
int main(int argc, char** argv)
{
int k = 5;
int i,j;
for ( i = 0; i < argc; i++ )
{
if (strcmp(argv[i], "-k") == 0 && i < argc - 1 )
{
k = atoi(argv[i+1]);
}
}
size_t buflen = 500;
char* buffer = (char*)malloc(buflen);
while ( getline(&buffer, &buflen, stdin) > 0 )
{
if ( strlen(buffer) <= 1 )
{
break;
}
buffer[strlen(buffer) - 1] = 0;
char* name = (char*)malloc(strlen(buffer)+1);
strcpy(name, buffer);
getline(&buffer, &buflen, stdin);
sparsegraph* g = (sparsegraph*)malloc(sizeof(sparsegraph));
SG_INIT((*g));
int num_loops = 0;
stringtosparsegraph(buffer, g, &num_loops);
getline(&buffer, &buflen, stdin);
// read the line to receive the deletion set.
int num_del = 0;
int* del_set = (int*)malloc(g->nv * sizeof(int));
bzero(del_set, g->nv * sizeof(int));
char* next = buffer;
next = strtok(next, " ");
while ( next != 0 )
{
int contains_number_character = 0;
int j = 0;
for ( j = 0; j < strlen(next); j++ )
{
if ( next[j] >= '0' && next[j] <= '9')
{
contains_number_character++;
}
}
if ( contains_number_character == 0 )
{
break;
}
int i = atoi(next);
del_set[i] = 1;
num_del++;
printf("%d ", i);
next = strtok(NULL, " ");
}
printf("\n");
int* edge_list = (int*)malloc(g->nde * sizeof(int));
int* del_edge_list = (int*)malloc(g->nde * sizeof(int));
int num_edges = 0;
int num_del_edges = 0;
for ( i = 0; i < g->nv; i++ )
{
for ( j = 0; j < g->d[i]; j++ )
{
int v = g->e[ g->v[i] + j ];
if ( v > i )
{
edge_list[2 * num_edges] = i;
edge_list[2 * num_edges + 1] = v;
if ( del_set[i] == 1 || del_set[v] == 1 )
{
// printf("delete edge (%2d) : %d %d\n", num_edges, i, v);
del_edge_list[num_del_edges++] = num_edges;
}
else
{
// printf("keep edge (%2d) : %d %d\n", num_edges, i, v);
}
num_edges++;
}
}
}
sparsegraph* seg = strong_edge_graph(g, edge_list, num_edges);
int result = is_deletion_reducible(seg, del_edge_list, num_del_edges, k);
printf("Configuration %s ", name);
if ( result )
{
printf("is");
}
else
{
printf("IS NOT");
}
printf(" %d-reducible.\n\n", k);
SG_FREE((*g));
free(g);
g = 0;
free(del_set);
del_set = 0;
free(del_edge_list);
free(edge_list);
free(name);
}
free(buffer);
return 0;
}
/**
* g - the graph
* coloring_order - a permutation of the vertices
* num_colored - How many already have a color
* colors - the colors assigned to each vertex. -1 for uncolored
* color_domains - a bitmask of the available colors at each vertex. Should have n*n entries, for deepening!
* k - how many colors to use
*/
int can_extend_coloring(sparsegraph* g, int* coloring_order, int num_colored, int* colors, int* color_domains, int k, int cur_max_color)
{
if ( num_colored >= g->nv )
{
return 1;
}
// extend color domains using previous color
if ( num_colored > 0 )
{
int* new_color_domains = &(color_domains[g->nv]);
int i = 0;
for ( i = 0; i < g->nv; i++ )
{
new_color_domains[i] = color_domains[i];
}
color_domains = new_color_domains;
int v = coloring_order[num_colored-1];
int c = colors[v];
for ( i = 0; i < g->d[v]; i++ )
{
int u = g->e[ g->v[v] + i ];
if ( colors[u] < 0 )
{
// Uncolored!
// remove c from the domain.
color_domains[u] &= ~(1 << c);
if ( color_domains[u] == 0 )
{
// no way to extend!
return 0;
}
}
}
}
else
{
// initialize color domains!
int i = 0;
for ( i = 0; i < g->nv; i++ )
{
color_domains[i] = (1 << k) - 1;
}
}
int v = coloring_order[num_colored];
int c = 0;
for ( c = 0; c < k && c <= cur_max_color; c++ )
{
if ( (color_domains[v] & (1 << c)) != 0 )
{
colors[v] = c;
int cmc_append = 0;
if ( c == cur_max_color )
{
cmc_append = 1;
}
int result = can_extend_coloring(g, coloring_order, num_colored+1, colors, color_domains, k, cur_max_color + cmc_append);
colors[v] = -1;
if ( result == 1 )
{
return 1;
}
}
}
return 0;
}
int is_deletion_reducible_recurse(sparsegraph* g, int num_del_verts, int* coloring_order, int num_colored, int* colors, int* color_domains, int k, int cur_max_color)
{
if ( num_colored >= g->nv - num_del_verts )
{
int result = can_extend_coloring(g, coloring_order, num_colored, colors, color_domains, k, cur_max_color);
if ( result == 0 )
{
// print the coloring!
printf("Fails on Coloring: ");
int i = 0;
for ( i = 0;i < num_colored; i++ )
{
printf("%d : %d, ", coloring_order[i], colors[coloring_order[i]]);
}
printf("\n");
}
return result;
}
// extend color domains using previous color
if ( num_colored > 0 )
{
int* new_color_domains = &(color_domains[g->nv]);
int i = 0;
for ( i = 0; i < g->nv; i++ )
{
new_color_domains[i] = color_domains[i];
}
color_domains = new_color_domains;
int v = coloring_order[num_colored-1];
int c = colors[v];
for ( i = 0; i < g->d[v]; i++ )
{
int u = g->e[ g->v[v] + i ];
if ( colors[u] < 0 )
{
// Uncolored!
// remove c from the domain.
color_domains[u] &= ~(1 << c);
if ( color_domains[u] == 0 )
{
// no way to extend!
return 0;
}
}
}
}
else
{
// initialize color domains!
int i = 0;
for ( i = 0; i < g->nv; i++ )
{
color_domains[i] = (1 << k) - 1;
}
}
int v = coloring_order[num_colored];
// Want: for all colorings, the coloring extends
int big_result = 1;
int c = 0;
for ( c = 0; c <= cur_max_color; c++ )
{
if ( (color_domains[v] & (1 << c)) != 0 )
{
colors[v] = c;
int cmc_append = 0;
if ( c == cur_max_color )
{
cmc_append = 1;
}
int result = is_deletion_reducible_recurse(g, num_del_verts, coloring_order, num_colored+1, colors, color_domains, k, cur_max_color + cmc_append);
colors[v] = -1;
if ( result == 0 )
{
return 0;
}
}
}
return big_result;
}
int is_deletion_reducible(sparsegraph* g, int* del_vert_list, int num_del_verts, int k)
{
int* coloring_order = (int*)malloc(g->nv * sizeof(int));
int* colors = (int*)malloc(g->nv*sizeof(int));
int* color_domains = (int*)malloc(g->nv * g->nv * sizeof(int));
int nco = 0;
// printf("Color Order: ");
int i = 0;
for ( i = 0; i < g->nv; i++ )
{
colors[i] = -1;
int is_del = 0;
int j = 0;
for ( j = 0; j < num_del_verts; j++ )
{
if ( i == del_vert_list[j] )
{
is_del = 1;
break;
}
}
if ( is_del == 0 )
{
coloring_order[nco++] = i;
// printf("%d ", i);
}
}
// printf("| ");
for ( i = 0; i < num_del_verts; i++ )
{
// printf("%d ", del_vert_list[i]);
coloring_order[nco++] = del_vert_list[i];
}
// printf("\n");
int result = is_deletion_reducible_recurse(g, num_del_verts, coloring_order, 0, colors, color_domains, k, 0);
free(colors);
free(color_domains);
free(coloring_order);
return result;
}
sparsegraph* strong_edge_graph(sparsegraph* g, int* edge_list, int num_edges)
{
sparsegraph* seg = (sparsegraph*)malloc(sizeof(sparsegraph));
SG_INIT((*seg));
seg->nv = num_edges;
seg->nde = 0;
seg->vlen = seg->nv;
seg->dlen = seg->nv;
seg->v = (int*)malloc(seg->nv * sizeof(int));
seg->d = (int*)malloc(seg->nv * sizeof(int));
int num_strong_dedges = 0;
int i = 0;
for ( i = 0; i < num_edges; i++ )
{
seg->v[i] = num_strong_dedges;
int u = edge_list[2*i];
int v = edge_list[2*i+1];
int di = 0;
int j = 0;
for ( j = 0; j < g->d[u]; j++ )
{
int x = g->e[g->v[u]+j];
di += g->d[x];
}
for ( j = 0; j < g->d[v]; j++ )
{
int x = g->e[g->v[v]+j];
int adj_to_u = 0;
int jj = 0;
for ( jj = 0; jj < g->d[u]; jj++ )
{
int xx = g->e[g->v[u] + jj];
if ( x == xx )
{
adj_to_u = 1;
}
}
if ( adj_to_u == 0 )
{
di += g->d[x];
}
}
seg->d[i] = di;
num_strong_dedges += di;
}
seg->elen = num_strong_dedges;
seg->e = (int*)malloc(num_strong_dedges*sizeof(int));
for ( i = 0; i < num_edges; i++ )
{
int u = edge_list[2*i];
int v = edge_list[2*i+1];
int di = 0;
int j = 0;
for ( j = 0; j < g->d[u]; j++ )
{
int x = g->e[g->v[u]+j];
int t = 0;
for ( t = 0; t < g->d[x]; t++ )
{
int y = g->e[g->v[x] + t];
int ii = 0;
for ( ii = 0; ii < num_edges; ii++ )
{
if ( (edge_list[2*ii] == x && edge_list[2*ii+1] == y )||(edge_list[2*ii] == y && edge_list[2*ii+1] == x ) )
{
// add adjacency!
seg->e[seg->v[i] + di] = ii;
di++;
}
}
}
}
for ( j = 0; j < g->d[v]; j++ )
{
int x = g->e[g->v[v]+j];
int adj_to_u = 0;
int jj = 0;
for ( jj = 0; jj < g->d[u]; jj++ )
{
int xx = g->e[g->v[u] + jj];
if ( x == xx )
{
adj_to_u = 1;
}
}
if ( adj_to_u == 0 )
{
int t = 0;
for ( t = 0; t < g->d[x]; t++ )
{
int y = g->e[g->v[x] + t];
int ii = 0;
for ( ii = 0; ii < num_edges; ii++ )
{
if ( (edge_list[2*ii] == x && edge_list[2*ii+1] == y )||(edge_list[2*ii] == y && edge_list[2*ii+1] == x ))
{
// add adjacency!
seg->e[seg->v[i] + di] = ii;
di++;
}
}
}
}
}
seg->d[i] = di;
}
return seg;
}