COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_concept.txt @ 10:436df3c980d1

Last change on this file since 10:436df3c980d1 was 10:436df3c980d1, checked in by marci, 17 years ago

property vectorokhoz korabban is letezo
fill constructorok dokumentaciojat beraktam a doksiba

File size: 7.7 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_graph_traits.hh //alapertelmezett graph_traits
20marci_list_graph.hh  //list_graph megvalositas
21marci_max_flow.hh     //folyam, kiserleti
22marci_property_vector.hh //property vector megvalosites indexelt grafokhoz     
23graf es iterator tipusok:
24
25class list_graph         
26
27class node_iterator     
28trivialis node iterator, csak cimezni lehet vele, pl property vectort
29
30class each_node_iterator
31node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
32
33class edge_iterator
34trivialis edge iterator, csak cimezni lehet vele, pl property vectort
35
36class each_edge_iterator
37edge iterator a graf osszes elenek bejarasara
38
39class out_edge_iterator
40edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
41
42class in_edge_iterator
43edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
44     
45class sym_edge_iterator
46edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
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
80node_iterator invalid_node()
81edge_iterator invalid_edge()
82out_edge_iterator invalid_out_edge()
83in_edge_iterator invalid_in_edge()
84sym_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 
110void get_invalid(node_iterator&)
111void get_invalid(edge_iterator&)
112void get_invalid(out_edge_iterator&)
113void get_invalid(in_edge_iterator&)
114void 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 is_valid()
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 is_valid()
147ezek nem tagfvek:
148friend bool operator==(const edge_iterator&, const edge_iterator&)
149friend bool operator!=(const edge_iterator&, const edge_iterator&)
150ujra tagfv-ek.
151//node_iterator tail_node() const               nem javasolt
152//node_iterator head_node() const               nem javasolt
153   
154each_edge_iterator metodusai:
155edge_iterator-bol szarmazik
156each_edge_iterator()
157each_edge_iterator& operator++()
158 
159out_edge_iterator metodusai:
160edge_iterator-bol szarmazik
161out_edge_iterator()
162//out_edge_iterator(const node_iterator&)       nem javasolt
163out_edge_iterator& operator++()
164//node_iterator a_node() const          nem javasolt
165//node_iterator b_node() const
166   
167 
168in_edge_iterator metodusai:
169edge_iterator-bol szarmazik
170in_edge_iterator()
171//in_edge_iterator(const node_iterator&)        nem javasolt
172in_edge_iterator& operator++()
173//node_iterator a_node() const          nem javasolt
174//node_iterator b_node() const
175
176
177sym_edge_iterator metodusai:
178edge_iterator-bol szarmazik
179sym_edge_iterator()
180//sym_edge_iterator(const node_iterator&)       nem javasolt
181sym_edge_iterator& operator++()
182//node_iterator a_node() const          nem javasolt
183//node_iterator b_node() const
184               
185Node propery array-okrol:
186
187template <typename graph_type, typename T>
188class node_property_vector
189
190metodusok:
191
192node_property_vector(graph_type&)
193node_property_vector(graph_type&, T a)
194fill constructor, a-val kitolt
195void put(graph_traits<graph_type>::node_iterator, const T&)
196T get(graph_traits<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&)
204edge_property_vector(graph_type&, T a)
205fill constructor, a-val kitolt
206void put(graph_traits<graph_type>::edge_iterator, const T&)
207get(graph_traits<graph_type>::edge_iterator)
208
209 Ennyi nem javasolas utan, meg nehany szo.
210 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
211csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
212Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
213graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
214tobb grafot ugyanazon pont-iteratorokkal.
215 Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
216at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
217Errol majd kesobb.
218
219marci@cs.elte.hu
220
221
222
Note: See TracBrowser for help on using the repository browser.