Hranové obarvení grafu – Delphi – Fórum – Programujte.com

Chtel bych poradit s hranovým obarvením vůbec si s tím nevím rady. Chci prostě když udělám graf tak zmáčknu tlačítko a obarví se mi hrany, které spolu nesousedí. za jakoukoliv radu děkuji předem...

A v jaké seš fázi? Máš uložený graf? Jak? Už ho umíš vykreslit?

Jinak je to o změne "statusu" hrany, na který se bude reagovat při vykreslení tak, že nastavíš pero na jinou barvu.

unit editro_grafu;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls;

type
TForm1 = class(TForm)
Image1: TImage;
Label1: TLabel;
Label2: TLabel;
procedure Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
procedure Image1DblClick(Sender: TObject);
procedure Image1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
vertex: byte;
vertexCount: byte;
vertexCoord: array [1..100] of TPoint;
matrix: array [1..100, 1..100] of boolean;
edge: boolean;
mcoord: TPoint;

implementation

{$R *.dfm}


procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
var i, j: byte;
begin
Label1.Caption:= IntToStr(X);
Label2.Caption:= IntToStr(Y);
if edge then begin
Image1.Canvas.PenPos:= vertexCoord[vertex];
Image1.Canvas.Pen.Color:= clWhite;
Image1.Canvas.LineTo(mcoord.X, mcoord.Y);
Image1.Canvas.PenPos:= vertexCoord[vertex];
Image1.Canvas.Pen.Color:= clBlack;
Image1.Canvas.LineTo(X, Y);
for i:= 1 to vertexCount do begin
for j:= i to vertexCount do begin
if matrix[i, j] then begin
Image1.Canvas.PenPos:= vertexCoord[i];
Image1.Canvas.LineTo(vertexCoord[j].X, vertexCoord[j].Y);
end;
end;
Image1.Canvas.Ellipse(vertexCoord[i].X - 10, vertexCoord[i].Y - 10, vertexCoord[i].X + 10, vertexCoord[i].Y + 10);
end;
end;
mcoord.X:= X;
mcoord.Y:= Y;
end;

procedure TForm1.Image1DblClick(Sender: TObject);
var i: integer;
draw: boolean;
begin
draw:= true;
for i:= 1 to vertexCount do
if (vertexCoord[i].X > mcoord.X - 20) and (vertexCoord[i].X < mcoord.X + 20) and (vertexCoord[i].Y > mcoord.Y - 20) and (vertexCoord[i].Y < mcoord.Y + 20) then
draw:= false;
if draw then begin
Image1.Canvas.PenPos:= mcoord;
Image1.Canvas.Ellipse(mcoord.X - 10, mcoord.Y - 10, mcoord.X + 10, mcoord.Y + 10);
inc(vertexCount);
vertexCoord[vertexCount]:= mcoord;
edge:= false;
end;
end;

procedure TForm1.Image1Click(Sender: TObject);
var i: integer;
begin
if edge then begin
for i:= 1 to vertexCount do
if (vertexCoord[i].X > mcoord.X - 10) and (vertexCoord[i].X < mcoord.X + 10) and (vertexCoord[i].Y > mcoord.Y - 10) and (vertexCoord[i].Y < mcoord.Y + 10) then begin
edge:= false;
Image1.Canvas.PenPos:= vertexCoord[vertex];
Image1.Canvas.Pen.Color:= clWhite;
Image1.Canvas.LineTo(mcoord.X, mcoord.Y);
Image1.Canvas.Pen.Color:= clBlack;
Image1.Canvas.PenPos:= vertexCoord[vertex];
Image1.Canvas.LineTo(vertexCoord[i].X, vertexCoord[i].Y);
matrix[i, vertex]:= true;
matrix[vertex, i]:= true;
Image1.Canvas.Ellipse(vertexCoord[i].X - 10, vertexCoord[i].Y - 10, vertexCoord[i].X + 10, vertexCoord[i].Y + 10);
Image1.Canvas.Ellipse(vertexCoord[vertex].X - 10, vertexCoord[vertex].Y - 10, vertexCoord[vertex].X + 10, vertexCoord[vertex].Y + 10);
end;
end else begin
for i:= 1 to vertexCount do
if (vertexCoord[i].X > mcoord.X - 10) and (vertexCoord[i].X < mcoord.X + 10) and (vertexCoord[i].Y > mcoord.Y - 10) and (vertexCoord[i].Y < mcoord.Y + 10) then begin
edge:= true;
vertex:= i;
Image1.Canvas.PenPos:= vertexCoord[i];
end;
end;
end;

initialization

begin
for vertexCount:= 1 to 100 do
for vertex:= 1 to 100 do
matrix[vertexCount, vertex]:= false;
vertexCount:= 0;
end;


end.

a nevím jak dál

Například takto ... přidáš si pole barev (nebo bool/int hodnot, to je jedno), při vložení bodů a hran uložíš i černou barvu (na stejný index). Po stisku tlačítka projdeš uložené hrany a najdeš ty, co hledáš a označíš je jinou barvou (nebo flagem, hodnotou). Tuto barvu (flag) pak zohledníš při vykreslení.

sorry já jsem asi špatně formuloval můj problém. Potřebuji udělat aby dvě sousední hrany neměli stejnou barvu. takže potřebuji aby v koncovém stavu byli obarveny všechny hrany. formálněji je to asi toto: Hranová barevnost (chromatický index grafu) je nejmenší pocet barev potřebných k obarvení hran. U barvení hran požadujeme, aby každé dvě hrany, které mají spolecný vrchol, byly obarveny ruznými barvami.

To na tom nic nemění. Co se týká vykreslení, tak si pro každou hranu ulož barvu, kterou jí přiřadíš při obarvování a potom ji s ní i vykresli. To je ta jednodušší část. Algoritmus na obarvení grafu si asi budeš muset najít ...

algoritmus jsem našel (sice vrcholové obarvení v tom ale problém nevidím) horší je to předělat do programu

algoritmus jsem našel (sice vrcholové obarvení v tom ale problém nevidím) horší je to předělat do programu

Pokud máš slovní popis, jak dosáhnout cíle, tak ho sem dej a dáme to nějak dohromady ;-).

(Vrcholové barvení grafu - backtracking)
raf G je reprezentován seznam vrcholu a jejich sousedu s nižším
indexem. Výstupem tohoto algoritmu je pole Barva, pricemž Barvau
je barva (tj. císlo barvy), kterou je vrchol u obarven. Hodnota
promenné Omez, je urcena barevností grafu G (pocet použitých barev
v poli Barva).
1. Inicializace. Obarvíme první vrchol - položíme k := 1, Bk := 1,
Omez := n + 1
2. Pokus o obarvení dalšího vrcholu nejnižší možnou barvou.
Položíme k := k + 1.
Jestliže k > n, potom bod 3. Jinak Bk := {minimum ze všech
barev, které se nevyskytují u sousedu vrcholu k}.
Jestliže Bk > Omez, pak y := k a pokracujeme bodem 4. Jinak
opakujeme bod 2.
3. Pro 8u 2 V (G) priradíme Barvau := Bu; Omez := max{Bk; 8k};
y := první vrchol obarvený barvou Omez.
GA
4. Pokusíme se snížit barvu ve vrcholu y. Posledního souseda vrcholu
y s nižším indexem oznacíme k.
5. Pokusíme se zvýšit barvu ve vrcholu k. Jestliže k = 1, potom
bod 6. Jinak položíme b := min{ze všech barev c > Bk
nevyskytujících se v okolí uzlu k}. Jestliže b < Omez ^ b · k,
pak Bk := b a pokracujeme bodem 2. Jinak položíme k := k − 1
a pokracujeme bodem 5.
6. Konec.
GA

radši ti dám odkaz http://www.cs.vsb.cz/ochodkova/courses/gra/gal8.pdf

Popsané je to hezky :-). Pro začátek bude asi potřeba změnit datovou reprezentaci tak, aby se dalo zjistit, kdo na koho navazuje. V zadání je napsáno, že máš seznam vrcholů a každý si vede svůj seznam pokračovatelů. Graf asi není orientovaný, tak nezapomeň, pokračovat lze i opačným směrem. Až to budeš mít, tak je možné pokračovat.