1.1 --- a/src/work/marci/oldies/marci_graph_concept.txt Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,217 +0,0 @@
1.4 -ETIK-OL-NOLIB-NEGRES graph concept-ek.
1.5 -
1.6 - Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
1.7 -A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
1.8 -operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
1.9 -ujakra van szukseg.
1.10 -
1.11 - Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
1.12 -az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet
1.13 -ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal
1.14 -ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly,
1.15 -a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere,
1.16 -a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen
1.17 -property_vector csak azokra a graf-objektumokra ervenyes, melyek
1.18 -letrehozasanak pillanataban a grafhoz tartoznak.
1.19 -
1.20 -marci_bfs.hh //bfs, tejesen kiserleti
1.21 -marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz
1.22 -marci_list_graph.hh //list_graph megvalositas
1.23 -marci_max_flow.hh //folyam, kiserleti
1.24 -marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
1.25 -graf es iterator tipusok:
1.26 -
1.27 -class list_graph;
1.28 -
1.29 -class node_iterator;
1.30 -trivialis node iterator, csak cimezni lehet vele, pl property vectort
1.31 -
1.32 -class each_node_iterator;
1.33 -node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
1.34 -
1.35 -class edge_iterator;
1.36 -trivialis edge iterator, csak cimezni lehet vele, pl property vectort
1.37 -
1.38 -class each_edge_iterator;
1.39 -edge iterator a graf osszes elenek bejarasara
1.40 -
1.41 -class out_edge_iterator;
1.42 -edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
1.43 -
1.44 -class in_edge_iterator;
1.45 -edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
1.46 -
1.47 -class sym_edge_iterator;
1.48 -edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
1.49 -konvertalhato
1.50 -
1.51 -default constructor:
1.52 -
1.53 -list_graph();
1.54 -
1.55 -A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
1.56 -Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
1.57 -ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
1.58 -iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
1.59 -van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
1.60 -out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
1.61 -out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
1.62 -esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
1.63 -
1.64 -each_node_iterator first_node();
1.65 -each_edge_iterator first_edge();
1.66 -out_edge_iterator first_out_edge(const node_iterator&);
1.67 -in_edge_iterator first_in_edge(const node_iterator&);
1.68 -sym_edge_iterator first_sym_edge(const node_iterator&);
1.69 -
1.70 -node_iterator tail(const edge_iterator&);
1.71 -node_iterator head(const edge_iterator&);
1.72 -
1.73 -node_iterator a_node(const out_edge_iterator&);
1.74 -node_iterator a_node(const in_edge_iterator&);
1.75 -node_iterator a_node(const sym_edge_iterator&);
1.76 -//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
1.77 -
1.78 -node_iterator b_node(const out_edge_iterator&);
1.79 -node_iterator b_node(const in_edge_iterator&);
1.80 -node_iterator b_node(const sym_edge_iterator&);
1.81 -//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
1.82 -
1.83 -//node_iterator invalid_node();
1.84 -//edge_iterator invalid_edge();
1.85 -//out_edge_iterator invalid_out_edge();
1.86 -//in_edge_iterator invalid_in_edge();
1.87 -//sym_edge_iterator invalid_sym_edge();
1.88 -
1.89 -//az iteratorok ures konstruktorai meghatarozatlan
1.90 -tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
1.91 -lehet ervenytelent csinalni.
1.92 -Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
1.93 -
1.94 -Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
1.95 -
1.96 -void get_first(each_node_iterator&);
1.97 -void get_first(each_edge_iterator&);
1.98 -void get_first(out_edge_iterator&, const node_iterator&);
1.99 -void get_first(in_edge_iterator&, const node_iterator&);
1.100 -void get_first(sym_edge_iterator&, const node_iterator&);
1.101 -
1.102 -void get_tail(node_iterator&, const edge_iterator&);
1.103 -void get_head(node_iterator&, const edge_iterator&);
1.104 -
1.105 -void get_a_node(node_iterator&, const out_edge_iterator&);
1.106 -void get_a_node(node_iterator&, const in_edge_iterator&);
1.107 -void get_a_node(node_iterator&, const sym_edge_iterator&);
1.108 -
1.109 -void get_b_node(node_iterator&, const out_edge_iterator&);
1.110 -void get_b_node(node_iterator&, const in_edge_iterator&);
1.111 -void get_b_node(node_iterator&, const sym_edge_iterator&);
1.112 -
1.113 -//void get_invalid(node_iterator&);
1.114 -//void get_invalid(edge_iterator&);
1.115 -//void get_invalid(out_edge_iterator&);
1.116 -//void get_invalid(in_edge_iterator&);
1.117 -//void get_invalid(sym_edge_iterator&);
1.118 -
1.119 -Pontok azonositasara de meginkabb property vectorokhoz:
1.120 -
1.121 -int id(const node_iterator&);
1.122 -int id(const edge_iterator&);
1.123 -
1.124 -Pontok es elek hozzaadasanak metodusai:
1.125 -
1.126 -node_iterator add_node();
1.127 -edge_iterator add_edge(const node_iterator&, const node_iterator&);
1.128 -
1.129 -Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
1.130 -ezek nem a list_graph metodusai
1.131 -
1.132 -friend std::ostream& operator<<(std::ostream&, const node_iterator&);
1.133 -friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
1.134 -
1.135 -node_iterator metodusai:
1.136 -node_iterator();
1.137 -bool valid();
1.138 -void make_invalid();
1.139 -ezek nem tagfuggvenyek:
1.140 -friend bool operator==(const node_iterator&, const node_iterator&);
1.141 -friend bool operator!=(const node_iterator& u, const node_iterator& v);
1.142 -
1.143 -each_node_iterator metodusai:
1.144 -ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
1.145 -each_node_iterator();
1.146 -each_node_iterator& operator++();
1.147 -
1.148 -edge_iterator metodusai:
1.149 -edge_iterator();
1.150 -bool valid();
1.151 -void make_invalid();
1.152 -ezek nem tagfvek:
1.153 -friend bool operator==(const edge_iterator&, const edge_iterator&);
1.154 -friend bool operator!=(const edge_iterator&, const edge_iterator&);
1.155 -ujra tagfv-ek.
1.156 -//node_iterator tail_node() const; nem javasolt
1.157 -//node_iterator head_node() const; nem javasolt
1.158 -
1.159 -each_edge_iterator metodusai:
1.160 -edge_iterator-bol szarmazik
1.161 -each_edge_iterator();
1.162 -each_edge_iterator& operator++();
1.163 -
1.164 -out_edge_iterator metodusai:
1.165 -edge_iterator-bol szarmazik
1.166 -out_edge_iterator();
1.167 -//out_edge_iterator(const node_iterator&); nem javasolt
1.168 -out_edge_iterator& operator++();
1.169 -//node_iterator a_node() const; nem javasolt
1.170 -//node_iterator b_node() const;
1.171 -
1.172 -
1.173 -in_edge_iterator metodusai:
1.174 -edge_iterator-bol szarmazik
1.175 -in_edge_iterator();
1.176 -//in_edge_iterator(const node_iterator&); nem javasolt
1.177 -in_edge_iterator& operator++();
1.178 -//node_iterator a_node() const; nem javasolt
1.179 -//node_iterator b_node() const;
1.180 -
1.181 -
1.182 -sym_edge_iterator metodusai:
1.183 -edge_iterator-bol szarmazik
1.184 -sym_edge_iterator();
1.185 -//sym_edge_iterator(const node_iterator&); nem javasolt
1.186 -sym_edge_iterator& operator++();
1.187 -//node_iterator a_node() const; nem javasolt
1.188 -//node_iterator b_node() const;
1.189 -
1.190 -Node propery array-okrol:
1.191 -
1.192 -template <typename graph_type, typename T>
1.193 -class node_property_vector;
1.194 -
1.195 -metodusok:
1.196 -
1.197 -node_property_vector(graph_type&);
1.198 -void put(graph_type::node_iterator, const T&);
1.199 -T get(graph_type::node_iterator);
1.200 -
1.201 -Ugyanez edge_property_array-okkal
1.202 -
1.203 -template <typename graph_type, typename T>
1.204 -class edge_property_vector;
1.205 -
1.206 -edge_property_vector(graph_type&);
1.207 -void put(graph_type::edge_iterator, const T&);
1.208 -get(graph_type::edge_iterator);
1.209 -
1.210 - Ennyi nem javasolas utan, meg nehany szo.
1.211 - Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
1.212 -csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
1.213 -Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
1.214 -graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
1.215 -tobb grafot ugyanazon pont-iteratorokkal.
1.216 - Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
1.217 -at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
1.218 -Errol majd kesobb.
1.219 -
1.220 -marci@cs.elte.hu