1 ETIK-OL-NOLIB-NEGRES graph concept-ek.
3 Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok.
4 A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
5 operacio elegzesere 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-a 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-a konvertalhato
41 class in_edge_iterator;
42 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
44 class sym_edge_iterator;
45 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
51 A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
52 Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
53 ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
54 iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
55 van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
56 out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
57 out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
58 esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
60 each_node_iterator first_node();
61 each_edge_iterator first_edge();
62 out_edge_iterator first_out_edge(const node_iterator&);
63 in_edge_iterator first_in_edge(const node_iterator&);
64 sym_edge_iterator first_sym_edge(const node_iterator&);
66 node_iterator tail(const edge_iterator&);
67 node_iterator head(const edge_iterator&);
69 node_iterator a_node(const out_edge_iterator&);
70 node_iterator a_node(const in_edge_iterator&);
71 node_iterator a_node(const sym_edge_iterator&);
72 //az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
74 node_iterator b_node(const out_edge_iterator&);
75 node_iterator b_node(const in_edge_iterator&);
76 node_iterator b_node(const sym_edge_iterator&);
77 //az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
79 //node_iterator invalid_node();
80 //edge_iterator invalid_edge();
81 //out_edge_iterator invalid_out_edge();
82 //in_edge_iterator invalid_in_edge();
83 //sym_edge_iterator invalid_sym_edge();
85 //az iteratorok ures konstruktorai meghatarozatlan
86 tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
87 lehet ervenytelent csinalni.
88 Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
90 Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
92 void get_first(each_node_iterator&);
93 void get_first(each_edge_iterator&);
94 void get_first(out_edge_iterator&, const node_iterator&);
95 void get_first(in_edge_iterator&, const node_iterator&);
96 void get_first(sym_edge_iterator&, const node_iterator&);
98 void get_tail(node_iterator&, const edge_iterator&);
99 void get_head(node_iterator&, const edge_iterator&);
101 void get_a_node(node_iterator&, const out_edge_iterator&);
102 void get_a_node(node_iterator&, const in_edge_iterator&);
103 void get_a_node(node_iterator&, const sym_edge_iterator&);
105 void get_b_node(node_iterator&, const out_edge_iterator&);
106 void get_b_node(node_iterator&, const in_edge_iterator&);
107 void get_b_node(node_iterator&, const sym_edge_iterator&);
109 //void get_invalid(node_iterator&);
110 //void get_invalid(edge_iterator&);
111 //void get_invalid(out_edge_iterator&);
112 //void get_invalid(in_edge_iterator&);
113 //void get_invalid(sym_edge_iterator&);
115 Pontok azonositasara de meginkabb property vectorokhoz:
117 int id(const node_iterator&);
118 int id(const edge_iterator&);
120 Pontok es elek hozzaadasanak metodusai:
122 node_iterator add_node();
123 edge_iterator add_edge(const node_iterator&, const node_iterator&);
125 Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
126 ezek nem a list_graph metodusai
128 friend std::ostream& operator<<(std::ostream&, const node_iterator&);
129 friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
131 node_iterator metodusai:
135 ezek nem tagfuggvenyek:
136 friend bool operator==(const node_iterator&, const node_iterator&);
137 friend bool operator!=(const node_iterator& u, const node_iterator& v);
139 each_node_iterator metodusai:
140 ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
141 each_node_iterator();
142 each_node_iterator& operator++();
144 edge_iterator metodusai:
149 friend bool operator==(const edge_iterator&, const edge_iterator&);
150 friend bool operator!=(const edge_iterator&, const edge_iterator&);
152 //node_iterator tail_node() const; nem javasolt
153 //node_iterator head_node() const; nem javasolt
155 each_edge_iterator metodusai:
156 edge_iterator-bol szarmazik
157 each_edge_iterator();
158 each_edge_iterator& operator++();
160 out_edge_iterator metodusai:
161 edge_iterator-bol szarmazik
163 //out_edge_iterator(const node_iterator&); nem javasolt
164 out_edge_iterator& operator++();
165 //node_iterator a_node() const; nem javasolt
166 //node_iterator b_node() const;
169 in_edge_iterator metodusai:
170 edge_iterator-bol szarmazik
172 //in_edge_iterator(const node_iterator&); nem javasolt
173 in_edge_iterator& operator++();
174 //node_iterator a_node() const; nem javasolt
175 //node_iterator b_node() const;
178 sym_edge_iterator metodusai:
179 edge_iterator-bol szarmazik
181 //sym_edge_iterator(const node_iterator&); nem javasolt
182 sym_edge_iterator& operator++();
183 //node_iterator a_node() const; nem javasolt
184 //node_iterator b_node() const;
186 Node propery array-okrol:
188 template <typename graph_type, typename T>
189 class node_property_vector;
193 node_property_vector(graph_type&);
194 void put(graph_type::node_iterator, const T&);
195 T get(graph_type::node_iterator);
197 Ugyanez edge_property_array-okkal
199 template <typename graph_type, typename T>
200 class edge_property_vector;
202 edge_property_vector(graph_type&);
203 void put(graph_type::edge_iterator, const T&);
204 get(graph_type::edge_iterator);
206 Ennyi nem javasolas utan, meg nehany szo.
207 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
208 csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
209 Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
210 graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
211 tobb grafot ugyanazon pont-iteratorokkal.
212 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
213 at a propertyket az algoritmusoknak, algoritmus-objektumoknak.