source: lemon-0.x/src/work/marci_graph_concept.txt @ 13:d33813af6e50

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