marci@280: ETIK-OL-NOLIB-NEGRES graph concept-ek.
marci@280: 
marci@280:  Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok. 
marci@280: A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi 
marci@280: operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen 
marci@280: ujakra van szukseg. 
marci@280: 
marci@280:  Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat, 
marci@280: az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet 
marci@280: ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal 
marci@280: ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly, 
marci@280: a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere, 
marci@280: a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen 
marci@280: property_vector csak azokra a graf-objektumokra ervenyes, melyek 
marci@280: letrehozasanak pillanataban a grafhoz tartoznak. 
marci@280: 
marci@280: marci_bfs.hh	      //bfs, tejesen kiserleti
marci@280: marci_graph_demo.cc  //peldaprogi a lisas graf hasznalatahoz
marci@280: marci_list_graph.hh  //list_graph megvalositas
marci@280: marci_max_flow.hh     //folyam, kiserleti
marci@280: marci_property_vector.hh //property vector megvalosites indexelt grafokhoz	
marci@280: graf es iterator tipusok:
marci@280: 
marci@280: class list_graph;	 
marci@280: 
marci@280: class node_iterator;      
marci@280: trivialis node iterator, csak cimezni lehet vele, pl property vectort
marci@280: 
marci@280: class each_node_iterator;
marci@280: node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
marci@280: 
marci@280: class edge_iterator;
marci@280: trivialis edge iterator, csak cimezni lehet vele, pl property vectort
marci@280: 
marci@280: class each_edge_iterator;
marci@280: edge iterator a graf osszes elenek bejarasara
marci@280: 
marci@280: class out_edge_iterator;
marci@280: edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
marci@280: 
marci@280: class in_edge_iterator;
marci@280: edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
marci@280:       
marci@280: class sym_edge_iterator;
marci@280: edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
marci@280: konvertalhato 
marci@280: 
marci@280: default constructor:
marci@280: 
marci@280: list_graph();
marci@280:     
marci@280: A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
marci@280: Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve 
marci@280: ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az 
marci@280: iteratorok metodusait ne hasznaljuk. Miert? Azt  szeretnenk, ha 1 ponthalmazon 
marci@280: van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont 
marci@280: out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert 
marci@280: out_edge_iterator(const node_iterator&) hasznalata nem javasolt, 
marci@280: esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj. 
marci@280: 
marci@280: each_node_iterator first_node();
marci@280: each_edge_iterator first_edge();
marci@280: out_edge_iterator first_out_edge(const node_iterator&);
marci@280: in_edge_iterator first_in_edge(const node_iterator&);
marci@280: sym_edge_iterator first_sym_edge(const node_iterator&);
marci@280: 
marci@280: node_iterator tail(const edge_iterator&);
marci@280: node_iterator head(const edge_iterator&);
marci@280: 
marci@280: node_iterator a_node(const out_edge_iterator&);
marci@280: node_iterator a_node(const in_edge_iterator&);
marci@280: node_iterator a_node(const sym_edge_iterator&);
marci@280: //az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
marci@280: 
marci@280: node_iterator b_node(const out_edge_iterator&);
marci@280: node_iterator b_node(const in_edge_iterator&);
marci@280: node_iterator b_node(const sym_edge_iterator&);
marci@280: //az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
marci@280: 
marci@280: //node_iterator invalid_node();
marci@280: //edge_iterator invalid_edge();
marci@280: //out_edge_iterator invalid_out_edge();
marci@280: //in_edge_iterator invalid_in_edge();
marci@280: //sym_edge_iterator invalid_sym_edge();
marci@280: 
marci@280: //az iteratorok ures konstruktorai meghatarozatlan 
marci@280: tartalmu konstruktort adnak vissza, ezekkel a matodusokkal 
marci@280: lehet ervenytelent csinalni.
marci@280: Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
marci@280: 
marci@280: Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
marci@280: 
marci@280: void get_first(each_node_iterator&);
marci@280: void get_first(each_edge_iterator&);
marci@280: void get_first(out_edge_iterator&, const node_iterator&);
marci@280: void get_first(in_edge_iterator&, const node_iterator&);
marci@280: void get_first(sym_edge_iterator&, const node_iterator&);
marci@280: 
marci@280: void get_tail(node_iterator&, const edge_iterator&);
marci@280: void get_head(node_iterator&, const edge_iterator&);
marci@280: 
marci@280: void get_a_node(node_iterator&, const out_edge_iterator&);
marci@280: void get_a_node(node_iterator&, const in_edge_iterator&);
marci@280: void get_a_node(node_iterator&, const sym_edge_iterator&);
marci@280:    
marci@280: void get_b_node(node_iterator&, const out_edge_iterator&);
marci@280: void get_b_node(node_iterator&, const in_edge_iterator&);
marci@280: void get_b_node(node_iterator&, const sym_edge_iterator&);
marci@280:  
marci@280: //void get_invalid(node_iterator&);
marci@280: //void get_invalid(edge_iterator&);
marci@280: //void get_invalid(out_edge_iterator&);
marci@280: //void get_invalid(in_edge_iterator&);
marci@280: //void get_invalid(sym_edge_iterator&);
marci@280:  
marci@280: Pontok azonositasara de meginkabb property vectorokhoz:
marci@280: 
marci@280: int id(const node_iterator&);
marci@280: int id(const edge_iterator&);
marci@280: 
marci@280: Pontok es elek hozzaadasanak metodusai:
marci@280: 
marci@280: node_iterator add_node();
marci@280: edge_iterator add_edge(const node_iterator&, const node_iterator&);
marci@280: 
marci@280: Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
marci@280: ezek nem a list_graph metodusai
marci@280: 
marci@280: friend std::ostream& operator<<(std::ostream&, const node_iterator&);
marci@280: friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
marci@280: 
marci@280: node_iterator metodusai:
marci@280: node_iterator();
marci@280: bool valid();
marci@280: void make_invalid();
marci@280: ezek nem tagfuggvenyek:
marci@280: friend bool operator==(const node_iterator&, const node_iterator&);
marci@280: friend bool operator!=(const node_iterator& u, const node_iterator& v);
marci@280:     
marci@280: each_node_iterator metodusai:
marci@280: ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
marci@280: each_node_iterator();
marci@280: each_node_iterator& operator++();
marci@280: 
marci@280: edge_iterator metodusai:
marci@280: edge_iterator();
marci@280: bool valid();
marci@280: void make_invalid();
marci@280: ezek nem tagfvek:
marci@280: friend bool operator==(const edge_iterator&, const edge_iterator&);
marci@280: friend bool operator!=(const edge_iterator&, const edge_iterator&);
marci@280: ujra tagfv-ek.
marci@280: //node_iterator tail_node() const;		nem javasolt
marci@280: //node_iterator head_node() const;		nem javasolt
marci@280:    
marci@280: each_edge_iterator metodusai:
marci@280: edge_iterator-bol szarmazik
marci@280: each_edge_iterator();
marci@280: each_edge_iterator& operator++();
marci@280:  
marci@280: out_edge_iterator metodusai:
marci@280: edge_iterator-bol szarmazik
marci@280: out_edge_iterator();
marci@280: //out_edge_iterator(const node_iterator&);	nem javasolt
marci@280: out_edge_iterator& operator++();
marci@280: //node_iterator a_node() const;		nem javasolt
marci@280: //node_iterator b_node() const; 
marci@280:     
marci@280:  
marci@280: in_edge_iterator metodusai: 
marci@280: edge_iterator-bol szarmazik
marci@280: in_edge_iterator();
marci@280: //in_edge_iterator(const node_iterator&);	nem javasolt
marci@280: in_edge_iterator& operator++();
marci@280: //node_iterator a_node() const;		nem javasolt
marci@280: //node_iterator b_node() const; 
marci@280: 
marci@280: 
marci@280: sym_edge_iterator metodusai:
marci@280: edge_iterator-bol szarmazik
marci@280: sym_edge_iterator();
marci@280: //sym_edge_iterator(const node_iterator&);	nem javasolt
marci@280: sym_edge_iterator& operator++();
marci@280: //node_iterator a_node() const;		nem javasolt
marci@280: //node_iterator b_node() const; 
marci@280: 		
marci@280: Node propery array-okrol:
marci@280: 
marci@280: template <typename graph_type, typename T>
marci@280: class node_property_vector; 
marci@280: 
marci@280: metodusok:
marci@280: 
marci@280: node_property_vector(graph_type&);
marci@280: void put(graph_type::node_iterator, const T&);
marci@280: T get(graph_type::node_iterator);
marci@280: 
marci@280: Ugyanez edge_property_array-okkal
marci@280: 
marci@280: template <typename graph_type, typename T>
marci@280: class edge_property_vector;
marci@280: 
marci@280: edge_property_vector(graph_type&);
marci@280: void put(graph_type::edge_iterator, const T&);
marci@280: get(graph_type::edge_iterator);
marci@280: 
marci@280:  Ennyi nem javasolas utan, meg nehany szo.
marci@280:  Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen 
marci@280: csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban. 
marci@280: Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a 
marci@280: graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
marci@280: tobb grafot ugyanazon pont-iteratorokkal.
marci@280:  Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk 
marci@280: at a propertyket az algoritmusoknak, algoritmus-objektumoknak. 
marci@280: Errol majd kesobb.
marci@280: 
marci@280: marci@cs.elte.hu