COIN-OR::LEMON - Graph Library

Context Navigation

source: lemon-0.x/src/work/marci_graph_concept.txt @ 39:28b0d751d29f

Last change on this file since 39:28b0d751d29f was 30:10a3f2e0928c, checked in by jacint, 21 years ago
is_valid changed to valid
File size: 8.2 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
[30]	29	<<<<<<< marci_graph_concept.txt
	30	class each_node_iterator
	31	node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
	32	=======
[15]	33	class each_node_iterator;
[9]	34	node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
[30]	35	>>>>>>> 1.3
[9]	36
[15]	37	class edge_iterator;
[9]	38	trivialis edge iterator, csak cimezni lehet vele, pl property vectort
	39
[15]	40	class each_edge_iterator;
[9]	41	edge iterator a graf osszes elenek bejarasara
	42
[30]	43	<<<<<<< marci_graph_concept.txt
	44	class out_edge_iterator
	45	edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
	46	=======
[15]	47	class out_edge_iterator;
[9]	48	edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
[30]	49	>>>>>>> 1.3
[9]	50
[30]	51	<<<<<<< marci_graph_concept.txt
	52	class in_edge_iterator
	53	edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
	54	=======
[15]	55	class in_edge_iterator;
[9]	56	edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
[30]	57	>>>>>>> 1.3
[9]	58
[30]	59	<<<<<<< marci_graph_concept.txt
	60	class sym_edge_iterator
	61	edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
	62	konvertalhato
	63	=======
[15]	64	class sym_edge_iterator;
[9]	65	edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
[30]	66	>>>>>>> 1.3
[9]	67
	68	default constructor:
	69
[15]	70	list_graph();
[9]	71
	72	A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
	73	Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve
	74	ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az
	75	iteratorok metodusait ne hasznaljuk. Miert? Azt szeretnenk, ha 1 ponthalmazon
	76	van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont
	77	out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert
	78	out_edge_iterator(const node_iterator&) hasznalata nem javasolt,
	79	esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj.
	80
[15]	81	each_node_iterator first_node();
	82	each_edge_iterator first_edge();
	83	out_edge_iterator first_out_edge(const node_iterator&);
	84	in_edge_iterator first_in_edge(const node_iterator&);
	85	sym_edge_iterator first_sym_edge(const node_iterator&);
[9]	86
[15]	87	node_iterator tail(const edge_iterator&);
	88	node_iterator head(const edge_iterator&);
[9]	89
[15]	90	node_iterator a_node(const out_edge_iterator&);
	91	node_iterator a_node(const in_edge_iterator&);
	92	node_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]	95	node_iterator b_node(const out_edge_iterator&);
	96	node_iterator b_node(const in_edge_iterator&);
	97	node_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
	107	tartalmu konstruktort adnak vissza, ezekkel a matodusokkal
	108	lehet ervenytelent csinalni.
	109	Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
	110
	111	Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
	112
[15]	113	void get_first(each_node_iterator&);
	114	void get_first(each_edge_iterator&);
	115	void get_first(out_edge_iterator&, const node_iterator&);
	116	void get_first(in_edge_iterator&, const node_iterator&);
	117	void get_first(sym_edge_iterator&, const node_iterator&);
[9]	118
[15]	119	void get_tail(node_iterator&, const edge_iterator&);
	120	void get_head(node_iterator&, const edge_iterator&);
[9]	121
[15]	122	void get_a_node(node_iterator&, const out_edge_iterator&);
	123	void get_a_node(node_iterator&, const in_edge_iterator&);
	124	void get_a_node(node_iterator&, const sym_edge_iterator&);
[9]	125
[15]	126	void get_b_node(node_iterator&, const out_edge_iterator&);
	127	void get_b_node(node_iterator&, const in_edge_iterator&);
	128	void 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
	136	Pontok azonositasara de meginkabb property vectorokhoz:
	137
[15]	138	int id(const node_iterator&);
	139	int id(const edge_iterator&);
[9]	140
	141	Pontok es elek hozzaadasanak metodusai:
	142
[15]	143	node_iterator add_node();
	144	edge_iterator add_edge(const node_iterator&, const node_iterator&);
[9]	145
	146	Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
	147	ezek nem a list_graph metodusai
	148
[15]	149	friend std::ostream& operator<<(std::ostream&, const node_iterator&);
	150	friend std::ostream& operator<<(std::ostream&, const edge_iterator&);
[9]	151
	152	node_iterator metodusai:
[15]	153	node_iterator();
[19]	154	bool valid();
[15]	155	void make_invalid();
[9]	156	ezek nem tagfuggvenyek:
[15]	157	friend bool operator==(const node_iterator&, const node_iterator&);
	158	friend bool operator!=(const node_iterator& u, const node_iterator& v);
[9]	159
	160	each_node_iterator metodusai:
	161	ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
[15]	162	each_node_iterator();
	163	each_node_iterator& operator++();
[9]	164
	165	edge_iterator metodusai:
[15]	166	edge_iterator();
[19]	167	bool valid();
[15]	168	void make_invalid();
[9]	169	ezek nem tagfvek:
[15]	170	friend bool operator==(const edge_iterator&, const edge_iterator&);
	171	friend bool operator!=(const edge_iterator&, const edge_iterator&);
[9]	172	ujra tagfv-ek.
[15]	173	//node_iterator tail_node() const; nem javasolt
	174	//node_iterator head_node() const; nem javasolt
[9]	175
	176	each_edge_iterator metodusai:
	177	edge_iterator-bol szarmazik
[15]	178	each_edge_iterator();
	179	each_edge_iterator& operator++();
[9]	180
	181	out_edge_iterator metodusai:
	182	edge_iterator-bol szarmazik
[15]	183	out_edge_iterator();
	184	//out_edge_iterator(const node_iterator&); nem javasolt
	185	out_edge_iterator& operator++();
	186	//node_iterator a_node() const; nem javasolt
	187	//node_iterator b_node() const;
[9]	188
	189
	190	in_edge_iterator metodusai:
	191	edge_iterator-bol szarmazik
[15]	192	in_edge_iterator();
	193	//in_edge_iterator(const node_iterator&); nem javasolt
	194	in_edge_iterator& operator++();
	195	//node_iterator a_node() const; nem javasolt
	196	//node_iterator b_node() const;
[9]	197
	198
	199	sym_edge_iterator metodusai:
	200	edge_iterator-bol szarmazik
[15]	201	sym_edge_iterator();
	202	//sym_edge_iterator(const node_iterator&); nem javasolt
	203	sym_edge_iterator& operator++();
	204	//node_iterator a_node() const; nem javasolt
	205	//node_iterator b_node() const;
[9]	206
	207	Node propery array-okrol:
	208
	209	template <typename graph_type, typename T>
[15]	210	class node_property_vector;
[9]	211
	212	metodusok:
	213
[15]	214	node_property_vector(graph_type&);
[19]	215	void put(graph_type::node_iterator, const T&);
	216	T get(graph_type::node_iterator);
[9]	217
	218	Ugyanez edge_property_array-okkal
	219
	220	template <typename graph_type, typename T>
[15]	221	class edge_property_vector;
[9]	222
[15]	223	edge_property_vector(graph_type&);
[19]	224	void put(graph_type::edge_iterator, const T&);
	225	get(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
	229	csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban.
	230	Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a
	231	graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
	232	tobb grafot ugyanazon pont-iteratorokkal.
	233	Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk
	234	at a propertyket az algoritmusoknak, algoritmus-objektumoknak.
	235	Errol majd kesobb.
	236
[15]	237	marci@cs.elte.hu

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

Download in other formats: