COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_graph_concept.txt @ 30:10a3f2e0928c

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

is_valid changed to valid

File size: 8.2 KB
RevLine 
[9]1ETIK-OL-NOLIB-NEGRES graph concept-ek.
2
[30]3 Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
[9]4A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
[30]5operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
[9]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
[15]24class list_graph;       
[9]25
[15]26class node_iterator;     
[9]27trivialis node iterator, csak cimezni lehet vele, pl property vectort
28
[30]29<<<<<<< marci_graph_concept.txt
30class each_node_iterator
31node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
32=======
[15]33class each_node_iterator;
[9]34node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
[30]35>>>>>>> 1.3
[9]36
[15]37class edge_iterator;
[9]38trivialis edge iterator, csak cimezni lehet vele, pl property vectort
39
[15]40class each_edge_iterator;
[9]41edge iterator a graf osszes elenek bejarasara
42
[30]43<<<<<<< marci_graph_concept.txt
44class out_edge_iterator
45edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
46=======
[15]47class out_edge_iterator;
[9]48edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
[30]49>>>>>>> 1.3
[9]50
[30]51<<<<<<< marci_graph_concept.txt
52class in_edge_iterator
53edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
54=======
[15]55class in_edge_iterator;
[9]56edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
[30]57>>>>>>> 1.3
[9]58     
[30]59<<<<<<< marci_graph_concept.txt
60class sym_edge_iterator
61edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
62konvertalhato
63=======
[15]64class sym_edge_iterator;
[9]65edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
[30]66>>>>>>> 1.3
[9]67
68default constructor:
69
[15]70list_graph();
[9]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
[15]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&);
[9]86
[15]87node_iterator tail(const edge_iterator&);
88node_iterator head(const edge_iterator&);
[9]89
[15]90node_iterator a_node(const out_edge_iterator&);
91node_iterator a_node(const in_edge_iterator&);
92node_iterator a_node(const sym_edge_iterator&);
[9]93//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
94
[15]95node_iterator b_node(const out_edge_iterator&);
96node_iterator b_node(const in_edge_iterator&);
97node_iterator b_node(const sym_edge_iterator&);
[9]98//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
99
[15]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();
[9]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
[15]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&);
[9]118
[15]119void get_tail(node_iterator&, const edge_iterator&);
120void get_head(node_iterator&, const edge_iterator&);
[9]121
[15]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&);
[9]125   
[15]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&);
[9]129 
[15]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&);
[9]135 
136Pontok azonositasara de meginkabb property vectorokhoz:
137
[15]138int id(const node_iterator&);
139int id(const edge_iterator&);
[9]140
141Pontok es elek hozzaadasanak metodusai:
142
[15]143node_iterator add_node();
144edge_iterator add_edge(const node_iterator&, const node_iterator&);
[9]145
146Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
147ezek nem a list_graph metodusai
148
[15]149friend std::ostream& operator<<(std::ostream&, const node_iterator&);
150friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
[9]151
152node_iterator metodusai:
[15]153node_iterator();
[19]154bool valid();
[15]155void make_invalid();
[9]156ezek nem tagfuggvenyek:
[15]157friend bool operator==(const node_iterator&, const node_iterator&);
158friend bool operator!=(const node_iterator& u, const node_iterator& v);
[9]159   
160each_node_iterator metodusai:
161ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
[15]162each_node_iterator();
163each_node_iterator& operator++();
[9]164
165edge_iterator metodusai:
[15]166edge_iterator();
[19]167bool valid();
[15]168void make_invalid();
[9]169ezek nem tagfvek:
[15]170friend bool operator==(const edge_iterator&, const edge_iterator&);
171friend bool operator!=(const edge_iterator&, const edge_iterator&);
[9]172ujra tagfv-ek.
[15]173//node_iterator tail_node() const;              nem javasolt
174//node_iterator head_node() const;              nem javasolt
[9]175   
176each_edge_iterator metodusai:
177edge_iterator-bol szarmazik
[15]178each_edge_iterator();
179each_edge_iterator& operator++();
[9]180 
181out_edge_iterator metodusai:
182edge_iterator-bol szarmazik
[15]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;
[9]188   
189 
190in_edge_iterator metodusai:
191edge_iterator-bol szarmazik
[15]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;
[9]197
198
199sym_edge_iterator metodusai:
200edge_iterator-bol szarmazik
[15]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;
[9]206               
207Node propery array-okrol:
208
209template <typename graph_type, typename T>
[15]210class node_property_vector;
[9]211
212metodusok:
213
[15]214node_property_vector(graph_type&);
[19]215void put(graph_type::node_iterator, const T&);
216T get(graph_type::node_iterator);
[9]217
218Ugyanez edge_property_array-okkal
219
220template <typename graph_type, typename T>
[15]221class edge_property_vector;
[9]222
[15]223edge_property_vector(graph_type&);
[19]224void put(graph_type::edge_iterator, const T&);
225get(graph_type::edge_iterator);
[9]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
[15]237marci@cs.elte.hu
Note: See TracBrowser for help on using the repository browser.