source: lemon-0.x/src/work/graph_concept.txt @ 965:1e16b8dac159

ETIK-OL-NOLIB-NEGRES full feature graph minimum concept. 

 Regota filozunk rajta hogy hogy is kene kinezni a fent emlitett concept-nek, 
most 1 egesz konkret javaslatot irnek. A fo cel, hogy lenyegeben 
minden operaciot a graf vegezzen, es az iteratorok csak vmi leiro szerepet 
toltsenek be. Azt is megfigyeltuk, hogy a fo technikai nehezseg, hogy a c++ 
nem tud a visszateresi ertek alapjan megkulonboztetni fuggvenyeket. Ennek 
megfeleloen 2 javaslatot irok most. Az egyikben a fv altal kiszamolt erteket 
az egyik operandusban kapjuk vissza, a masikban egy tag-template specializacip 
eredmenyekent balra adja vissza a cuccot. Nehol referencia van irva ahol nem 
kell, ezen ne tessek fonnakadni.

class Graph;

class NodeIt;      
trivialis node iterator, csak cimezni lehet vele, pl property vectort
class EachNodeIt;
node iterator a graf pontjainak bejarasara, NodeIt-e konvertalhato

class EdgeIt;
trivialis edge iterator, csak cimezni lehet vele, pl property vectort
class EachEdgeIt;
edge iterator a graf osszes elenek bejarasara
class OutEdgeIt;
edge iterator 1 pont ki eleinek bejarasara, EdgeIt-e konvertalhato
class InEdgeIt;
edge iterator 1 pont be eleinek bejarasara, EdgeIt-e konvertalhato
class SymEdgeIt;
edge iterator 1 pont be es ki eleinek bejarasara, EdgeIt-e konvertalhato

Az iteratorok ures konstruktorai invalid iteratort konstrualnak. 

template<typename ValueType> class NodeMap;
template<typename ValueType> class EdgeMap;

Graph();
default constructor
    
A kovetkezo cuccokbol kell valasztani:

NodeIt tail(const EdgeIt) const;
NodeIt head(const EdgeIt) const;

NodeIt aNode(const OutEdgeIt) const;
NodeIt aNode(const InEdgeIt) const;
NodeIt aNode(const SymEdgeIt) const;
az out, in or sym edge iterator rogzitett pontjara ad 1 NodeIt-t

NodeIt bNode(const OutEdgeIt) const;
NodeIt bNode(const InEdgeIt) const;
NodeIt bNode(const SymEdgeIt) const;
az out, in or sym edge iterator nem rogzitett pontjara ad 1 NodeIt-t

EachNodeIt first<EachNodeIt>() const;
EachEdgeIt first<EachEdgeIt>() const;
OutEdgeIt first<OutEdgeIt>(const NodeIt) const; 
InEdgeIt first<InEdgeIt>(const NodeIt) const; 
SymEdgeIt first<SymEdgeIt>(const NodeIt) const; 
EachNodeIt get<EachNodeIt>(const NodeIt) const; ??? konverzio miatt
EachEdgeIt get<EachEdgeIt>(const EdgeIt) const; ??? konverzio miatt
OutEdgeIt get<OutEdgeIt>(const NodeIt, const EdgeIt) const; ??? konverzio miatt
InEdgeIt get<InEdgeIt>(const NodeIt, const EdgeIt) const; ??? konverzio miatt
SymEdgeIt get<SymEdgeIt>(const NodeIt, const EdgeIt) const; ??? konverzio miatt

A masik lehetoseg pedig:

void getTail(NodeIt&, const EdgeIt) const;
void getHead(NodeIt&, const EdgeIt) const;

void getANode(NodeIt&, const OutEdgeIt) const;
void getANode(NodeIt&, const InEdgeIt) const;
void getANode(NodeIt&, const SymEdgeIt) const;
   
void getBNode(NodeIt&, const OutEdgeIt) const;
void getBNode(NodeIt&, const InEdgeIt) const;
void getBNode(NodeIt&, const SymEdgeIt) const;

void getFirst(EachNodeIt&) const;
void getFirst(EachEdgeIt&) const;
void getFirst(OutEdgeIt&, const NodeIt) const;
void getFirst(InEdgeIt&, const NodeIt) const;
void getFirst(SymEdgeIt&, const NodeIt) const;
void get(EachNodeIt&, const NodeIt) const; ??? konverzio miatt
void get(EachEdgeIt&, const EdgeIt) const; ??? konverzio miatt
void get(OutEdgeIt&, const NodeIt, const EdgeIt) const; ??? konverzio miatt
void get(InEdgeIt&, const NodeIt, const EdgeIt) const; ??? konverzio miatt
void get(SymEdgeIt&, const NodeIt, const EdgeIt) const; ??? konverzio miatt

Itt er veget az alternativ ize.

Pontok azonositasara de meginkabb property vectorokhoz:

int id(const NodeIt&) const;
int id(const EdgeIt&) const;

int nodeNum() const;
int edgeNum() const;

Pontok es elek hozzaadasanak metodusai:

NodeIt addNode();
EdgeIt addEdge(const NodeIt, const NodeIt);

void deleteNode(const NodeIt);
void deleteEdge(const EdgeIt);

void setTail(const NodeIt); vagy void setTail(NodeIt); nem tom
void setHead(const NodeIt); vagy void setHead(NodeIt); nem tom

Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
ezek nem a ListGraph metodusai

friend std::ostream& operator<<(std::ostream&, const NodeIt&);
friend std::ostream& operator<<(std::ostream&, const EdgeIt&);

AZ iteratorok leptetesere ket lehetoseg van, az iterator ++ operatora, a 
masik pedig 
It G.next(It) const;
const G.next(const It) const; 
It& G.setNext(It&) const; G.goNext(It&) const; G.moveNext(It&) const; mi a jobb szo?

Kerdes: A bool valid()-nak ki kell-e jelenteni magarol, hogy const??
NodeIt metodusai:
NodeIt();
bool valid() const;
ezek nem tagfuggvenyek:
friend bool operator==(const NodeIt&, const NodeIt&);
friend bool operator!=(const NodeIt&, const NodeIt&);
    
EachNodeIt metodusai:
ez publikusan szarmazik a NodeIt-bol, tehat a fentiek is.
EachNodeIt();
EachNodeIt& operator++();

EdgeIt metodusai:
EdgeIt();
bool valid() const;
ezek nem tagfvek:
friend bool operator==(const EdgeIt&, const EdgeIt&);
friend bool operator!=(const EdgeIt&, const EdgeIt&);
ujra tagfv-ek.
   
EachEdgeIt metodusai:
EdgeIt-bol szarmazik
EachEdgeIt();
EachEdgeIt& operator++();
 
OutEdgeIt metodusai:
EdgeIt-bol szarmazik
OutEdgeIt();
OutEdgeIt& operator++();
 
InEdgeIt metodusai: 
EdgeIt-bol szarmazik
InEdgeIt();
InEdgeIt& operator++();

SymEdgeIt metodusai:
EdgeIt-bol szarmazik
SymEdgeIt();
SymEdgeIt& operator++();
                
Ami itt kovetkezik az mar nem lenyeg, sot valtozni fog.

Node propery array-okrol:

template <typename ValueType>
class NodeMap; 

metodusok:

NodeMap(const Graph&);
NodeMap(const Graph&, const ValueType);
void set(Graph::NodeIt, const ValueType);
//void put(Graph::NodeIt, const ValueType);
ValueType get(Graph::NodeIt) const;

Ugyanez edge_property_array-okkal

template <typename ValueType>
class EdgeMap;

EdgeMap(const Graph&);
EdgeMap(const Graph&, const ValueType);
void set(Graph::EdgeIt, const ValueType);
//void put(Graph::EdgeIt, const ValueType);
ValueType get(Graph::EdgeIt) const;

marci@cs.elte.hu