COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_concept.txt @ 31:d93bef0c4ed3

Last change on this file since 31:d93bef0c4ed3 was 30:10a3f2e0928c, checked in by jacint, 20 years ago

is_valid changed to valid

File size: 8.2 KB
Line 
1ETIK-OL-NOLIB-NEGRES graph concept-ek.
2
3 Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
4A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
5operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
6ujakra van szukseg.
7
8 Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
9az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet
10ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal
11ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly,
12a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere,
13a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen
14property_vector csak azokra a graf-objektumokra ervenyes, melyek
15letrehozasanak pillanataban a grafhoz tartoznak.
16
17marci_bfs.hh          //bfs, tejesen kiserleti
18marci_graph_demo.cc  //peldaprogi a lisas graf hasznalatahoz
19marci_list_graph.hh  //list_graph megvalositas
20marci_max_flow.hh     //folyam, kiserleti
21marci_property_vector.hh //property vector megvalosites indexelt grafokhoz     
22graf es iterator tipusok:
23
24class list_graph;       
25
26class node_iterator;     
27trivialis node iterator, csak cimezni lehet vele, pl property vectort
28
29<<<<<<< marci_graph_concept.txt
30class each_node_iterator
31node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
32=======
33class each_node_iterator;
34node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
35>>>>>>> 1.3
36
37class edge_iterator;
38trivialis edge iterator, csak cimezni lehet vele, pl property vectort
39
40class each_edge_iterator;
41edge iterator a graf osszes elenek bejarasara
42
43<<<<<<< marci_graph_concept.txt
44class out_edge_iterator
45edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
46=======
47class out_edge_iterator;
48edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
49>>>>>>> 1.3
50
51<<<<<<< marci_graph_concept.txt
52class in_edge_iterator
53edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
54=======
55class in_edge_iterator;
56edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
57>>>>>>> 1.3
58     
59<<<<<<< marci_graph_concept.txt
60class sym_edge_iterator
61edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
62konvertalhato
63=======
64class sym_edge_iterator;
65edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
66>>>>>>> 1.3
67
68default constructor:
69
70list_graph();
71   
72A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
73Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
74ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
75iteratorok metodusait ne hasznaljuk. Miert? Azt  szeretnenk, ha 1 ponthalmazon
76van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
77out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
78out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
79esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
80
81each_node_iterator first_node();
82each_edge_iterator first_edge();
83out_edge_iterator first_out_edge(const node_iterator&);
84in_edge_iterator first_in_edge(const node_iterator&);
85sym_edge_iterator first_sym_edge(const node_iterator&);
86
87node_iterator tail(const edge_iterator&);
88node_iterator head(const edge_iterator&);
89
90node_iterator a_node(const out_edge_iterator&);
91node_iterator a_node(const in_edge_iterator&);
92node_iterator a_node(const sym_edge_iterator&);
93//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
94
95node_iterator b_node(const out_edge_iterator&);
96node_iterator b_node(const in_edge_iterator&);
97node_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
107tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
108lehet ervenytelent csinalni.
109Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
110
111Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
112
113void get_first(each_node_iterator&);
114void get_first(each_edge_iterator&);
115void get_first(out_edge_iterator&, const node_iterator&);
116void get_first(in_edge_iterator&, const node_iterator&);
117void get_first(sym_edge_iterator&, const node_iterator&);
118
119void get_tail(node_iterator&, const edge_iterator&);
120void get_head(node_iterator&, const edge_iterator&);
121
122void get_a_node(node_iterator&, const out_edge_iterator&);
123void get_a_node(node_iterator&, const in_edge_iterator&);
124void get_a_node(node_iterator&, const sym_edge_iterator&);
125   
126void get_b_node(node_iterator&, const out_edge_iterator&);
127void get_b_node(node_iterator&, const in_edge_iterator&);
128void 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 
136Pontok azonositasara de meginkabb property vectorokhoz:
137
138int id(const node_iterator&);
139int id(const edge_iterator&);
140
141Pontok es elek hozzaadasanak metodusai:
142
143node_iterator add_node();
144edge_iterator add_edge(const node_iterator&, const node_iterator&);
145
146Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
147ezek nem a list_graph metodusai
148
149friend std::ostream& operator<<(std::ostream&, const node_iterator&);
150friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
151
152node_iterator metodusai:
153node_iterator();
154bool valid();
155void make_invalid();
156ezek nem tagfuggvenyek:
157friend bool operator==(const node_iterator&, const node_iterator&);
158friend bool operator!=(const node_iterator& u, const node_iterator& v);
159   
160each_node_iterator metodusai:
161ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
162each_node_iterator();
163each_node_iterator& operator++();
164
165edge_iterator metodusai:
166edge_iterator();
167bool valid();
168void make_invalid();
169ezek nem tagfvek:
170friend bool operator==(const edge_iterator&, const edge_iterator&);
171friend bool operator!=(const edge_iterator&, const edge_iterator&);
172ujra tagfv-ek.
173//node_iterator tail_node() const;              nem javasolt
174//node_iterator head_node() const;              nem javasolt
175   
176each_edge_iterator metodusai:
177edge_iterator-bol szarmazik
178each_edge_iterator();
179each_edge_iterator& operator++();
180 
181out_edge_iterator metodusai:
182edge_iterator-bol szarmazik
183out_edge_iterator();
184//out_edge_iterator(const node_iterator&);      nem javasolt
185out_edge_iterator& operator++();
186//node_iterator a_node() const;         nem javasolt
187//node_iterator b_node() const;
188   
189 
190in_edge_iterator metodusai:
191edge_iterator-bol szarmazik
192in_edge_iterator();
193//in_edge_iterator(const node_iterator&);       nem javasolt
194in_edge_iterator& operator++();
195//node_iterator a_node() const;         nem javasolt
196//node_iterator b_node() const;
197
198
199sym_edge_iterator metodusai:
200edge_iterator-bol szarmazik
201sym_edge_iterator();
202//sym_edge_iterator(const node_iterator&);      nem javasolt
203sym_edge_iterator& operator++();
204//node_iterator a_node() const;         nem javasolt
205//node_iterator b_node() const;
206               
207Node propery array-okrol:
208
209template <typename graph_type, typename T>
210class node_property_vector;
211
212metodusok:
213
214node_property_vector(graph_type&);
215void put(graph_type::node_iterator, const T&);
216T get(graph_type::node_iterator);
217
218Ugyanez edge_property_array-okkal
219
220template <typename graph_type, typename T>
221class edge_property_vector;
222
223edge_property_vector(graph_type&);
224void put(graph_type::edge_iterator, const T&);
225get(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
229csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
230Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
231graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
232tobb grafot ugyanazon pont-iteratorokkal.
233 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
234at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
235Errol majd kesobb.
236
237marci@cs.elte.hu
Note: See TracBrowser for help on using the repository browser.