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