No output with the clique cover?

[bsubercaseaux]

Hi,

No matter what I pass to the flag --output_filename (described in the --help), I don't get any files written. How do I see the ECC obtained by the program?

[darrenstrash]

Hi Bernardo,

I believe the output feature may not be implemented, as I was focused on reporting the size in my experiments. I can implement the feature this week on a branch for you to try. Do you mind sharing a graph you are testing with? I will make sure the feature works for your graph.

Best,
Darren

[bsubercaseaux]

Thanks! https://pastebin.com/t9Gmy98R I've put a graph (in the edge list representation that the tool seems to take) here. Running it with the ReduIG mode for instance gives me the following output:

input_vertices=50
input_edges=298
Done with reductions
ecc_reduction_time=0.0006
ecc_reduction_offset=0
ecc_kernel_vertices=50
ecc_kernel_all_edges=596
ecc_kernel_uncovered_edges=596
vcc_converted_vertices=596
vcc_converted_edges=14760
time_ecc_to_vcc=0.0034
kernel build
VERTEX CLIQUE COVERING PROBLEM (CCP) SOLVER
version 0.2
Finding clique coverings using our heuristic...
GIS:
Run 1:
The algorithm found a an independent set of size 64.
IG-GCC:
Run 575:
Time		VCC	IS
0.014623	118	64
 [iterations: 0][independent set: 64]

The algorithm needed 118 cliques.

On average, it took 0 seconds and 0 iterations. Success rate: 0 / 1.
Final results: IG-GCC: 118.00, BRE: 0.00, GIS: 64.00, RLS-IS: 64.00
Approximation: 1.843750, discrepancy: 54
kernel solve
BEGIN_OUTPUT_FOR_TABLES
run_type=ReduIG
vcc_reduction_time=0.0096
vcc_reduction_offset=0
vcc_kernel_vertices=574
vcc_kernel_edges=13237
total_time_to_best=0.0147
ig_time=0.0011
time_to_best_without_unwind=0.0151
total_solution=118
verified_cover=passed
optimal=unknown

[darrenstrash]

Thanks! I had a few things come up but I should have an implementation for you next week.

[darrenstrash]

Hi Bernardo,

I have implemented the feature on the branch print_ecc. Please try it out. When I run your graph with the following, it writes the cover to cover.txt:

./optimized/redu3ecc --run_type=Redu3IG --solver_time_limit=10 --output_filename=cover.txt er-graph.txt

And gives the following output:

Reading the graph
Initializing the cover object
input_vertices=50
input_edges=596
Preparing to run reductions...
Done with reductions
ecc_reduction_time=0.0003
ecc_reduction_offset=0
ecc_kernel_vertices=50
ecc_kernel_all_edges=596
ecc_kernel_uncovered_edges=596
vcc_converted_vertices=596
vcc_converted_edges=14760
time_ecc_to_vcc=0.0020
kernel build
VERTEX CLIQUE COVERING PROBLEM (CCP) SOLVER
version 0.2
Finding clique coverings using our heuristic...
GIS:
Run 1:
The algorithm found a an independent set of size 64.
IG-GCC:
Run 575:
Time VCC IS
0.008331 118 64
0.008812 116 64
0.009062 106 64
0.009310 105 64
0.009561 100 64
0.010054 99 64
0.010304 98 64
0.010553 96 64
0.011295 95 65
0.014170 94 66
0.021765 93 66
0.029045 92 68
0.031658 91 68
0.036592 90 69
0.054794 89 70
0.057017 88 70
0.077793 87 71
[iterations: 41109][independent set: 72]

The algorithm needed 87 cliques.

On average, it took 0 seconds and 0 iterations. Success rate: 0 / 1.
Final results: IG-GCC: 87.00, BRE: 0.00, GIS: 64.00, RLS-IS: 72.00
Approximation: 1.208333, discrepancy: 15
kernel solve
BEGIN_OUTPUT_FOR_TABLES
run_type=Redu3IG
vcc_reduction_time=0.0054
vcc_reduction_offset=0
vcc_kernel_vertices=574
vcc_kernel_edges=13237
time_to_best_with_unwind=0.0780
ig_solver_time=0.0701
time_to_unwind_vcc_reductions=0.0000
time_to_unwind_ecc_to_vcc=0.0001
time_to_best_without_unwind=0.0778
total_solution=87
vcc_verified_cover=passed
ecc_verified_cover=passed
solution_is_optimal=unknown
NOTE: Writing cover to cover.txt ...

[bsubercaseaux]

Thanks a lot!