1 | ETIK-OL-NOLIB-NEGRES graph concept-ek. |
---|
2 | |
---|
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 |
---|
6 | ujakra van szukseg. |
---|
7 | |
---|
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. |
---|
16 | |
---|
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: |
---|
23 | |
---|
24 | class list_graph; |
---|
25 | |
---|
26 | class node_iterator; |
---|
27 | trivialis node iterator, csak cimezni lehet vele, pl property vectort |
---|
28 | |
---|
29 | <<<<<<< marci_graph_concept.txt |
---|
30 | class each_node_iterator |
---|
31 | node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato |
---|
32 | ======= |
---|
33 | class each_node_iterator; |
---|
34 | node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato |
---|
35 | >>>>>>> 1.3 |
---|
36 | |
---|
37 | class edge_iterator; |
---|
38 | trivialis edge iterator, csak cimezni lehet vele, pl property vectort |
---|
39 | |
---|
40 | class each_edge_iterator; |
---|
41 | edge iterator a graf osszes elenek bejarasara |
---|
42 | |
---|
43 | <<<<<<< marci_graph_concept.txt |
---|
44 | class out_edge_iterator |
---|
45 | edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato |
---|
46 | ======= |
---|
47 | class out_edge_iterator; |
---|
48 | edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato |
---|
49 | >>>>>>> 1.3 |
---|
50 | |
---|
51 | <<<<<<< marci_graph_concept.txt |
---|
52 | class in_edge_iterator |
---|
53 | edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato |
---|
54 | ======= |
---|
55 | class in_edge_iterator; |
---|
56 | edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato |
---|
57 | >>>>>>> 1.3 |
---|
58 | |
---|
59 | <<<<<<< marci_graph_concept.txt |
---|
60 | class sym_edge_iterator |
---|
61 | edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra |
---|
62 | konvertalhato |
---|
63 | ======= |
---|
64 | class sym_edge_iterator; |
---|
65 | edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato |
---|
66 | >>>>>>> 1.3 |
---|
67 | |
---|
68 | default constructor: |
---|
69 | |
---|
70 | list_graph(); |
---|
71 | |
---|
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. |
---|
80 | |
---|
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&); |
---|
86 | |
---|
87 | node_iterator tail(const edge_iterator&); |
---|
88 | node_iterator head(const edge_iterator&); |
---|
89 | |
---|
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 |
---|
94 | |
---|
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 |
---|
99 | |
---|
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(); |
---|
105 | |
---|
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. |
---|
110 | |
---|
111 | Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai: |
---|
112 | |
---|
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&); |
---|
118 | |
---|
119 | void get_tail(node_iterator&, const edge_iterator&); |
---|
120 | void get_head(node_iterator&, const edge_iterator&); |
---|
121 | |
---|
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&); |
---|
125 | |
---|
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&); |
---|
129 | |
---|
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&); |
---|
135 | |
---|
136 | Pontok azonositasara de meginkabb property vectorokhoz: |
---|
137 | |
---|
138 | int id(const node_iterator&); |
---|
139 | int id(const edge_iterator&); |
---|
140 | |
---|
141 | Pontok es elek hozzaadasanak metodusai: |
---|
142 | |
---|
143 | node_iterator add_node(); |
---|
144 | edge_iterator add_edge(const node_iterator&, const node_iterator&); |
---|
145 | |
---|
146 | Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas: |
---|
147 | ezek nem a list_graph metodusai |
---|
148 | |
---|
149 | friend std::ostream& operator<<(std::ostream&, const node_iterator&); |
---|
150 | friend std::ostream& operator<<(std::ostream&, const edge_iterator&); |
---|
151 | |
---|
152 | node_iterator metodusai: |
---|
153 | node_iterator(); |
---|
154 | bool valid(); |
---|
155 | void make_invalid(); |
---|
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); |
---|
159 | |
---|
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++(); |
---|
164 | |
---|
165 | edge_iterator metodusai: |
---|
166 | edge_iterator(); |
---|
167 | bool valid(); |
---|
168 | void make_invalid(); |
---|
169 | ezek nem tagfvek: |
---|
170 | friend bool operator==(const edge_iterator&, const edge_iterator&); |
---|
171 | friend bool operator!=(const edge_iterator&, const edge_iterator&); |
---|
172 | ujra tagfv-ek. |
---|
173 | //node_iterator tail_node() const; nem javasolt |
---|
174 | //node_iterator head_node() const; nem javasolt |
---|
175 | |
---|
176 | each_edge_iterator metodusai: |
---|
177 | edge_iterator-bol szarmazik |
---|
178 | each_edge_iterator(); |
---|
179 | each_edge_iterator& operator++(); |
---|
180 | |
---|
181 | out_edge_iterator metodusai: |
---|
182 | edge_iterator-bol szarmazik |
---|
183 | out_edge_iterator(); |
---|
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; |
---|
188 | |
---|
189 | |
---|
190 | in_edge_iterator metodusai: |
---|
191 | edge_iterator-bol szarmazik |
---|
192 | in_edge_iterator(); |
---|
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; |
---|
197 | |
---|
198 | |
---|
199 | sym_edge_iterator metodusai: |
---|
200 | edge_iterator-bol szarmazik |
---|
201 | sym_edge_iterator(); |
---|
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; |
---|
206 | |
---|
207 | Node propery array-okrol: |
---|
208 | |
---|
209 | template <typename graph_type, typename T> |
---|
210 | class node_property_vector; |
---|
211 | |
---|
212 | metodusok: |
---|
213 | |
---|
214 | node_property_vector(graph_type&); |
---|
215 | void put(graph_type::node_iterator, const T&); |
---|
216 | T get(graph_type::node_iterator); |
---|
217 | |
---|
218 | Ugyanez edge_property_array-okkal |
---|
219 | |
---|
220 | template <typename graph_type, typename T> |
---|
221 | class edge_property_vector; |
---|
222 | |
---|
223 | edge_property_vector(graph_type&); |
---|
224 | void put(graph_type::edge_iterator, const T&); |
---|
225 | get(graph_type::edge_iterator); |
---|
226 | |
---|
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. |
---|
235 | Errol majd kesobb. |
---|
236 | |
---|
237 | marci@cs.elte.hu |
---|