COIN-OR::LEMON - Graph Library

Context Navigation

source: lemon-0.x/src/work/marci_graph_concept.txt @ 21:181b37336b29

Last change on this file since 21:181b37336b29 was 19:3151a1026db9, checked in by marci, 21 years ago
* empty log message *
File size: 7.6 KB

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

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

Download in other formats: