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 class each_node_iterator;
30 node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
33 trivialis edge iterator, csak cimezni lehet vele, pl property vectort
35 class each_edge_iterator;
36 edge iterator a graf osszes elenek bejarasara
38 class out_edge_iterator;
39 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
41 class in_edge_iterator;
42 edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
44 class sym_edge_iterator;
45 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
52 A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
53 Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
54 ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
55 iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
56 van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
57 out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
58 out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
59 esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
61 each_node_iterator first_node();
62 each_edge_iterator first_edge();
63 out_edge_iterator first_out_edge(const node_iterator&);
64 in_edge_iterator first_in_edge(const node_iterator&);
65 sym_edge_iterator first_sym_edge(const node_iterator&);
67 node_iterator tail(const edge_iterator&);
68 node_iterator head(const edge_iterator&);
70 node_iterator a_node(const out_edge_iterator&);
71 node_iterator a_node(const in_edge_iterator&);
72 node_iterator a_node(const sym_edge_iterator&);
73 //az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
75 node_iterator b_node(const out_edge_iterator&);
76 node_iterator b_node(const in_edge_iterator&);
77 node_iterator b_node(const sym_edge_iterator&);
78 //az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
80 //node_iterator invalid_node();
81 //edge_iterator invalid_edge();
82 //out_edge_iterator invalid_out_edge();
83 //in_edge_iterator invalid_in_edge();
84 //sym_edge_iterator invalid_sym_edge();
86 //az iteratorok ures konstruktorai meghatarozatlan
87 tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
88 lehet ervenytelent csinalni.
89 Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
91 Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
93 void get_first(each_node_iterator&);
94 void get_first(each_edge_iterator&);
95 void get_first(out_edge_iterator&, const node_iterator&);
96 void get_first(in_edge_iterator&, const node_iterator&);
97 void get_first(sym_edge_iterator&, const node_iterator&);
99 void get_tail(node_iterator&, const edge_iterator&);
100 void get_head(node_iterator&, const edge_iterator&);
102 void get_a_node(node_iterator&, const out_edge_iterator&);
103 void get_a_node(node_iterator&, const in_edge_iterator&);
104 void get_a_node(node_iterator&, const sym_edge_iterator&);
106 void get_b_node(node_iterator&, const out_edge_iterator&);
107 void get_b_node(node_iterator&, const in_edge_iterator&);
108 void get_b_node(node_iterator&, const sym_edge_iterator&);
110 //void get_invalid(node_iterator&);
111 //void get_invalid(edge_iterator&);
112 //void get_invalid(out_edge_iterator&);
113 //void get_invalid(in_edge_iterator&);
114 //void get_invalid(sym_edge_iterator&);
116 Pontok azonositasara de meginkabb property vectorokhoz:
118 int id(const node_iterator&);
119 int id(const edge_iterator&);
121 Pontok es elek hozzaadasanak metodusai:
123 node_iterator add_node();
124 edge_iterator add_edge(const node_iterator&, const node_iterator&);
126 Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
127 ezek nem a list_graph metodusai
129 friend std::ostream& operator<<(std::ostream&, const node_iterator&);
130 friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
132 node_iterator metodusai:
136 ezek nem tagfuggvenyek:
137 friend bool operator==(const node_iterator&, const node_iterator&);
138 friend bool operator!=(const node_iterator& u, const node_iterator& v);
140 each_node_iterator metodusai:
141 ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
142 each_node_iterator();
143 each_node_iterator& operator++();
145 edge_iterator metodusai:
150 friend bool operator==(const edge_iterator&, const edge_iterator&);
151 friend bool operator!=(const edge_iterator&, const edge_iterator&);
153 //node_iterator tail_node() const; nem javasolt
154 //node_iterator head_node() const; nem javasolt
156 each_edge_iterator metodusai:
157 edge_iterator-bol szarmazik
158 each_edge_iterator();
159 each_edge_iterator& operator++();
161 out_edge_iterator metodusai:
162 edge_iterator-bol szarmazik
164 //out_edge_iterator(const node_iterator&); nem javasolt
165 out_edge_iterator& operator++();
166 //node_iterator a_node() const; nem javasolt
167 //node_iterator b_node() const;
170 in_edge_iterator metodusai:
171 edge_iterator-bol szarmazik
173 //in_edge_iterator(const node_iterator&); nem javasolt
174 in_edge_iterator& operator++();
175 //node_iterator a_node() const; nem javasolt
176 //node_iterator b_node() const;
179 sym_edge_iterator metodusai:
180 edge_iterator-bol szarmazik
182 //sym_edge_iterator(const node_iterator&); nem javasolt
183 sym_edge_iterator& operator++();
184 //node_iterator a_node() const; nem javasolt
185 //node_iterator b_node() const;
187 Node propery array-okrol:
189 template <typename graph_type, typename T>
190 class node_property_vector;
194 node_property_vector(graph_type&);
195 void put(graph_type::node_iterator, const T&);
196 T get(graph_type::node_iterator);
198 Ugyanez edge_property_array-okkal
200 template <typename graph_type, typename T>
201 class edge_property_vector;
203 edge_property_vector(graph_type&);
204 void put(graph_type::edge_iterator, const T&);
205 get(graph_type::edge_iterator);
207 Ennyi nem javasolas utan, meg nehany szo.
208 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
209 csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
210 Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
211 graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
212 tobb grafot ugyanazon pont-iteratorokkal.
213 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
214 at a propertyket az algoritmusoknak, algoritmus-objektumoknak.