ETIK-OL-NOLIB-NEGRES graph concept-ek. Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok. A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi operacio elvegzesere 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-ra 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-ra konvertalhato class in_edge_iterator; edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato class sym_edge_iterator; edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra 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 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 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