alpar@1: // -*-mode: c++; -*- alpar@1: #ifndef __GRAPH_H_ alpar@1: #define __GRAPH_H_ alpar@1: alpar@1: //inline void *operator new(size_t s, void *p) { return p; } alpar@1: #include alpar@6: #include alpar@1: alpar@1: namespace NEGRO alpar@1: { alpar@1: using namespace std; alpar@1: alpar@1: #include "oldgraph.h" alpar@1: alpar@1: template class Graph : protected OldGraph alpar@1: { alpar@1: public: alpar@1: typedef E EdgeType; alpar@1: typedef N NodeType; alpar@1: alpar@70: class EdgeIt alpar@1: { alpar@1: public: alpar@1: NEGRO::EdgePoint e; alpar@70: bool valid() { return e; } alpar@1: }; alpar@1: alpar@70: class InEdgeIt : public EdgeIt {}; alpar@70: class OutEdgeIt : public EdgeIt {}; alpar@70: class BiEdgeIt : public EdgeIt {}; alpar@70: class SymEdgeIt : public EdgeIt {}; alpar@1: alpar@70: typedef int NodeIt; alpar@70: alpar@70: typedef NodeIt EachNodeIt; alpar@1: alpar@1: class NodeIterator; alpar@1: alpar@1: class EdgeIterator; alpar@1: class InEdgeIterator; alpar@1: class OutEdgeIterator; alpar@1: class BiEdgeIterator; alpar@1: class SymEdgeIterator; alpar@1: class AllEdgeIterator; alpar@1: alpar@6: class FirstAnythingTypeNode; //Required by the unified First() function. alpar@1: alpar@1: friend class NodeIterator; alpar@1: friend class EdgeIterator; alpar@1: friend class InEdgeIterator; alpar@1: friend class OutEdgeIterator; alpar@1: friend class BiEdgeIterator; alpar@1: friend class SymEdgeIterator; alpar@70: friend class EachEdgeIterator; alpar@1: alpar@1: class NodeIterator alpar@1: { alpar@1: Graph *G; //operator*() miatt kell!!! alpar@1: int n; //nem kellene, ha itt mutato lenne!! alpar@1: public: alpar@1: alpar@1: NodeIterator() {;} alpar@3: NodeIterator(Graph &Gr)//'const Graph &G' would be wrong. alpar@3: {G=&Gr;n=Gr.OldGraph::FirstNode();} alpar@1: NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} alpar@1: alpar@70: NodeIterator &goNext() { n=G->NextNode(n); return *this;} alpar@70: NodeIterator next() const { return NodeIterator(*this).goNext();} alpar@70: NodeIterator &operator++() { return goNext();} alpar@1: NodeIterator operator++(int) alpar@70: {NodeIterator tmp(*this); goNext(); return tmp;} alpar@70: bool valid() { return n!=INVALID; } alpar@1: alpar@1: N &operator*() const { return G->Data(n); } alpar@1: N *operator->() const { return &G->Data(n); } alpar@1: alpar@1: bool operator==(const NodeIterator &i) const {return n==i.n;} alpar@1: bool operator!=(const NodeIterator &i) const {return n!=i.n;} alpar@1: alpar@70: int index() const { return n; } //If the nodes are indexable alpar@1: friend class Graph; alpar@1: friend class EdgeIterator; alpar@1: friend class InEdgeIterator; alpar@1: friend class OutEdgeIterator; alpar@1: friend class BiEdgeIterator; alpar@1: friend class SymEdgeIterator; alpar@70: friend class EachEdgeIterator; alpar@1: friend class FirstAnythingTypeNode; alpar@1: alpar@1: //Nem kellene egy: alpar@1: // static NodeIterator &GetInvalid(); ? alpar@1: }; alpar@1: alpar@1: class EdgeIterator alpar@1: { alpar@1: alpar@1: Graph *G; //Itt baj van!!!!! operator*() miatt kell! alpar@1: //Ez csak kicsit baj, de: alpar@1: // Meg a From() es To() miatt!!!!!!!!!! alpar@1: alpar@70: NEGRO::EdgeIt e; alpar@1: alpar@1: public: alpar@1: EdgeIterator() {;} //Kell inicializalni? (Nem) alpar@1: EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;} alpar@1: alpar@1: // Lehet, hogy ez a ketto nem kell!!! alpar@1: alpar@986: NodeIterator source() const {NodeIterator i;i.G=G;i.n=e->From();return i;} alpar@986: NodeIterator target() const {NodeIterator i;i.G=G;i.n=e->To();return i;} alpar@70: NodeIterator opposite(const NodeIterator &n) const alpar@986: {return n==source()?target():source();} alpar@1: alpar@70: bool valid() {return e;} alpar@1: E &operator*() const { return G->Data(e); } alpar@1: E *operator->() const { return &G->Data(e); } alpar@1: alpar@1: //operator const OutEdgeIterator (); alpar@1: //operator const InEdgeIterator (); alpar@1: //operator const BiEdgeIterator (); alpar@1: //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal alpar@1: alpar@1: bool operator==(const EdgeIterator &i) const {return e==i.e;} alpar@1: bool operator!=(const EdgeIterator &i) const {return e!=i.e;} alpar@2: alpar@70: int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;} alpar@2: //If the edges are indexable alpar@2: alpar@1: friend class Graph; alpar@1: friend class InEdgeIterator; alpar@1: friend class OutEdgeIterator; alpar@1: friend class BiEdgeIterator; alpar@1: friend class SymEdgeIterator; alpar@70: friend class EachEdgeIterator; alpar@1: }; alpar@1: alpar@1: class BiEdgeIterator : public EdgeIterator alpar@1: { alpar@1: public: alpar@70: BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;} alpar@70: BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;} alpar@70: BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();} alpar@70: BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();} alpar@1: alpar@1: operator InEdgeIterator () alpar@1: {InEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator OutEdgeIterator () alpar@1: {OutEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: //operator const SymEdgeIterator () alpar@1: alpar@1: friend class Graph; alpar@1: }; alpar@1: alpar@1: class InEdgeIterator : public EdgeIterator alpar@1: //Ne a BiEdgeIterator-bol szarmazzon? alpar@1: { alpar@1: public: alpar@3: InEdgeIterator() {} alpar@70: InEdgeIterator(Graph &Gr,const NodeIterator &n) alpar@3: { G=&Gr; e=Gr.OldGraph::FirstIn(n.n);} alpar@3: alpar@1: InEdgeIterator &GoNext() { e=e->NextIn(); return *this;} alpar@1: InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();} alpar@1: InEdgeIterator &operator++() { return GoNext();} alpar@1: InEdgeIterator operator++(int) alpar@1: {InEdgeIterator tmp(*this); GoNext(); return tmp;} alpar@1: alpar@1: operator const OutEdgeIterator () alpar@1: {OutEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const BiEdgeIterator () alpar@1: {EdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: // operator const SymEdgeIterator (); alpar@1: alpar@1: NodeIterator Anode() const {return To();} alpar@1: NodeIterator Bnode() const {return From();} alpar@1: alpar@1: friend class Graph; alpar@1: }; alpar@1: alpar@1: class OutEdgeIterator : public EdgeIterator alpar@1: { alpar@1: public: alpar@3: OutEdgeIterator() {} alpar@3: OutEdgeIterator(Graph &Gr,const NodeIterator &n) alpar@3: { G=&Gr; e=Gr.OldGraph::FirstOut(n.n);} alpar@3: alpar@70: OutEdgeIterator &goNext() { e=e->NextOut(); return *this;} alpar@70: OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();} alpar@70: OutEdgeIterator &operator++() { return goNext();} alpar@1: OutEdgeIterator operator++(int) alpar@70: {OutEdgeIterator tmp(*this); goNext(); return tmp;} alpar@1: alpar@986: NodeIterator aNode() const {return source();} alpar@986: NodeIterator bNode() const {return target();} alpar@1: alpar@1: operator const InEdgeIterator () alpar@1: {InEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const BiEdgeIterator () alpar@1: {BiEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: //operator const SymEdgeIterator(); alpar@1: alpar@1: friend class Graph; alpar@1: }; alpar@1: alpar@1: class SymEdgeIterator : public EdgeIterator alpar@1: { alpar@1: NodeIterator n; // Itt ketszer van a G alpar@1: alpar@1: public: alpar@3: SymEdgeIterator() {} alpar@70: SymEdgeIterator(Graph &Gr,const NodeIterator &nn) alpar@70: { G=&Gr; n=nn; e=Gr.OldGraph::FirstEdge(nn.n); } alpar@3: alpar@70: SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;} alpar@70: SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();} alpar@70: SymEdgeIterator &operator++() { return goNext();} alpar@1: SymEdgeIterator operator++(int) alpar@70: {SymEdgeIterator tmp(*this); goNext(); return tmp;} alpar@1: alpar@70: NodeIterator aNode() const {return n;} alpar@986: NodeIterator bNode() const {return n.n==source().n?target():source();} alpar@1: alpar@1: operator const InEdgeIterator () alpar@1: {InEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const OutEdgeIterator () alpar@1: {OutEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const BiEdgeIterator () alpar@1: {BiEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: alpar@1: friend class Graph; alpar@1: }; alpar@1: alpar@70: class EachEdgeIterator : public EdgeIterator alpar@1: { alpar@1: NodeIterator n; // Itt ketszer van a G alpar@1: alpar@1: public: alpar@70: EachEdgeIterator() {} alpar@70: EachEdgeIterator(Graph &Gr) : n(Gr) alpar@3: { alpar@70: e=n.valid()?Gr.OldGraph::FirstOut(n.n):NULL; alpar@3: } alpar@3: alpar@70: EachEdgeIterator &goNext() alpar@1: { alpar@1: e=e->NextOut(); alpar@70: if(!e && (++n).valid()) e=G->OldGraph::FirstOut(n.n); alpar@1: return *this; alpar@1: } alpar@70: EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();} alpar@70: EachEdgeIterator &operator++() { return goNext();} alpar@70: EachEdgeIterator operator++(int) alpar@70: {EachEdgeIterator tmp(*this); goNext(); return tmp;} alpar@1: alpar@1: alpar@70: NodeIterator aNode() const {return n;} alpar@986: NodeIterator bNode() const {return n.n==source().n?target():source();} alpar@1: alpar@70: operator const EdgeIterator () alpar@70: {EdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const InEdgeIterator () alpar@1: {InEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const OutEdgeIterator () alpar@1: {OutEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: operator const BiEdgeIterator () alpar@1: {BiEdgeIterator i; i.G=G;i.e=e;return i;} alpar@1: alpar@1: friend class Graph; alpar@1: }; alpar@1: alpar@1: typedef NodeIterator DeletingNodeIterator; alpar@1: typedef EdgeIterator DeletingEdgeIterator; alpar@1: typedef BiEdgeIterator DeletingBiEdgeIterator; alpar@1: typedef OutEdgeIterator DeletingOutEdgeIterator; alpar@1: typedef InEdgeIterator DeletingInEdgeIterator; alpar@1: typedef SymEdgeIterator DeletingSymEdgeIterator; alpar@1: alpar@70: const NodeIterator firstNode() alpar@1: { alpar@1: NodeIterator i; alpar@1: i.G=this;i.n=OldGraph::FirstNode(); alpar@1: return i; alpar@1: } alpar@1: alpar@70: void getFirst(NodeIt &p) { p=OldGraph::FirstNode(); } alpar@1: alpar@70: void getFirst(InEdgeIt &p,const NodeIt &n) alpar@1: { p=OldGraph::FirstIn(n); } alpar@70: void getFirst(OutEdgeIt &p,const NodeIt &n) alpar@1: { p=OldGraph::FirstOut(n); } alpar@70: void getFirst(SymEdgeIt &p,const NodeIt &n) alpar@1: { p=OldGraph::FirstEdge(n); } alpar@70: void getFirst(EdgeIt &p) //Vegigmegy mindenen alpar@70: { p.e=nodeNum()?OldGraph::FirstOut(OldGraph::FirstNode()):NULL;} alpar@1: alpar@70: void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph::FirstNode();} alpar@1: alpar@70: void getFirst(InEdgeIterator &i,const NodeIterator &n) alpar@1: { i.G=this;i.e=OldGraph::FirstIn(n.n); } alpar@70: void getFirst(OutEdgeIterator &i,const NodeIterator &n) alpar@1: { i.G=this;i.e=OldGraph::FirstOut(n.n); } alpar@70: void getFirst(SymEdgeIterator &i,const NodeIterator &n) alpar@70: { i.G=this;i.e=OldGraph::FirstEdge(n.n); } alpar@70: void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen alpar@1: { alpar@1: i.G=this; alpar@70: getFirst(i.n); alpar@1: i.e=OldGraph::NodeNum()?OldGraph::FirstOut(i.n.n):NULL; alpar@1: } alpar@1: alpar@1: alpar@1: alpar@1: //Vagy beginnode()? alpar@70: const DeletingEdgeIterator firstOut(const NodeIterator &n) alpar@1: { alpar@1: EdgeIterator i; alpar@1: i.G=n.G;i.edge=n.G->OldGraph::FirstOut(n.n); alpar@1: return i; alpar@1: } alpar@70: const DeletingEdgeIterator firstIn(const NodeIterator &n) alpar@1: { alpar@1: EdgeIterator i; alpar@1: i.G=n.G;i.edge=n.G->OldGraph::FirstIn(n.n); alpar@1: return i; alpar@1: } alpar@70: const DeletingSymEdgeIterator firstSym(const NodeIterator &n) alpar@1: { alpar@1: EdgeIterator i; alpar@1: i.G=n.G;i.n=n.n; alpar@1: i.edge=n.G->OldGraph::FirstEdge(n.n); alpar@1: return i; alpar@1: } alpar@1: alpar@1: // class FirstAnythingType; alpar@1: // friend class FirstAnythingType; alpar@1: alpar@1: class FirstAnythingTypeNode alpar@1: { alpar@1: NodeIterator n; alpar@1: public: alpar@1: FirstAnythingTypeNode(NodeIterator i) : n(i) {} alpar@1: alpar@1: operator const InEdgeIterator () const alpar@1: {InEdgeIterator i; n.G->GetFirst(i,n);return i;} alpar@1: operator const OutEdgeIterator () const alpar@1: {OutEdgeIterator i; n.G->GetFirst(i,n);return i;} alpar@1: operator const SymEdgeIterator () const alpar@1: {SymEdgeIterator i; n.G->GetFirst(i,n);return i;} alpar@1: alpar@70: operator const InEdgeIt () const alpar@70: {InEdgeIt i; n.G->GetFirst(i,n);return i;} alpar@70: operator const OutEdgeIt () const alpar@70: {OutEdgeIt i; n.G->GetFirst(i,n);return i;} alpar@70: operator const SymEdgeIt () const alpar@70: {SymEdgeIt i; n.G->GetFirst(i,n);return i;} alpar@1: }; alpar@1: alpar@1: class FirstAnythingType alpar@1: { alpar@1: Graph *G; alpar@1: public: alpar@1: FirstAnythingType(Graph *gg) : G(gg) {} alpar@1: alpar@70: operator const EachEdgeIterator () const alpar@70: {EachEdgeIterator i; G->GetFirst(i);return i;} alpar@70: operator const EdgeIt () const alpar@70: {EdgeIt i; G->GetFirst(i);return i;} alpar@1: operator const NodeIterator () const alpar@1: {NodeIterator i; G->GetFirst(i);return i;} alpar@70: operator const NodeIt () const alpar@70: {NodeIt i; G->GetFirst(i);return i;} alpar@1: } _FST; alpar@1: alpar@1: // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} alpar@70: FirstAnythingTypeNode first(NodeIterator &i) alpar@1: {FirstAnythingTypeNode t(i); return t;} alpar@70: const FirstAnythingType &first() {return _FST;} alpar@1: alpar@1: // LastNode() vagy endnode() stb. Nem kell? alpar@1: alpar@70: DeletingNodeIterator addNode() alpar@1: { alpar@1: DeletingNodeIterator i; alpar@1: i.G=this; i.n=OldGraph::AddNode(); alpar@1: return i; alpar@1: } alpar@1: DeletingEdgeIterator alpar@70: addEdge(const NodeIterator from,const NodeIterator to) alpar@1: { alpar@1: DeletingEdgeIterator i; alpar@1: i.G=this;i.e=OldGraph::AddEdge(from.n,to.n);return i; alpar@1: } alpar@1: alpar@1: void Delete(DeletingNodeIterator n) {n.G->OldGraph::Delete(n.n);} alpar@1: void Delete(DeletingEdgeIterator e) {e.G->OldGraph::Delete(e.e);} alpar@1: alpar@70: int nodeNum() { OldGraph::NodeNum(); } alpar@70: void clean() { OldGraph::Clean(); } alpar@1: alpar@1: Graph() : _FST(this) {} alpar@6: alpar@6: // MAPS: alpar@6: template class NodeMap alpar@6: { alpar@6: Graph *G; alpar@6: vector map; alpar@6: alpar@6: public: alpar@6: typedef T value_type; alpar@70: void put(const NodeIterator i, const T &t) {map[i.Index()]=t;} alpar@70: T get(const NodeIterator i) const {return map[i.Index()];} alpar@8: T operator[](NodeIterator i) {return map[i.Index()];} alpar@6: alpar@8: void update() { map.resize(G->MaxNode());} alpar@6: alpar@8: NodeMap() {} alpar@70: void setG(Graph &Gr) { G=&Gr; update();} alpar@6: }; alpar@6: alpar@6: template class EdgeMap alpar@6: { alpar@6: Graph *G; alpar@6: vector map; alpar@6: alpar@6: public: alpar@6: typedef T value_type; alpar@70: void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;} alpar@70: T get(const EdgeIterator i) const {return map[i.Index()];} alpar@70: T &operator[](EdgeIterator i) {return map[i.Index()];} alpar@6: alpar@6: void update() alpar@8: { map.resize(G->MaxEdge());} alpar@6: alpar@8: EdgeMap() {} alpar@70: void setG(Graph &Gr) alpar@8: { G=&Gr ;update();} alpar@6: alpar@6: }; alpar@6: alpar@8: alpar@70: int maxNode() { return OldGraph::MaxNode();} alpar@70: int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;} alpar@8: alpar@1: }; alpar@1: alpar@70: template //G is a graph-type alpar@70: class Path alpar@70: { alpar@70: public: alpar@70: typedef G Graph; alpar@70: typedef typename G::NodeIterator NodeIterator; alpar@70: typedef typename G::EdgeIterator EdgeIterator; alpar@70: typedef typename G::SymEdgeIterator SymEdgeIterator; alpar@70: alpar@70: private: alpar@70: std::vector path; alpar@70: std::vector reversed; alpar@70: alpar@70: public: alpar@70: void setLength(int n) { path.resize(n);reversed.resize(n);} alpar@70: int getLength() { return path.size(); } alpar@70: EdgeIterator &operator[](int n) {return path[n];} alpar@70: NodeIterator GetNode(int n) // What about path of length 1? alpar@70: { alpar@70: return n? alpar@986: reversed[n-1]?path[n-1].source():path[n-1].target(): alpar@986: reversed[0]?path[0].target():path[0].source(); alpar@70: } alpar@70: void setRevert(int n,bool r=true) {reversed[n]=r;} alpar@70: void setEdge(int n,SymEdgeIterator i) alpar@70: { alpar@70: path[n]=i; alpar@986: reversed[n] = i.target()==i.aNode(); alpar@70: } alpar@70: void setEdge(int n,EdgeIterator i,bool r) alpar@70: { alpar@70: path[n]=i; alpar@70: reversed[n] = r; alpar@70: } alpar@70: alpar@986: NodeIterator source() { return getNode(0); } alpar@986: NodeIterator target() { return getNode(getLength()); } alpar@70: }; alpar@70: alpar@1: /* Ez itt a fiam kommentje: alpar@1: