1 ETIK-OL-NOLIB-NEGRES graph concept-ek.
3 Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
4 A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
5 operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
8 Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
9 az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet
10 ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal
11 ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly,
12 a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere,
13 a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen
14 property_vector csak azokra a graf-objektumokra ervenyes, melyek
15 letrehozasanak pillanataban a grafhoz tartoznak.
17 marci_bfs.hh //bfs, tejesen kiserleti
18 marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz
19 marci_list_graph.hh //list_graph megvalositas
20 marci_max_flow.hh //folyam, kiserleti
21 marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
22 graf es iterator tipusok:
27 trivialis node iterator, csak cimezni lehet vele, pl property vectort
29 <<<<<<< marci_graph_concept.txt
30 class each_node_iterator
31 node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
33 class each_node_iterator;
34 node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
38 trivialis edge iterator, csak cimezni lehet vele, pl property vectort
40 class each_edge_iterator;
41 edge iterator a graf osszes elenek bejarasara
43 <<<<<<< marci_graph_concept.txt
44 class out_edge_iterator
45 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
47 class out_edge_iterator;
48 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
51 <<<<<<< marci_graph_concept.txt
52 class in_edge_iterator
53 edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
55 class in_edge_iterator;
56 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
59 <<<<<<< marci_graph_concept.txt
60 class sym_edge_iterator
61 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
64 class sym_edge_iterator;
65 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
72 A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
73 Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
74 ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
75 iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
76 van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
77 out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
78 out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
79 esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
81 each_node_iterator first_node();
82 each_edge_iterator first_edge();
83 out_edge_iterator first_out_edge(const node_iterator&);
84 in_edge_iterator first_in_edge(const node_iterator&);
85 sym_edge_iterator first_sym_edge(const node_iterator&);
87 node_iterator tail(const edge_iterator&);
88 node_iterator head(const edge_iterator&);
90 node_iterator a_node(const out_edge_iterator&);
91 node_iterator a_node(const in_edge_iterator&);
92 node_iterator a_node(const sym_edge_iterator&);
93 //az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
95 node_iterator b_node(const out_edge_iterator&);
96 node_iterator b_node(const in_edge_iterator&);
97 node_iterator b_node(const sym_edge_iterator&);
98 //az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
100 //node_iterator invalid_node();
101 //edge_iterator invalid_edge();
102 //out_edge_iterator invalid_out_edge();
103 //in_edge_iterator invalid_in_edge();
104 //sym_edge_iterator invalid_sym_edge();
106 //az iteratorok ures konstruktorai meghatarozatlan
107 tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
108 lehet ervenytelent csinalni.
109 Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
111 Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
113 void get_first(each_node_iterator&);
114 void get_first(each_edge_iterator&);
115 void get_first(out_edge_iterator&, const node_iterator&);
116 void get_first(in_edge_iterator&, const node_iterator&);
117 void get_first(sym_edge_iterator&, const node_iterator&);
119 void get_tail(node_iterator&, const edge_iterator&);
120 void get_head(node_iterator&, const edge_iterator&);
122 void get_a_node(node_iterator&, const out_edge_iterator&);
123 void get_a_node(node_iterator&, const in_edge_iterator&);
124 void get_a_node(node_iterator&, const sym_edge_iterator&);
126 void get_b_node(node_iterator&, const out_edge_iterator&);
127 void get_b_node(node_iterator&, const in_edge_iterator&);
128 void get_b_node(node_iterator&, const sym_edge_iterator&);
130 //void get_invalid(node_iterator&);
131 //void get_invalid(edge_iterator&);
132 //void get_invalid(out_edge_iterator&);
133 //void get_invalid(in_edge_iterator&);
134 //void get_invalid(sym_edge_iterator&);
136 Pontok azonositasara de meginkabb property vectorokhoz:
138 int id(const node_iterator&);
139 int id(const edge_iterator&);
141 Pontok es elek hozzaadasanak metodusai:
143 node_iterator add_node();
144 edge_iterator add_edge(const node_iterator&, const node_iterator&);
146 Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
147 ezek nem a list_graph metodusai
149 friend std::ostream& operator<<(std::ostream&, const node_iterator&);
150 friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
152 node_iterator metodusai:
156 ezek nem tagfuggvenyek:
157 friend bool operator==(const node_iterator&, const node_iterator&);
158 friend bool operator!=(const node_iterator& u, const node_iterator& v);
160 each_node_iterator metodusai:
161 ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
162 each_node_iterator();
163 each_node_iterator& operator++();
165 edge_iterator metodusai:
170 friend bool operator==(const edge_iterator&, const edge_iterator&);
171 friend bool operator!=(const edge_iterator&, const edge_iterator&);
173 //node_iterator tail_node() const; nem javasolt
174 //node_iterator head_node() const; nem javasolt
176 each_edge_iterator metodusai:
177 edge_iterator-bol szarmazik
178 each_edge_iterator();
179 each_edge_iterator& operator++();
181 out_edge_iterator metodusai:
182 edge_iterator-bol szarmazik
184 //out_edge_iterator(const node_iterator&); nem javasolt
185 out_edge_iterator& operator++();
186 //node_iterator a_node() const; nem javasolt
187 //node_iterator b_node() const;
190 in_edge_iterator metodusai:
191 edge_iterator-bol szarmazik
193 //in_edge_iterator(const node_iterator&); nem javasolt
194 in_edge_iterator& operator++();
195 //node_iterator a_node() const; nem javasolt
196 //node_iterator b_node() const;
199 sym_edge_iterator metodusai:
200 edge_iterator-bol szarmazik
202 //sym_edge_iterator(const node_iterator&); nem javasolt
203 sym_edge_iterator& operator++();
204 //node_iterator a_node() const; nem javasolt
205 //node_iterator b_node() const;
207 Node propery array-okrol:
209 template <typename graph_type, typename T>
210 class node_property_vector;
214 node_property_vector(graph_type&);
215 void put(graph_type::node_iterator, const T&);
216 T get(graph_type::node_iterator);
218 Ugyanez edge_property_array-okkal
220 template <typename graph_type, typename T>
221 class edge_property_vector;
223 edge_property_vector(graph_type&);
224 void put(graph_type::edge_iterator, const T&);
225 get(graph_type::edge_iterator);
227 Ennyi nem javasolas utan, meg nehany szo.
228 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
229 csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
230 Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
231 graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
232 tobb grafot ugyanazon pont-iteratorokkal.
233 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
234 at a propertyket az algoritmusoknak, algoritmus-objektumoknak.