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_graph_traits.hh //alapertelmezett graph_traits
20 marci_list_graph.hh //list_graph megvalositas
21 marci_max_flow.hh //folyam, kiserleti
22 marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
23 graf es iterator tipusok:
28 trivialis node iterator, csak cimezni lehet vele, pl property vectort
30 class each_node_iterator
31 node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
34 trivialis edge iterator, csak cimezni lehet vele, pl property vectort
36 class each_edge_iterator
37 edge iterator a graf osszes elenek bejarasara
39 class out_edge_iterator
40 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
42 class in_edge_iterator
43 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
45 class sym_edge_iterator
46 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
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:
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.
142 each_node_iterator& operator++()
144 edge_iterator metodusai:
148 friend bool operator==(const edge_iterator&, const edge_iterator&)
149 friend bool operator!=(const edge_iterator&, const edge_iterator&)
151 //node_iterator tail_node() const nem javasolt
152 //node_iterator head_node() const nem javasolt
154 each_edge_iterator metodusai:
155 edge_iterator-bol szarmazik
157 each_edge_iterator& operator++()
159 out_edge_iterator metodusai:
160 edge_iterator-bol szarmazik
162 //out_edge_iterator(const node_iterator&) nem javasolt
163 out_edge_iterator& operator++()
164 //node_iterator a_node() const nem javasolt
165 //node_iterator b_node() const
168 in_edge_iterator metodusai:
169 edge_iterator-bol szarmazik
171 //in_edge_iterator(const node_iterator&) nem javasolt
172 in_edge_iterator& operator++()
173 //node_iterator a_node() const nem javasolt
174 //node_iterator b_node() const
177 sym_edge_iterator metodusai:
178 edge_iterator-bol szarmazik
180 //sym_edge_iterator(const node_iterator&) nem javasolt
181 sym_edge_iterator& operator++()
182 //node_iterator a_node() const nem javasolt
183 //node_iterator b_node() const
185 Node propery array-okrol:
187 template <typename graph_type, typename T>
188 class node_property_vector
192 node_property_vector(graph_type&)
193 void put(graph_traits<graph_type>::node_iterator, const T&)
194 T get(graph_traits<graph_type>::node_iterator)
196 Ugyanez edge_property_array-okkal
198 template <typename graph_type, typename T>
199 class edge_property_vector
201 edge_property_vector(graph_type&)
202 void put(graph_traits<graph_type>::edge_iterator, const T&)
203 get(graph_traits<graph_type>::edge_iterator)
205 Ennyi nem javasolas utan, meg nehany szo.
206 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
207 csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
208 Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
209 graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
210 tobb grafot ugyanazon pont-iteratorokkal.
211 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
212 at a propertyket az algoritmusoknak, algoritmus-objektumoknak.