COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_concept.txt @ 19:3151a1026db9

Last change on this file since 19:3151a1026db9 was 19:3151a1026db9, checked in by marci, 20 years ago

* empty log message *

File size: 7.6 KB
Line 
1ETIK-OL-NOLIB-NEGRES graph concept-ek.
2
3 Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok.
4A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
5operacio elegzesere 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
29class each_node_iterator;
30node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
31
32class edge_iterator;
33trivialis edge iterator, csak cimezni lehet vele, pl property vectort
34
35class each_edge_iterator;
36edge iterator a graf osszes elenek bejarasara
37
38class out_edge_iterator;
39edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
40
41class in_edge_iterator;
42edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
43     
44class sym_edge_iterator;
45edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
46
47default constructor:
48
49list_graph();
50   
51A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
52Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
53ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
54iteratorok metodusait ne hasznaljuk. Miert? Azt  szeretnenk, ha 1 ponthalmazon
55van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
56out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
57out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
58esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
59
60each_node_iterator first_node();
61each_edge_iterator first_edge();
62out_edge_iterator first_out_edge(const node_iterator&);
63in_edge_iterator first_in_edge(const node_iterator&);
64sym_edge_iterator first_sym_edge(const node_iterator&);
65
66node_iterator tail(const edge_iterator&);
67node_iterator head(const edge_iterator&);
68
69node_iterator a_node(const out_edge_iterator&);
70node_iterator a_node(const in_edge_iterator&);
71node_iterator a_node(const sym_edge_iterator&);
72//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
73
74node_iterator b_node(const out_edge_iterator&);
75node_iterator b_node(const in_edge_iterator&);
76node_iterator b_node(const sym_edge_iterator&);
77//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
78
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();
84
85//az iteratorok ures konstruktorai meghatarozatlan
86tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
87lehet ervenytelent csinalni.
88Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
89
90Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
91
92void get_first(each_node_iterator&);
93void get_first(each_edge_iterator&);
94void get_first(out_edge_iterator&, const node_iterator&);
95void get_first(in_edge_iterator&, const node_iterator&);
96void get_first(sym_edge_iterator&, const node_iterator&);
97
98void get_tail(node_iterator&, const edge_iterator&);
99void get_head(node_iterator&, const edge_iterator&);
100
101void get_a_node(node_iterator&, const out_edge_iterator&);
102void get_a_node(node_iterator&, const in_edge_iterator&);
103void get_a_node(node_iterator&, const sym_edge_iterator&);
104   
105void get_b_node(node_iterator&, const out_edge_iterator&);
106void get_b_node(node_iterator&, const in_edge_iterator&);
107void get_b_node(node_iterator&, const sym_edge_iterator&);
108 
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&);
114 
115Pontok azonositasara de meginkabb property vectorokhoz:
116
117int id(const node_iterator&);
118int id(const edge_iterator&);
119
120Pontok es elek hozzaadasanak metodusai:
121
122node_iterator add_node();
123edge_iterator add_edge(const node_iterator&, const node_iterator&);
124
125Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
126ezek nem a list_graph metodusai
127
128friend std::ostream& operator<<(std::ostream&, const node_iterator&);
129friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
130
131node_iterator metodusai:
132node_iterator();
133bool valid();
134void make_invalid();
135ezek nem tagfuggvenyek:
136friend bool operator==(const node_iterator&, const node_iterator&);
137friend bool operator!=(const node_iterator& u, const node_iterator& v);
138   
139each_node_iterator metodusai:
140ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
141each_node_iterator();
142each_node_iterator& operator++();
143
144edge_iterator metodusai:
145edge_iterator();
146bool valid();
147void make_invalid();
148ezek nem tagfvek:
149friend bool operator==(const edge_iterator&, const edge_iterator&);
150friend bool operator!=(const edge_iterator&, const edge_iterator&);
151ujra tagfv-ek.
152//node_iterator tail_node() const;              nem javasolt
153//node_iterator head_node() const;              nem javasolt
154   
155each_edge_iterator metodusai:
156edge_iterator-bol szarmazik
157each_edge_iterator();
158each_edge_iterator& operator++();
159 
160out_edge_iterator metodusai:
161edge_iterator-bol szarmazik
162out_edge_iterator();
163//out_edge_iterator(const node_iterator&);      nem javasolt
164out_edge_iterator& operator++();
165//node_iterator a_node() const;         nem javasolt
166//node_iterator b_node() const;
167   
168 
169in_edge_iterator metodusai:
170edge_iterator-bol szarmazik
171in_edge_iterator();
172//in_edge_iterator(const node_iterator&);       nem javasolt
173in_edge_iterator& operator++();
174//node_iterator a_node() const;         nem javasolt
175//node_iterator b_node() const;
176
177
178sym_edge_iterator metodusai:
179edge_iterator-bol szarmazik
180sym_edge_iterator();
181//sym_edge_iterator(const node_iterator&);      nem javasolt
182sym_edge_iterator& operator++();
183//node_iterator a_node() const;         nem javasolt
184//node_iterator b_node() const;
185               
186Node propery array-okrol:
187
188template <typename graph_type, typename T>
189class node_property_vector;
190
191metodusok:
192
193node_property_vector(graph_type&);
194void put(graph_type::node_iterator, const T&);
195T get(graph_type::node_iterator);
196
197Ugyanez edge_property_array-okkal
198
199template <typename graph_type, typename T>
200class edge_property_vector;
201
202edge_property_vector(graph_type&);
203void put(graph_type::edge_iterator, const T&);
204get(graph_type::edge_iterator);
205
206 Ennyi nem javasolas utan, meg nehany szo.
207 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
208csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
209Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
210graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
211tobb grafot ugyanazon pont-iteratorokkal.
212 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
213at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
214Errol majd kesobb.
215
216marci@cs.elte.hu
Note: See TracBrowser for help on using the repository browser.