Graphpar: Software para particionar grafos

Problema

O problema da Partição Conexa Balanceada é o seguinte:

dado um inteiro q ≥ 2, um grafo conexo G = (V,A) com uma função peso w : V → Z₊ definida sobre seus vértices, encontrar uma q-partição P = (V₁, V₂, . . . , V_q) de V tal que G[V_i] (subgrafo induzido por V_i) seja conexo para 1 ≤ i ≤ q e o peso do subgrafo mais leve seja o maior possível. Mais formalmente, queremos encontrar uma tal partição que maximiza a função min{w(V_i) : i = 1, . . . , q}.

w(X) denota o peso de um conjunto X, definido como a soma dos pesos de seus elementos.

Software

Download do binário (estático) disponível nas seguintes plataformas:

Como usar

usage: graphpar <graph options> [output options] [-h <heuristic number>] [heuristic options]
  graph options:
        to read a graph from XML:
          -i <input file> (path to XML file)
        to generate a random graph you must provide:
          -v <vertices> (# of vertices)
          -d <density> (graph density in percent)
          -c <clusters> (# of cluters in partition)
          [-w <weight>] (weight of each cluster - optional)
  output options:
        -I prints ampl model with inital solution
        -C prints easy to parse solution
        -y <file> (prints graphml output for yEd)
  heuristc numbers:
        0 = mixed heuristic               O(c^2.n^3.t + c^2.n.m.t)  [default]
        1 = random heuristic              O(c^2.n^2.t)
        2 = fc all 1-trees                O(c^2.n^3.m)
        3 = fc simple                     O(c^2.n^2 + c^2.m.n)
        4 = Chlebikova 3/4-approximation  O(n^3.c^2)                [only for 2-partitions]
        5 = LW 3-partition heutistic      O(n^4.c^2)                [only for 3-partitions]
    n = # of vertices
    m = # of edges
    c = # of clusters
    t = # of tries
  heuristc options:
        -T <time> (max execution time in seconds)
        -t <tries> (set try option of heuristics 0 and 1)           [default = n^2]
        -r (allow random retrys for heuristic 3)                    [default = false]

Exemplos

$ graphpar -i graph.xml

Particiona o grafo especificado em graph.xml

$ graphpar -i graph.xml -h 4

Particiona o grafo especificado em graph.xml usando a aproximação de Chlebíková

$ graphpar -i graph.xml -h 1 -t 10 -T 0.3

Particiona o grafo especificado em graph.xml usando random heuristic com 10 tentativas e por no máximo 0.3 segundos.

$ graphpar -v 30 -d 25 -c 8 -t 100

Particiona um grafo gerado aleatoriamente com 30 vértices e 25 % denso em 8 classes usando o algortimo default com o numero de tentativas = 100

Representação do grafo em XML

Um exemplo da representação de um grafo em XML para o graphpar é o seguinte. Note que um grafo com n vértices tem os índices dos vértices variando de 1 a n orbrigatóriamente.

<?xml version="1.0"?>
<graph nodes="9" arcs="11" clusters="2">
   <nodes>
        <node id="1" weight="2" />
        <node id="2" weight="3" />
        <node id="3" weight="2" />
        <node id="4" weight="1" />
        <node id="5" weight="1" />
        <node id="6" weight="4" />
        <node id="7" weight="6" />
        <node id="8" weight="1" />
        <node id="9" weight="5" />
   </nodes>
   <arcs>
        <arc id="1" from="1" to="6" />
        <arc id="2" from="1" to="2" />
        <arc id="3" from="1" to="7" />
        <arc id="4" from="2" to="3" />
        <arc id="5" from="2" to="4" />
        <arc id="6" from="2" to="5" />
        <arc id="7" from="3" to="4" />
        <arc id="8" from="5" to="6" />
        <arc id="9" from="7" to="9" />
        <arc id="10" from="7" to="8" />
        <arc id="11" from="8" to="9" />
   </arcs>
</graph>

Software de visualização

graphpar tem a opção -y <filename>, que gera o arquivo filename. Esse arquivo contém a representação em graphml da solução que pode ser visualizada com o sofware (freeware) yEd (java webstart). Exemplo:

$ graphpar -i graph.xml -y solution.graphml

A figura a seguir é um exemplo do desenho, gerado pelo yEd, de uma 16-partição de uma árvore com 10000 vértices.