Official Utilities for the CG:SHOP 2022 Challenge
This package provides some utilities for handling instances and solutions for the CG:SHOP 2022 Challenge on Minimum Partition into Plane Subgraphs. These are the tools that are used by us, the (technical) organizers, to handle our instances and your solutions.
- Reading and writing instances.
- Reading and writing solutions.
- Verifying solutions for correctness.
The source code can be found here.
Installation
The installation is simple. Clone this repository, change into the folder, and execute
pip install .
This automatically builds the native C++-core (requires g++). There can be linking issues when using conda because conda uses a different clib than your system.
If pip
does not install the dependencies for you you may also need
pip install networkx
The verification component is implemented in C++ and requires a C++17-capable C++ compiler to be installed. On Linux and MacOS systems, installing a current version of the default C++ compiler (g++ or clang++) should be sufficient.
Reading and Writing Instances
Instances can be read as follows.
from cgshop2022utils.io import read_instance
instance = read_instance("path or file object to instance")
The instance is a dict of the following format:
{
"type": "Instance_CGSHOP2022",
"id": "unique name of instance",
"meta": dict, # with information on the instance (e.g., the polygon for visibility instances)
"graph": networkx.Graph, # The instance graph with typing.Tuple[int, int] as vertices.
}
Check out the documentation of networkx on how to deal with the graphs. It is fairly straight forward. For example:
print("Points:")
for v in graph.nodes:
print(v)
print("Edges:")
for v,w in graph.edges:
print(v, "<->", w)
Conversely, instance files can also be written to files:
from cgshop2022utils.io import write_instance
write_instance('path_or_stream', graph, 'unique_instance_name', {'some': 'meta', 'info': 1})
Reading and Writing Solutions
Similarly to instances, solutions can be read and written using the cgshop2022utils.io
package.
from cgshop2022utils.io import read_solution, write_solution
# read a solution; this returns a dict {'instance': 'unique_instance_name', 'num_colors': 42, 'colors': [0, 1, ...]}
# raises ValueError if the file contents do not seem to be a valid solution
some_solution = read_solution('path_or_stream')
#list_of_colors = ... # compute a List[int] of colors such that list_of_colors[i] is the color of edge i in the instance
write_solution('path_or_stream', 'unique_instance_name', list_of_colors)
Verifying a Solution for an Instance
Verifying a coloring can be done using the method verify_coloring
as follows.
from cgshop2022utils.verify import verify_coloring
from cgshop2022utils.io import read_instance, read_solution
instance = read_instance('some_instance_file')
solution = read_solution('some_solution_for_that_instance') # solution['instance'] should be instance['id']
error, num_colors = verify_coloring(instance, solution['colors'], expected_num_colors=solution['num_colors'])
if error is None:
# solution is valid and uses exactly num_colors distinct colors
else:
# solution is invalid. error is a ColoringError object and error.message describes the error
The expected_num_colors
parameter is optional.
It causes the method to return a ColoringError if the coloring uses more colors than expected_num_colors
.
The first parameter can also be a networkx
graph as in instance['graph']
.
If it has an idx
edge attribute (as the graphs returned by read_instance
have), that attribute determines the order of edges.
If the graph has no such attribute, the order of edges in instance.edges
is used.
It is also possible to pass a list of Tuple[Tuple[int,int], Tuple[int,int]]
or
Tuple[int, int, int, int]
as first parameter.