由于上一次的graph adt结构没有 主索引表allArc,allNode 和 VNode 结构内的inArc,outArc 的相互索引能力,效率比较低.
这一次专门细化了基本结构(VNode,VArc)的元操作,不导致任何功能上的冲突.
写代码期间居然有心情写注释,说明写库如果先自上而下的设计,再自下而上的实现,还是能够增加设计级效率.


0  为了实现相互索引的优化能力,图结构的每一个node和arc都有key和tag两种索引标记,key是面向graph的使用者设计的,tag是面向内在结构设计的,这样,同时让使用者用自由值索引,又保持内在的高效索引.

1 只加了两处测试代码,其他测试代码之后加上去(主要是要考虑使用者会不会进行意想不到的图操作).

2 对于结点数等计数信息直接用引用变量锁定vector的对象,这样,整个代码里面找不到任何关于长度的计数信息(如++,--),完全和vector的n值(长度)同步.

/**//*  graph.h :base::adt::graph */

#ifndef GRAPH__

#define GRAPH__

#include "base.h"
#include "vector.h"


namespace adt
{
    using adt::vector;
    template<typename VTypeN,typename VTypeE>
    class graph : public base::adt
    {
    public:
        struct VArc;
        struct VNode;
        struct VArc
        {
            VNode* begin;
            VNode* end;

            int *tag_begin;
            int *tag_end;
            VTypeE weight;

            int tag;/**//*internal index tag*/
            int key;/**//*external index tag*/

            VArc()
            {
                tag=0;
                key=0;
            }
            VArc(VNode *_begin,VNode * _end,int _key,int _tag,VTypeE _w)
            {
                begin=_begin;
                end=_end;
                weight=_w;
                tag=_tag;
                key=_key;
                tag_begin=&begin->tag;
                tag_end=&end->tag;
            }
            ~VArc()
            {
                begin=0;
                end=0;
                tag=0;
                key=0;
            }
            /**//*copy to _arc only by data not adr*/
            void copyTo(VArc * _arc)
            {
                _arc->weight=weight;
                _arc->tag=tag;
                _arc->key=key;
            }
            void setKey(int _key)
            {
                key=_key;
            }
            void setTag(int _tag)
            {
                tag=_tag;
            }
            void setWeight(VTypeE _w)
            {
                weight=_w;
            }
            void setBegin(VNode* _begin)
            {
                begin=_begin;
                tag_begin=&begin->tag;
                
            }
            void setEnd(VNode* _end)
            {
                end=_end;
                tag_end=&end->tag;
            }
        };
        struct VNode
        {
            vector<VArc*> inArc;
            vector<VArc*> outArc;
            int &inNum;
            int &outNum;

            VTypeN weight;

            int tag;/**//*internal index tag*/
            int key;/**//*external index tag*/

            int status;/**//*node status*/

            /**//*copy to _arc only by data not adr*/
            void copyTo(VNode * _node)
            {
                _node->weight=weight;
                _node->tag=tag;
                _node->key=key;
                _node->status=status;

            }
            VNode():/**//*build up ref*/inNum(inArc.n),outNum(outArc.n)
            {
                status=0;
                tag=0;
                key=0;
            }
            VNode(int _key,int _tag,VTypeN _w,int _status):/**//*build up ref*/inNum(inArc.n),outNum(outArc.n)
            {
                weight=_w;
                status=_status;
                tag=_tag;
                key=_key;
            }
            ~VNode()
            {
                tag=0;
                key=0;
                status=0;
            }
            /**//*  set key  */
            void setKey(int _key)
            {
                key=_key;
            }
            /**//*  set tag */
            void setTag(int _tag)
            {
                tag=_tag;
            }
            /**//*  set weight */
            int setWeight(VTypeN _w)
            {
                weight=_w;
                return 1;
            }
            /**//*  set status */
            void setStatus(int _status)
            {
                status=_status;
            }

            /**//* add inArc */
            int addIn(VArc *_inArc )
            {
                if(!_inArc)
                    return 0;
                inArc.push(_inArc);
                //++inNum;
                return 1;
            }
            /**//* and outArc */
            int addOut(VArc *_outArc )
            {
                if(!_outArc)
                    return 0;
                outArc.push(_outArc);
                //++outNum;
                return 1;
            }

            /**//* remove inArc by weight */
            int removeInWeight(VTypeE _w)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->weight==_w)
                    {
                        inArc.remove(i);
                        //--inNum;
                        --i;
                    }
                }
                return 1;
            }
            /**//* remove outArc by weight */
            int removeOutWeight(VTypeE _w)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->weight==_w)
                    {
                        outArc.remove(i);
                        //--outNum;
                        --i;
                    }
                }
                return 1;
            }
            /**//* remove inArc by tag */
            int removeInTag(int _tag)
            {
                for(int i=0;i!=inArc.n;i++)
                {
                    if(inArc[i]->tag==_tag)
                    {
                        inArc.remove(i);
                        //--inNum;
                        return 1;
                    }
                }
                return 0;
            }
            /**//* remove outArc by tag */
            int removeOutTag(int _tag)
            {
                for(int i=0;i!=outArc.n;i++)
                {
                    if(outArc[i]->tag==_tag)
                    {
                        outArc.remove(i);
                        //--outNum;
                        return 1;
                    }
                }
                return 0;
            }
            /**//* remove inArc by key */
            int removeInKey(int _key)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->key==_key)
                    {
                        inArc.remove(i);
                        //--inNum;
                        return 1;
                    }
                }
                return 0;
            }
            /**//* remove outArc by key */
            int removeOutKey(int _key)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->key==_key)
                    {
                        outArc.remove(i);
                        //--outNum;
                        return 1;
                    }
                }
                return 0;
            }
            /**//* search inArc by weight */
            VArc* findInWeight(VTypeE _w)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->weight==_w)
                    {
                        return inArc_[i];
                    }
                }
                return 0;

            }
            /**//* search outArc by weight */
            VArc* findOutWeight(VTypeE _w)
            {
                for(int i=0;i!=outArc.n;i++)
                {
                    if(outArc[i]->weight==_w)
                    {
                        return outArc[i];
                    }
                }
                return 0;

            }
            /**//* search inArc by tag */
            VArc* findInTag(int _t)
            {
                for(int i=0;i!=inArc.n;i++)
                {
                    if(inArc[i]->tag==_t)
                    {
                        return inArc[i];
                    }
                }
                return 0;

            }
            /**//* search outArc by tag */
            VArc* findOutTag(int _t)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->tag==_t)
                    {
                        return outArc_[i];
                    }
                }
                return 0;

            }
            /**//* search inArc by key */
            VArc* findInKey(int _key)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->key==_key)
                    {
                        return inArc_[i];
                    }
                }
                return 0;

            }
            /**//* search outArc by key */
            VArc* findOutKey(int _key)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->key==_key)
                    {
                        return outArc_[i];
                    }
                }
                return 0;

            }
        };
        vector<VNode*> allNode;
        vector<VArc*>  allArc;
        int& nodeNum;
        int& arcNum; 
        graph():/**//*build up ref*/nodeNum(allNode.n),arcNum(allArc.n)
        {

        }
        graph(graph & obj):/**//*build up ref*/nodeNum(allNode.n),arcNum(allArc.n)
        {
            obj.copyTo(*this);
        }
        int addNode(int _key,VTypeN _w,int _status)
        {
            

            if(findNodeTag(_key)!=-1)
            {
                
#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::addNode Function.")
#endif
                return 0;

            }

            VNode* _node=new VNode;
            /**//*init data*/
            _node->setKey(_key);
            _node->setWeight(_w);
            _node->setStatus(_status);
            _node->setTag(nodeNum);/**//*index reciprocally beginning with 0 */
            /**//*push in index list*/
            allNode.push(_node);
            return 1;
        }
        int setNode(int _key,VTypeN _w,int _status)
        {
            int _tag;

            if((_tag=findNodeTag(_key))==-1)
            {
                
#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::setNode Function.")
#endif
                return 0;

            }

            VNode* _node=allNode[_tag];
            /**//*init data*/
            _node->setWeight(_w);
            _node->setStatus(_status);
            return 1;
        }
        /**//* switch key to tag */
        int findNodeTag(int _key)
        {
            for(int i=0;i!=allNode.n;i++)
            {
                if(allNode[i]->key==_key)
                {
                    return allNode[i]->tag;
                }
            }
            return -1;
        }
        /**//* switch key to tag */
        int findArcTag(int _key)
        {
            for(int i=0;i!=allArc.n;i++)
            {
                if(allArc[i]->key==_key)
                {
                    return allArc[i]->tag;
                }
            }
            return -1;
        }
        /**//* find node by key */
        int findNode(int _key)
        {
            for(int i=0;i!=allNode.n;i++)
            {
                if(allNode[i]->key==_key)
                {
                    return 1;
                }
            }
            return 0;
        }
        /**//* find arc by key */
        int findArc(int _key)
        {
            for(int i=0;i!=allArc.n;i++)
            {
                if(allArc[i]->key==_key)
                {
                    return 1;
                }
            }
            return 0;
        }
        int isGo(int _key,VTypeE _w,int &_next_key)
        {
            int _tag = findNodeTag(_key);

            if(_tag>=nodeNum||_tag==-1)
            {
#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::isGo function.")
#endif
                return 0;
            }
                

            VNode * _node = allNode[_tag];
            VArc* _arc = _node->findOutWeight(_w);
            if(!_arc)
                return 0;
            _next_key = _arc->end->key;
            return 1;
        }
        int getStatus(int _key)
        {
            int _tag = findNodeTag(_key);

            return allNode[_tag]->status;
        }
        /**//* add arc by begin and end 's key */
        void addArc(int _k_begin,int _k_end,int _key,VTypeE _w)
        {
            if(findArcTag(_key)!=-1)
            {
                
#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::addArc function.")
#endif
                return;

            }
            VArc* _arc=new VArc;
            /**//* switch key to tag,get begin's and end's adr*/
            int _tag_begin = findNodeTag(_k_begin);
            int _tag_end   = findNodeTag(_k_end);
            VNode* _begin=allNode[_tag_begin];
            VNode* _end  =allNode[_tag_end];
            /**//*init data*/
            _arc->setBegin(_begin);
            _arc->setEnd(_end);
            _arc->setKey(_key);
            _arc->setWeight(_w);
            /**//*index reciprocally beginning with zero */
            _arc->setTag(arcNum);
            /**//*building begin-end link.*/
            _begin->addOut(_arc);
            _end->addIn(_arc);
            /**//*push in index list*/
            allArc.push(_arc);

        }
        int setArc(int _key,VTypeE _w)
        {
            int _tag;
            if((_tag=findArcTag(_key))==-1)
            {
                
#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::setArc function.")
#endif
                return 0;

            }
            VArc* _arc=allArc[_tag];
    
            VNode* _begin=allNode[_arc->begin->tag];
            VNode* _end  =allNode[_arc->end->tag];
            /**//*init data*/
            _arc->setBegin(_begin);
            _arc->setEnd(_end);
            _arc->setWeight(_w);

        }
        /**//* copy self to graph-obj */
        int copyTo(graph & _obj)
        {
            VNode *_node;
            VArc *_arc;
            
            for(int i=0;i!=nodeNum;i++)
            {
                _node=allNode[i];
                _obj.allNode.push(new VNode(_node->key,_node->tag,_node->weight,_node->status));

            }
            for(int i=0;i!=arcNum;i++)
            {
                _arc=allArc[i];
                _obj.addArc(_arc->begin->key,_arc->end->key,_arc->key,_arc->weight);
            }
            return 1;
        }
        int copyFrom(graph & _obj)
        {
            _obj.copyTo(*this);
            return 1;
        }
        /**//* get value from rightObj */
        void operator = (graph& _rObj)
        {
            copyFrom(_rObj);
        }
        /**//* remove arc by tag */
        int removeArcTag(int _tag)
        {

            VArc* _arc=allArc[_tag];
            _arc->begin->removeOutTag(_tag);
            _arc->end->removeInTag(_tag);
            allArc.remove(_tag);
            for(int i=_tag;i!=arcNum;i++)
                --allArc[i]->tag;

            return 1;
        }
        /**//* remove arc by key */
        int removeArcKey(int _key)
        {
            VArc* _arc;

            /**//* search by key */

            for(int i=0;i!=arcNum;i++)
            {
                if(allArc[i]->key==_key)
                {
                    _arc=allArc[i];
                    removeArcTag(_arc->tag);
                    return 1;
                }
            }

            return 0;
        }
        /**//* remove node by tag*/
        int removeNodeTag(int _tag)
        {
            
            VNode* _node=allNode[_tag];
            
            /**//* remove all inArc */
            for(;0!=_node->inNum;)
            {
                            
                removeArcTag(_node->inArc[0]->tag);
                //_node->inArc.remove(0);
            }
            /**//* remove all outArc */
            for(;0!=_node->outNum;)
            {
                
                removeArcTag(_node->outArc[0]->tag);
                //cout<<_node->outNum;
                //_node->outArc.remove(0);
            }
            /**//* remove itself*/
            allNode.remove(_tag);
            for(int i=_tag;i!=arcNum;i++)
                --allArc[i]->tag;
            return 1;
        }
        /**//* remove node by key*/
        int removeNodeKey(int _key)
        {

            VNode* _node;
            /**//* search by key */
            
            for(int i=0;i!=nodeNum;i++)
            {
                if(allNode[i]->key==_key)
                {
                    _node=allNode[i];
                    
                    removeNodeTag(_node->tag);
                    return 1;
                }
            }
            
            return 0;
        }
        int free()
        {


            for(;0!=nodeNum;)
            {
                delete allNode.pop();

            }
            for(;0!=arcNum;)
            {
                
                delete allArc.pop();
            }

            return 1;
        }
        ~graph()
        {
            
            free();
            
        }

    };
};





#endif

关于匹配的一个case:

主要测试增加删除结点并且测试key,weight是否对应功能,会否出现崩溃.

不过还好目前没有任何输入会引起崩溃.

多次变化增加删除结点.

实现了对一个dfa  的匹配,一开始能匹配/(at|ro)(om)/,当第一次匹配成功后继续匹配时删除一条'o'边,导致r到m的边无法达到,匹配自动变成/atom/.

当第二次匹配成功(对 /atom/ 的匹配),增加回原来的'o'边,使匹配自动回到/(at|ro)(om)/,直到输入流都匹配为结束

void test_graph()
{

    using adt::graph;

    graph<int,char> g,g2;

    g.addNode(1,1,-1);
    g.addNode(2,1,0);
    g.addNode(3,1,0);
    g.addNode(4,1,0);
    g.addNode(5,1,0);
    g.addNode(6,1,1);


    g.addArc(1,2,1,'a');
    g.addArc(2,4,2,'t');
    g.addArc(4,5,3,'o');
    g.addArc(5,6,4,'m');
    g.addArc(1,3,5,'r');
    g.addArc(3,4,6,'o');

    g2=g;




    char buf[200]={0},get;
    int init=1,key=init,tag,_i=0,len,select=0;
    os::control reader;
    
    do
    {
    reader.read(buf,len);
    }while(reader.size(buf)==0);
    while(1){
        char list[100]={0};
        int i=0;
        key=init;
        while(1)
        {
            if(g2.getStatus(key)==1)
            {
                break;
            }
            if(_i==len)
                break;
            if(g2.isGo(key,buf[_i],key))
            {
                if(i==0)
                    tag=_i+1;
                list[i]=buf[_i];
                ++i;
                ++_i;
            }else
            {
                
                if(i!=0)
                {
                    _i=tag;
                    i=0;
                    key=init;
                }else
                {
                    i=0;
                    key=init;
                    ++_i;
                }


            }


        }
        if(g2.getStatus(key)==1)
        {
            if(select==0)
            {
                g2.removeArcKey(6);
                cout<<"your input(\""<<list<<"\") matches the dfa(regex:/(at|ro)(om)/)."<<endl;
                cout<<"the dfa switch to another dfa(regex:/atom/)"<<endl;
                
            }else if(select==1)
            {
                g2.addArc(3,4,6,'o');
                cout<<"your input(\""<<list<<"\") matches the dfa(regex:/atom/)."<<endl;
                cout<<"the dfa switch to another dfa(regex:/(at|ro)(om)/)"<<endl;
                
            }
            select = (select+1)%2;
        }
        cout<<_i<<":"<<len<<endl;
        if(_i==len)break;
        getch();
    }

}

Input:

your atom is in my room,atomic things..room

Output:

your input("atom") matches the dfa(regex:/(at|ro)(om)/).
the dfa switch to another dfa(regex:/atom/)
9:50
your input("atom") matches the dfa(regex:/atom/).
the dfa switch to another dfa(regex:/(at|ro)(om)/)
28:50
your input("room") matches the dfa(regex:/(at|ro)(om)/).
the dfa switch to another dfa(regex:/atom/)
46:50
50:50
请按任意键继续. . .