Context Navigation

marci_graph_concept.txt @ 132:1ac27e476e25

Last change on this file since 132:1ac27e476e25 was 40:ffaa9448964c, checked in by Mihaly Barasz, 21 years ago
Jacint conflict-janak kijavitasa
File size: 7.6 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: lemon-0.x/src/work/marci_graph_concept.txt @ 132:1ac27e476e25

Download in other formats: