ETIK-OL-NOLIB-NEGRES graph concept-ek.

 Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok. 

A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi 

operacio elegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen 

ujakra van szukseg. 

 Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat, 

az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet 

ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal 

ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly, 

a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere, 

a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen 

property_vector csak azokra a graf-objektumokra ervenyes, melyek 

letrehozasanak pillanataban a grafhoz tartoznak. 

marci_bfs.hh	      //bfs, tejesen kiserleti

marci_graph_demo.cc  //peldaprogi a lisas graf hasznalatahoz

marci_graph_traits.hh //alapertelmezett graph_traits

marci_list_graph.hh  //list_graph megvalositas

marci_max_flow.hh     //folyam, kiserleti

marci_property_vector.hh //property vector megvalosites indexelt grafokhoz	

graf es iterator tipusok:

class list_graph	 

class node_iterator      

trivialis node iterator, csak cimezni lehet vele, pl property vectort

class each_node_iterator

node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato

class edge_iterator

trivialis edge iterator, csak cimezni lehet vele, pl property vectort

class each_edge_iterator

edge iterator a graf osszes elenek bejarasara

class out_edge_iterator

edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato

class in_edge_iterator

edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato

class sym_edge_iterator

edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato

default constructor:

list_graph() 

A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:

Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve 

ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az 

iteratorok metodusait ne hasznaljuk. Miert? Azt  szeretnenk, ha 1 ponthalmazon 

van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont 

out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert 

out_edge_iterator(const node_iterator&) hasznalata nem javasolt, 

esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj. 

each_node_iterator first_node()

each_edge_iterator first_edge()

out_edge_iterator first_out_edge(const node_iterator&)

in_edge_iterator first_in_edge(const node_iterator&)

sym_edge_iterator first_sym_edge(const node_iterator&)

node_iterator tail(const edge_iterator&)

node_iterator head(const edge_iterator&)

node_iterator a_node(const out_edge_iterator&)

node_iterator a_node(const in_edge_iterator&)

node_iterator a_node(const sym_edge_iterator&)

//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t

node_iterator b_node(const out_edge_iterator&)

node_iterator b_node(const in_edge_iterator&)

node_iterator b_node(const sym_edge_iterator&)

//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t

node_iterator invalid_node()

edge_iterator invalid_edge()

out_edge_iterator invalid_out_edge()

in_edge_iterator invalid_in_edge()

sym_edge_iterator invalid_sym_edge()

//az iteratorok ures konstruktorai meghatarozatlan 

tartalmu konstruktort adnak vissza, ezekkel a matodusokkal 

lehet ervenytelent csinalni.

Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.

Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:

void get_first(each_node_iterator&)

void get_first(each_edge_iterator&)

void get_first(out_edge_iterator&, const node_iterator&)

void get_first(in_edge_iterator&, const node_iterator&)

void get_first(sym_edge_iterator&, const node_iterator&)

void get_tail(node_iterator&, const edge_iterator&)

void get_head(node_iterator&, const edge_iterator&)

void get_a_node(node_iterator&, const out_edge_iterator&)

void get_a_node(node_iterator&, const in_edge_iterator&)

void get_a_node(node_iterator&, const sym_edge_iterator&)

void get_b_node(node_iterator&, const out_edge_iterator&)

void get_b_node(node_iterator&, const in_edge_iterator&)

void get_b_node(node_iterator&, const sym_edge_iterator&)

void get_invalid(node_iterator&)

void get_invalid(edge_iterator&)

void get_invalid(out_edge_iterator&)

void get_invalid(in_edge_iterator&)

void get_invalid(sym_edge_iterator&)

Pontok azonositasara de meginkabb property vectorokhoz:

int id(const node_iterator&)

int id(const edge_iterator&)

Pontok es elek hozzaadasanak metodusai:

node_iterator add_node()

edge_iterator add_edge(const node_iterator&, const node_iterator&)

Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:

ezek nem a list_graph metodusai

friend std::ostream& operator<<(std::ostream&, const node_iterator&)

friend std::ostream& operator<<(std::ostream&, const edge_iterator&)

node_iterator metodusai:

node_iterator()

bool is_valid()

ezek nem tagfuggvenyek:

friend bool operator==(const node_iterator&, const node_iterator&)

friend bool operator!=(const node_iterator& u, const node_iterator& v)

each_node_iterator metodusai:

ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.

each_node_iterator()

each_node_iterator& operator++()

edge_iterator metodusai:

edge_iterator()

bool is_valid()

ezek nem tagfvek:

friend bool operator==(const edge_iterator&, const edge_iterator&)

friend bool operator!=(const edge_iterator&, const edge_iterator&)

ujra tagfv-ek.

//node_iterator tail_node() const		nem javasolt

//node_iterator head_node() const		nem javasolt

each_edge_iterator metodusai:

edge_iterator-bol szarmazik

each_edge_iterator()

each_edge_iterator& operator++()

out_edge_iterator metodusai:

edge_iterator-bol szarmazik

out_edge_iterator()

//out_edge_iterator(const node_iterator&)	nem javasolt

out_edge_iterator& operator++()

//node_iterator a_node() const		nem javasolt

//node_iterator b_node() const 

in_edge_iterator metodusai: 

edge_iterator-bol szarmazik

in_edge_iterator()

//in_edge_iterator(const node_iterator&)	nem javasolt

in_edge_iterator& operator++()

//node_iterator a_node() const		nem javasolt

//node_iterator b_node() const 

sym_edge_iterator metodusai:

edge_iterator-bol szarmazik

sym_edge_iterator()

//sym_edge_iterator(const node_iterator&)	nem javasolt

sym_edge_iterator& operator++()

//node_iterator a_node() const		nem javasolt

//node_iterator b_node() const 

Node propery array-okrol:

template <typename graph_type, typename T>

class node_property_vector 

metodusok:

node_property_vector(graph_type&)

node_property_vector(graph_type&, T a)

fill constructor, a-val kitolt

void put(graph_traits<graph_type>::node_iterator, const T&)

T get(graph_traits<graph_type>::node_iterator)

Ugyanez edge_property_array-okkal

template <typename graph_type, typename T>

class edge_property_vector

edge_property_vector(graph_type&)

edge_property_vector(graph_type&, T a)

fill constructor, a-val kitolt

void put(graph_traits<graph_type>::edge_iterator, const T&)

get(graph_traits<graph_type>::edge_iterator)

 Ennyi nem javasolas utan, meg nehany szo.

 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen 

csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban. 

Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a 

graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon

tobb grafot ugyanazon pont-iteratorokkal.

 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk 

at a propertyket az algoritmusoknak, algoritmus-objektumoknak. 

Errol majd kesobb.

marci@cs.elte.hu