COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_concept.txt @ 172:c645f4a2a6ae

Last change on this file since 172:c645f4a2a6ae was 40:ffaa9448964c, checked in by Mihaly Barasz, 17 years ago

Jacint conflict-janak kijavitasa

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