SDJ.Software.Developer-'s.Journal.2011.07.PL.(P2PNet.pl).pdf

REDAKCJA

7/2011 (199)

BIBLIOTEKA MIESIĄCA

PRoGRAmowANIE TCL

Grafy i algorytmy grafowe.

Biblioteka boost::graph

Robert Nowak, Andrzej Michałowski

Grafy są strukturą danych, która pozwala opisać zło-

żone zależności z otaczającego nas świata. W artykule

omawiamy bibliotekę do reprezentacji grafów, wchodzą-

cą w skład kolekcji boost.

Tcl: wirtualne systemy plików.

Część II: Skrypty Tcl jako aplikacje

wykonywalne

Piotr Bełtowski, Wojciech Kocjan

Tcl/Tk to dosyć interesujący język. Od 20 lat Tk po-

zwala na tworzenie budowanie interfejsów graficznych

działających na różnych systemach operacyjnych – wy-

korzystywane między innymi przez języki Perl oraz Py-

thon. Od 11 lat Tcl pozwala na pakowanie całej aplika-

cji do pojedynczego pliku wykonywalnego – co prak-

tycznie eliminuje problemy z dystrybucją aplikacji oraz

ich uaktualnianiem. W dzisiejszym artykule przybliżymy

ten proces.

KLUB TECHNICZNY

Po drugiej stronie ekranu.

Czyli od kampera do game

developera.

Adrian Zając

Niewiele osób zdaje sobie sprawę, że praca przy tworze-

niu gier komputerowych stała się w ostatnich latach jak

najbardziej realnym źródłem dochodów w naszym kra-

ju. Młodzieńcze pasje mogą nie tylko znaleźć swe ujście

w nowo otwartych kierunkach studiów, lecz otworzyć

przed nami drogę do jednego z najbardziej dochodowe-

go segmentu rynku.

Tcl: wirtualne systemy plików.

Część III: System budujący TABS

Piotr Bełtowski, Wojciech Kocjan

Programiści Javy od lat z powodzeniem korzystają ze

sprawdzonego i popularnego rozwiązania, jakim jest

środowisko budujące Ant. Przyjęta filozofia definiowania

projektów jest na tyle wygodna i elastyczna, że docze-

kała się analogicznych narzędzi dla innych języków. Rów-

nież Tcl może poszczycić się systemem TABS, który opi-

szemy w niniejszym artykule.

PRoGRAmowANIE JAvA

Analiza wydajności aplikacji Java

dla opornych. Jak diagnozować

i rozwiązywać problemy z Garbage

Collectorem w Javie?

Daniel Witkowski, Paweł Wojtanka

Miesięcznik Software Developer’s Journal (12 numerów w roku)

jest wydawany przez

Software Press Sp. z o.o. SK

ul. Bokserska 1, 02-682 Warszawa, Polska

tel. +48 22 427 36 91, fax +48 22 224 24 59

Prezes: Paweł Marciniak

www.sdjournal.org

cooperation@software.com.pl

Dyrektor wydawniczy: Natalia Sieniutowicz

Dział reklamy: adv@software.com.pl

Redakcja dokłada wszelkich starań, by publikowane w piśmie

i na towarzyszących mu nośnikach informacje i programy były

poprawne, jednakże nie bierze odpowiedzialności za efekty

wykorzystania ich; nie gwarantuje także poprawnego działania

programów shareware, freeware i public domain.

Wszystkie znaki firmowe zawarte w piśmie są własności

odpowiednich firm.

Zostały użyte wyłącznie w celach informacyjnych.

Redaktor naczelny: Łukasz Łopuszański

lukasz.lopuszanski@software.com.pl

Skład i łamanie: Tomasz Kostro

www.studiopoligraficzne.com

Kierownik produkcji: Andrzej Kuca

andrzej.kuca@software.com.pl

Adres korespondencyjny:

Software Press Sp. z o.o. SK,

Osoby zainteresowane wspópracą prosimy o kontakt:

cooperation@software.com.pl

7/2011

Spis treści

E-CommERCE

su, że się nie opłaca. Wszystkie te osoby mają coś wspól-

nego, w praktyce prawie nikt tego nie robi. Głównie dla-

tego, że to kosztuje. Czy na pewno?

Wiem czego chcesz. Systemy

rekomendacji produktów

Piotr Płoński

Współcześnie trudno jest znaleźć w sieci, film, książ-

kę, piosenkę – produkt, który będzie się nam podobał.

W artykule opiszę dwa algorytmy stosowane najczęściej

w serwisach internetowych, takich jak np. Amazon.com

lub YouTube.com, do polecania produktów. Systemy re-

komendacji pozwalają użytkownikowi znaleźć szybciej

interesujący go produkt, a właścicielom serwisów osią-

gać większe zyski.

Skuteczne wdrażanie w projekt

Michał Kapłon

Wszyscy wiedzą, jak to jest z nowymi projekta-

mi. Niezależnie od tego czy są ciekawe czy nudne, łatwe

czy wymagające, skomplikowane technologicznie czy da-

jące się realizować za pomocą kartki papieru i ołówka,

jedną przynajmniej cechę mają wspólną. Dla ludzi, któ-

rzy dołączają do zespołu są nowe. Nowi programiści, za-

nim w pełni rozwiną swe „koderskie” skrzydła, muszą

nauczyć się wielu reguł, faktów, zależności – słowem, niu-

ansów nowej domeny. Rolą mentorów jest umożliwie-

nie im tego w jak najmniej bolesny sposób. Rolą ich sa-

mych jest świadome uczenie się rzeczy istotnych, najbar-

dziej potrzebnych.

INŻYNIERIA OPROGRAMOWANIA

Naturalny porządek refaktoryzacji

Michal Bartyzel, Mariusz Sieraczkiewicz

Są tacy, którzy wiedzą, że trzeba refaktoryzować.

Są tacy, którzy nie wiedzą, że trzeba refaktoryzować.

Są tacy, którzy uważają, że refaktoryzowanie nie ma sen-

Reklama

www.sdjournal.org

BIBLIOTEKA MIESIĄCA

Grafy i algorytmy grafowe

Biblioteka boost::graph library

Grafy są strukturą danych, która pozwala opisać złożone zależności

z otaczającego nas świata. W artykule omawiamy bibliotekę

do reprezentacji grafów, wchodzącą w skład kolekcji boost.

Dowiesz się:

• Jak reprezentować grafy w C++;

• Co oferuje biblioteka boost::graph;

• Jak używać algorytmów grafowych oferowanych przez

tę bibliotekę.

Powinieneś wiedzieć:

• Jak pisać proste programy w C++;

• Co to jest graf.

Biblioteka boost::graph

Grafy, czyli zbiory wierzchołków powiązane krawędzia-

mi (patrz ramka), są bardzo często wykorzystywane do

przetwarzania informacji. Są one bardzo ogólną struk-

turą danych, inne powszechnie używane struktury da-

nych (drzewa, listy) są pewnymi szczególnymi przypad-

kami grafów.

Biblioteka BGL (ang. Boost Graph Library ), wchodząca

w skład bibliotek boost, zawiera szablony reprezentu-

jące grafy oraz zbiór kilkudziesięciu algorytmów grafo-

wych. Grafy są dostarczane w postaci generycznej, dzię-

ki czemu z wierzchołkiem, krawędzią lub całym grafem

można związać obiekt lub obiekty dowolnego typu. Na

rysunku 1 pokazano schematycznie graf przechowywany

w takiej postaci, gdzie z wierzchołkiem są związane kra-

wędzie z niego wychodzące.

Szablony z biblioteki boost::graph wykorzystują kolek-

cje ze standardowej biblioteki szablonów (patrz ramka).

Graf reprezentowany listą sąsiedztwa generuje się uży-

wając szablonu adjacency_list , tak jak pokazano na Li-

stingu 1. Trzy pierwsze parametry są nazwami typów,

które definiują kolekcje wykorzystane do przechowy-

wania krawędzi i wierzchołków oraz rodzaju grafu, na-

tomiast trzy kolejne są typami związanymi z wierzchoł-

kiem, krawędzią i grafem. Znaczenie tych parametrów,

oraz typowe wartości podano na Listingu 1. Biblioteka

wykorzystuje typ struct no_property {} , który oznacza,

że nie przechowujemy obiektów związanych z wierz-

chołkiem, krawędzią lub grafem.

Graf może być reprezentowany także przez macierz

sąsiedztwa (szablon adjacency_matrix ) albo w postaci

skompresowanej (szablon compressed_sparse_row_graph ),

te sposoby nie są wykorzystywane w tym artykule.

W najprostszym przypadku, gdy krawędzie są przecho-

wywane w wektorze, identyfikatorem wierzchołka jest

Szybki start

Aby uruchomić przedstawione przykłady, nale-

ży mieć dostęp do kompilatora C++ oraz edyto-

ra tekstu. Przykłady wykorzystują biblioteki boost

( www.boost.org ). Aby poprawnie je skompilować

należy dodać odpowiednie zależności wykorzysty-

wane podczas konsolidacji; dla konsolidatora g++

należy dodać opcje: -lboost _ graph ; dla konsoli-

datora Visual Studio (program link) biblioteki bo-

ost są dodawane automatycznie. Na wydrukach

pominięto dołączanie odpowiednich nagłówków

oraz udostępnianie przestrzeni nazw, pełne źródła

umieszczono jako materiały pomocnicze.

Rysunek 1. Przykładowy graf

7/2011

Grafy i algorytmy grafowe

liczba całkowita (indeks). W takim przypadku graf można

utworzyć dostarczając liczbę wierzchołków oraz tablicę

krawędzi, gdzie krawędź to para liczb: indeks wierzchoł-

ka z którego krawędź wychodzi oraz indeks wierzchołka

do którego krawędź wchodzi. Przykład konstrukcji grafu

zawiera Listing 2. Reprezentacja wewnętrzna jest sche-

matycznie przedstawiona na Rysunku 2.

Dodawanie, usuwanie wierzchołków oraz krawędzi

jest możliwe dla grafów utworzonych za pomocą sza-

blonu adjacency_list . Wymienione modyfikacje grafu

wykonuje się za pomocą funkcji add_vertex , add_edge ,

remove_vertex oraz remove_edge . Szczególną uwagę nale-

ży zwrócić na usuwanie wierzchołków ( remove_vertex ),

powinno się najpierw usunąć wszystkie krawędzie wcho-

dzące i wychodzące z usuwanego wierzchołka. Bibliote-

ka zawiera funkcję clear_vertex , która upraszcza to za-

danie.

Do grafu, pokazanego na Rysunku 1 dodawany jest no-

wy wierzchołek. Następnie tworzona jest krawędź po-

między wierzchołkiem A, a tym dodanym; później usu-

wane są wszystkie krawędzie związane z wierzchołkiem

D (wchodzące i wychodzące). Na koniec usuwany jest

Grafy

Grafy to zbiory wierzchołków powiązane krawę-

dziami. Każda krawędź zaczyna się i kończy w jed-

nym z wierzchołków. Grafy dzielimy na skierowa-

ne (krawędzie mają określony kierunek) oraz nie-

skierowane. Przykład grafu pokazano na Rysunku

1. Specjalnym rodzajem grafów są drzewa, którymi

nazywamy grafy nie zawierające dróg zamknię-

tych (czyli cykli).

Grafy są bardzo często wykorzystywane do opi-

sywania różnych zależności z otaczającego nas

świata; przykładem jest opis sieci połączeń pomię-

dzy miastami, wtedy wierzchołki mogą opisywać

miasta, zaś krawędzie – drogi.

Standardowa biblioteka szablonów

Zbiór kontenerów jednowymiarowych (tablice, listy,

słowniki), algorytmów i iteratorów, wchodzi w skład

biblioteki standardowej języka C++. Jest bardzo

wydajna i uniwersalna (wykorzystuje szablony).

Więcej informacji http://www.sgi.com/tech/stl/ .

Listing 1. Szablon tworzący graf

adjacency_list < VertexList , //kolekcja przechowująca wierzchołki, znaczenie jest następujące:

// vecS - std::vector

// listS - std::list

// setS - std::set

// multisetS - std::multiset

OutEdgeList ,// kolekcja przechowująca krawędzie - parametr ma wartości takie jak

VertexList

Directed , // rodzaj grafu, znaczenie:

// directedS - graf skierowany

// undirectedS - graf nieskierowany

VertexProperties , // typ obiektu związanego z wierzchołkiem, domyślnie no_property

EdgeProperties , // typ obiektu związanego z krawdzią, domyślnie no_property

GraphProperties > // typ obiektu zwizanego z caym grafem , domy ś lnie no_property

Listing 2 . Tworzenie i modyikacja grafu

typedef adjacency_list < vecS , vecS , directedS > Graph ; //typ grafu

enum { A , B , C , D , E , N } ; //identyikatory wierzchołków, N – liczba wierzchołków

typedef std :: pair < int , int > Edge ; //para liczb - reprezentuje krawędź

const Edge EDGE_ARRAY [] = { Edge ( A , B ) , Edge ( A , E ) ,

Edge ( B , A ) , Edge ( B , C ) , Edge ( B , D ) ,

Edge ( D , E ) , Edge ( E , B ) } ;

const int NUM_EDGES = sizeof ( EDGE_ARRAY ) / sizeof ( EDGE_ARRAY [ 0 ]);

Graph g ( EDGE_ARRAY , EDGE_ARRAY + NUM_EDGES , N );

Graph :: vertex_descriptor v = add_vertex ( g ); //dodaje nowy wierzchołek

add_edge ( A , v , g ); //dodaje nową krawędź

clear_vertex ( D , g ); //usuwa krawędzie związane z wierzchołkiem D

remove_vertex ( D , g ); // usuwa wierzcho ł ek

www.sdjournal.org

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: