Hranové obarvení grafu – Delphi – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
zajda
~ Anonymní uživatel
10 příspěvků
16. 4. 2010   #1
-
0
-

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

Nahlásit jako SPAM
IP: 90.181.88.–
Reklama
Reklama
liborb
~ Redaktor
+18
Guru
16. 4. 2010   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 85.207.166.–
zajda
~ Anonymní uživatel
10 příspěvků
16. 4. 2010   #3
-
0
-

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

Nahlásit jako SPAM
IP: 90.181.88.–
liborb
~ Redaktor
+18
Guru
16. 4. 2010   #4
-
0
-

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

Nahlásit jako SPAM
IP: 85.207.166.–
zajda
~ Anonymní uživatel
10 příspěvků
16. 4. 2010   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 90.181.88.–
liborb
~ Redaktor
+18
Guru
16. 4. 2010   #6
-
0
-

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

Nahlásit jako SPAM
IP: 91.203.96.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
16. 4. 2010   #7
-
0
-

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

Nahlásit jako SPAM
IP: 90.181.88.–
zajda
~ Anonymní uživatel
10 příspěvků
16. 4. 2010   #8
-
0
-

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

Nahlásit jako SPAM
IP: 90.181.88.–
liborb
~ Redaktor
+18
Guru
17. 4. 2010   #9
-
0
-

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

Nahlásit jako SPAM
IP: 91.203.96.–
zajda
~ Anonymní uživatel
10 příspěvků
17. 4. 2010   #10
-
0
-

(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

Nahlásit jako SPAM
IP: 90.181.88.–
zajda
~ Anonymní uživatel
10 příspěvků
17. 4. 2010   #11
-
0
-

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

Nahlásit jako SPAM
IP: 90.181.88.–
liborb
~ Redaktor
+18
Guru
18. 4. 2010   #12
-
0
-

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.

Nahlásit jako SPAM
IP: 91.203.96.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 21 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý