diff -r be43902fadb7 -r 19f3943521ab src/work/marci_graph_concept.txt --- a/src/work/marci_graph_concept.txt Sat Apr 03 14:22:33 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,217 +0,0 @@ -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