pydcop generate graphcoloring¶
Graph coloring benchmark problem generator¶
Synopsis¶
pydcop generate graphcoloring
--variables_count <variables_count>
--colors_count <colors_count>
--graph <graph_type>
[--allow_subgraph]
[--soft]
[--extensive]
[--noagents]
[--p_edge <p_edge>]
[--m_edge <m_edge>]
Description¶
This command generates graph coloring problems, soft or hard, on several types of graphs.
Graph structures:
Random graph, based on the Erdős-Rényi model
Preferential attachment graph (scale free), based on the Barabási–Albert model
Grid graph
Problems:
Graph coloring, with pseudo-hard constraint where a cost of 10000 is incurred for neighbors sharing the same color and 0 otherwise. These constraints can be expressed intentionally or extensively.
Weighted, or soft graph coloring, with soft constraints where the cost of a join assignment between two neighbors is a random cost, always expressed extensively.
Note: the generated DCOP is written to the standard output. To write it in a file,
you can use the --output <file>
global option.
Options¶
--variables_count <variables_count>
/-v <variables_count>
Number of variables in the problem. If the grid graph structure is used, this number MUST be a valid square side (i.e. \(\sqrt{v}\) must be an
int
).--colors_count <colors_count>
/-c <colors_count>
Number of colors for coloring the graph.
--graph <graph_type>
/--g <graph_type>
Structure of the constraints graph. Can be
random
,scalefree
orgrid
.--allow_subgraph
When generating the graph structure, we only keep graph with no disconnected sub-graph. When this flag is set no filtering is done and you may get disconnected sub-graphs.
--soft
If this flag is set, a weighted graph coloring problem is generated, otherwise a classical (pseudo-) hard graph coloring problem is generated.
--intentional
If this flag is set, constraints are expressed intentionally, otherwise an extensive representation is used (by default). Intentional constraints can only be used for standard graph coloring problems.
--noagents
If this flag is set, no agent definition is generated in the dcop file, otherwise one agent is created for each variable.
--p_edge <p_edge>
/--p <p_edge>
Only used for random graph, probability for edge creation in the random Erdős-Rényi graph creation model.
--m_edge <m_edge>
/--m <m_edge>
Only used for scale-free graph, number of edges to attach from a new variable in the preferential attachment Barabási–Albert graph model
Examples
Generating a random soft graph coloring problem with 10 variables:
pydcop generate graph_coloring --graph random --variables_count 10 \
--colors_count 3 --p_edge 0.5 --soft