Problem kolorowania wierzchołków grafu.
Każdemu wierzchołkwi grafu przyporządkowujemy liczbę naturalną w taki sposób,
aby oba końce żadnej krawędzi nie miały przypisanej tej samej liczby.Szukamy przyporządkowania wykorzystującego jak najmniej różnych liczb.
Powyżej treść problemu
Rozwiązanie poniżej...
problem jest w tym, że dla grafów ostatnich pojawia się dość duża liczba obrotów licznika.... Graph.Counter (jest taki counter)
Czy można ten algorytm jeszcze jakoś zoptymalizować dla poszczególnych klas grafów (wiem, że to NP-trudny problem). Algorytm musi być z powrotami...
[code]
using System.Collections.Generic ;
using System;
namespace ASD.Graph
{
public static class ColoringExtender
{
// koloruje graf algorytmem zachlannym (byc moze niepotymalnie)
public static int GreedyColor(this IGraph g, out int[] colors)
{
// kazdemu wierzcholkowi
// przydzielamy najmniejszy kolor nie kolidujacy z juz pokolorowanymi sasiadami
// (wpisujemy go do tablicy colors)
// zwracamy liczbe uzytych kolorow
int n = g.VerticesCount;
colors = new int[n];
int nr_koloru = 1;
for (int i = 0; i < n; i++)
{
HashSet<int> NodeColors = new HashSet<int>();
foreach (Edge e in g.OutEdges(i))
{
int kolor = colors[e.To];
if (!NodeColors.Contains(kolor) && kolor != 0)
NodeColors.Add(kolor);
}
if (NodeColors.Count == nr_koloru)
{
++nr_koloru;
colors[i] = nr_koloru;
}
else
{
for (int j = 1; j <= nr_koloru; j++)
{
if (!NodeColors.Contains(j))
{
colors[i] = j;
break;
}
}
}
}
/* ZMIENIC */ //int k=g.VerticesCount;
/* ZMIENIC */ //colors=new int[k];
/* ZMIENIC */ //for ( int i=0 ; i<k ; ++i )
/* ZMIENIC */ // colors[i]=i+1;
/* ZMIENIC */
return nr_koloru;
}
// koloruje graf algorytmem z powrotami (optymalnie)
public static int BacktrackingColor(this IGraph g, out int[] colors)
{
var gc = new Coloring(g);
/*
int EdgesCountFull = -1;
if (g.Directed)
EdgesCountFull = g.VerticesCount * (g.VerticesCount - 1);
else
EdgesCountFull = g.VerticesCount * (g.VerticesCount - 1) / 2;
if (g.EdgesCount == EdgesCountFull)
{
colors = new int[g.VerticesCount];
int n = g.VerticesCount;
for (int i = 1; i <= g.VerticesCount; i++)
colors[i-1] = i;
return n;
}
*/
gc.Color(0, new int[g.VerticesCount], 0);
colors = gc.bestColors;
return gc.bestColorsNumber;
}
// klasa pomocnicza dla algorytmu z powrotami
private sealed class Coloring
{
// tablica pamietajaca najlepsze dotychczas znalezione pokolorowanie
internal int[] bestColors=null;
// zmienna pamietajaca liczbe kolorow w najlepszym dotychczas znalezionym pokolorowaniu
internal int bestColorsNumber;
// badany graf
private IGraph g;
// konstruktor
internal Coloring(IGraph g)
{
this.g=g;
bestColorsNumber=g.VerticesCount+1;
}
// rekurencyjna metoda znajdujaca najlepsze pokolorowanie
// v - wierzcholek do pokolorowania
// colors - tablica kolorow
// n - liczba kolorow uzytych w pokolorowaniu zapisanym w colors
internal void Color(int v ,int[] colors, int n)
{
// tu zaimplementowac algorytm z powrotami
/* ZMIENIC */ //int k=g.VerticesCount;
/* ZMIENIC */ //bestColors=new int[k];
/* ZMIENIC */ //for ( int i=0 ; i<k ; ++i )
/* ZMIENIC */ // bestColors[i]=i+1;
/* ZMIENIC */ //bestColorsNumber=k;
//if (n >= colors.Length)
// throw new Exception("Coś się zwaliło");
if (n >= bestColorsNumber)
return;
if (v >= g.VerticesCount)
{
if (n < bestColorsNumber)
{
bestColorsNumber = n;
bestColors = (int[])colors.Clone();
// Console.WriteLine("ALA");
}
return;
}
HashSet<int> NodeColors = new HashSet<int>();
foreach (Edge e in g.OutEdges(v))
{
if (e.To < v)
{
if (e.To == v)
throw new Exception();
int color = colors[e.To];
if (color != 0 && !NodeColors.Contains(color))
NodeColors.Add(color);
}
}
if (n < NodeColors.Count)
throw new Exception();
int OutDegree = g.OutDegree(v);
if (v % 2 == 0)
{
for (int i = 1; i <= n; i++)
if (!NodeColors.Contains(i))
{
colors[v] = i;
Color(v + 1, colors, n);
}
}
else
{
for (int i = n; i >= 1; i--)
if (!NodeColors.Contains(i))
{
colors[v] = i;
Color(v + 1, colors, n);
}
}
colors[v] = n + 1;
Color(v + 1, colors, n + 1);
//colors[v] = 0;
}
} // class Coloring
} // class ColoringExtender
} // namespace ASD.Graph
[/code]
main.cs
[code]
using System;
using ASD.Graph;
class Zad09
{
public static void Main()
{
int[] backtrackingColors;
int[] greedyColors;
int n,i,j,mb,mg;
long counter0, counter1, counter2;
string[] message1 = { "Zwykly maly graf:",
"Maly dwudzielny:",
"Mala klika:" };
int[] bestColorsNumbers1 = { 4, 2, 9 };
string[] message2 = { "Zwykly graf:",
"Graf dwudzielny:",
"Cykl parzysty:",
"Klika:" };
int[] bestColorsNumbers2 = { 6, 2, 2, 200 };
string[] message3 = { "Zwykly duzy graf:",
"Duzy dwudzielny:",
"Duza klika:" };
int[] bestColorsNumbers3 = { 59, 2, 4000 };
IGraph[] g1 = new IGraph[message1.Length];
IGraph[] g2 = new IGraph[message2.Length];
IGraph[] g3 = new IGraph[message3.Length];
var rgg = new RandomGraphGenerator();
//GraphExport ge = new GraphExport(true, "C:\Users\polgrabiat\Desktop\Graphviz2.26.3\Graphviz2.26.3\bin\dot.exe");
Console.WriteLine();
Console.WriteLine("Generowanie grafow");
Console.WriteLine();
rgg.SetSeed(101);
g1[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph),8,0.5);
rgg.SetSeed(102);
g1[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph),5,3,0.75);
n=9;
g1[2] = new AdjacencyMatrixGraph(false,n);
for ( i=0 ; i<n ; ++i )
for ( j=i+1 ; j<n ; ++ j )
g1[2].AddEdge(i,j);
rgg.SetSeed(103);
g2[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph), 20, 0.5);
rgg.SetSeed(104);
g2[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph), 30, 20, 0.25);
n = 50;
g2[2] = new AdjacencyListsGraph(false, n);
for (i = 1; i < n; ++i)
g2[2].AddEdge(i - 1, i);
g2[2].AddEdge(n - 1, 0);
rgg.SetSeed(105);
g2[2] = rgg.Permute(g2[2]);
n = 200;
g2[3] = new AdjacencyMatrixGraph(false, n);
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
g2[3].AddEdge(i, j);
rgg.SetSeed(106);
g3[0] = rgg.UndirectedGraph(typeof(AdjacencyMatrixGraph), 75, 0.99);
rgg.SetSeed(107);
g3[1] = rgg.BipariteGraph(typeof(AdjacencyMatrixGraph), 2000, 2000, 0.55);
n = 5000;
g3[2] = new AdjacencyMatrixGraph(false, n);
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
g3[2].AddEdge(i, j);
//Console.WriteLine("{0}", g3[2].EdgesCount);
Console.WriteLine();
for ( i=0 ; i<g1.Length ; ++i )
{
// ge.Export(g1[i], "ala");
counter0=Graph.Counter;
mb=g1[i].BacktrackingColor(out backtrackingColors);
counter1=Graph.Counter;
mg=g1[i].GreedyColor(out greedyColors);
counter2=Graph.Counter;
Console.WriteLine("{0,-17} liczba wierzcholkow {1,4}, optymalna liczba kolorow {2,4}", message1[i], g1[i].VerticesCount, bestColorsNumbers1[i]);
Console.WriteLine(" Backtracking: liczba kolorow {0,4}, zlozonosc {1,8}", mb, counter1-counter0);
Console.WriteLine(" Greedy: liczba kolorow {0,4}, zlozonosc {1,8}", mg, counter2-counter1);
Console.WriteLine();
}
Console.WriteLine();
for (i = 0; i < g2.Length; ++i)
{
counter0 = Graph.Counter;
mb = g2[i].BacktrackingColor(out backtrackingColors);
counter1 = Graph.Counter;
mg = g2[i].GreedyColor(out greedyColors);
counter2 = Graph.Counter;
Console.WriteLine("{0,-17} liczba wierzcholkow {1,4}, optymalna liczba kolorow {2,4}", message2[i], g2[i].VerticesCount, bestColorsNumbers2[i]);
Console.WriteLine(" Backtracking: liczba kolorow {0,4}, zlozonosc {1,8}", mb, counter1 - counter0);
Console.WriteLine(" Greedy: liczba kolorow {0,4}, zlozonosc {1,8}", mg, counter2 - counter1);
Console.WriteLine();
}
Console.WriteLine();
for (i = 0; i < g3.Length; ++i)
{
counter0 = Graph.Counter;
mb = g3[i].BacktrackingColor(out backtrackingColors);
counter1 = Graph.Counter;
mg = g3[i].GreedyColor(out greedyColors);
counter2 = Graph.Counter;
Console.WriteLine("{0,-17} liczba wierzcholkow {1,4}, optymalna liczba kolorow {2,4}", message3[i], g3[i].VerticesCount, bestColorsNumbers3[i]);
Console.WriteLine(" Backtracking: liczba kolorow {0,4}, zlozonosc {1,8}", mb, counter1 - counter0);
Console.WriteLine(" Greedy: liczba kolorow {0,4}, zlozonosc {1,8}", mg, counter2 - counter1);
Console.WriteLine();
}
Console.WriteLine("Koniec");
Console.WriteLine();
}
}
[/code]