lemon-0.x: src/work/marci_graph_concept.txt@f505c414feb9

     1 ETIK-OL-NOLIB-NEGRES graph concept-ek.

     3  Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.

     4 A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi

     5 operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen

     6 ujakra van szukseg.

     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.

    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:

    24 class list_graph;

    26 class node_iterator;

    27 trivialis node iterator, csak cimezni lehet vele, pl property vectort

    29 <<<<<<< marci_graph_concept.txt

    30 class each_node_iterator

    31 node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato

    32 =======

    33 class each_node_iterator;

    34 node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato

    35 >>>>>>> 1.3

    37 class edge_iterator;

    38 trivialis edge iterator, csak cimezni lehet vele, pl property vectort

    40 class each_edge_iterator;

    41 edge iterator a graf osszes elenek bejarasara

    43 <<<<<<< marci_graph_concept.txt

    44 class out_edge_iterator

    45 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato

    46 =======

    47 class out_edge_iterator;

    48 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato

    49 >>>>>>> 1.3

    51 <<<<<<< marci_graph_concept.txt

    52 class in_edge_iterator

    53 edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato

    54 =======

    55 class in_edge_iterator;

    56 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato

    57 >>>>>>> 1.3

    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 =======

    64 class sym_edge_iterator;

    65 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato

    66 >>>>>>> 1.3

    68 default constructor:

    70 list_graph();

    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.

    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&);

    87 node_iterator tail(const edge_iterator&);

    88 node_iterator head(const edge_iterator&);

    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&);

    93 //az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t

    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&);

    98 //az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t

   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();

   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.

   111 Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:

   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&);

   119 void get_tail(node_iterator&, const edge_iterator&);

   120 void get_head(node_iterator&, const edge_iterator&);

   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&);

   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&);

   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&);

   136 Pontok azonositasara de meginkabb property vectorokhoz:

   138 int id(const node_iterator&);

   139 int id(const edge_iterator&);

   141 Pontok es elek hozzaadasanak metodusai:

   143 node_iterator add_node();

   144 edge_iterator add_edge(const node_iterator&, const node_iterator&);

   146 Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:

   147 ezek nem a list_graph metodusai

   149 friend std::ostream& operator<<(std::ostream&, const node_iterator&);

   150 friend std::ostream& operator<<(std::ostream&, const edge_iterator&);

   152 node_iterator metodusai:

   153 node_iterator();

   154 bool valid();

   155 void make_invalid();

   156 ezek nem tagfuggvenyek:

   157 friend bool operator==(const node_iterator&, const node_iterator&);

   158 friend bool operator!=(const node_iterator& u, const node_iterator& v);

   160 each_node_iterator metodusai:

   161 ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.

   162 each_node_iterator();

   163 each_node_iterator& operator++();

   165 edge_iterator metodusai:

   166 edge_iterator();

   167 bool valid();

   168 void make_invalid();

   169 ezek nem tagfvek:

   170 friend bool operator==(const edge_iterator&, const edge_iterator&);

   171 friend bool operator!=(const edge_iterator&, const edge_iterator&);

   172 ujra tagfv-ek.

   173 //node_iterator tail_node() const;		nem javasolt

   174 //node_iterator head_node() const;		nem javasolt

   176 each_edge_iterator metodusai:

   177 edge_iterator-bol szarmazik

   178 each_edge_iterator();

   179 each_edge_iterator& operator++();

   181 out_edge_iterator metodusai:

   182 edge_iterator-bol szarmazik

   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;

   190 in_edge_iterator metodusai:

   191 edge_iterator-bol szarmazik

   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;

   199 sym_edge_iterator metodusai:

   200 edge_iterator-bol szarmazik

   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;

   207 Node propery array-okrol:

   209 template <typename graph_type, typename T>

   210 class node_property_vector;

   212 metodusok:

   214 node_property_vector(graph_type&);

   215 void put(graph_type::node_iterator, const T&);

   216 T get(graph_type::node_iterator);

   218 Ugyanez edge_property_array-okkal

   220 template <typename graph_type, typename T>

   221 class edge_property_vector;

   223 edge_property_vector(graph_type&);

   224 void put(graph_type::edge_iterator, const T&);

   225 get(graph_type::edge_iterator);

   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.

   237 marci@cs.elte.hu

author	jacint
	Fri, 23 Jan 2004 22:26:13 +0000
changeset 33	f505c414feb9
parent 19	3151a1026db9
child 40	ffaa9448964c
permissions	-rw-r--r--