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 or grid.

--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