source: lemon-0.x/src/work/marci_graph_concept.txt @ 21:181b37336b29

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_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 valid();
void make_invalid();
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 valid();
void make_invalid();
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&);
void put(graph_type::node_iterator, const T&);
T get(graph_type::node_iterator);

Ugyanez edge_property_array-okkal

template <typename graph_type, typename T>
class edge_property_vector;

edge_property_vector(graph_type&);
void put(graph_type::edge_iterator, const T&);
get(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