how to implement lexbfs to generate a peo

Postby zghenry on Wed, Jul 23, 2008 06:15
if i change the lexbfs2 to mcs this is a correct code for 1015.however it does not work for lexbfs2.
by the book there are two ways of rendering peo one is mcs(max cardinality set) the other is lexbfs (lexicographic broad first search)
but I can not get code accepted when I wrote lexbfs.This problem has been puzzling me for two month any one can give some suggestion?

Code: Select all
    #pragma warning(disable: 4786)
    #include "stdafx.h"
    //#include <stdio.h>
    #include <list>
    using namespace std;
    typedef list<int> listinttype;
    listinttype connectgraph[2001];
    bool connectarray[2001][2001];
    int sortedorder[2001];
    /*********************************************
              lexbfs2
    *********************************************/

    inline void lexbfs2(int numofvertex)
    {
       int visited[2001];
       list<listinttype> Qlist;
       list<int> bucket;
       list<int> flaglist;
       list<int>::iterator Qiter;
       list<int>::iterator flagiter;
       list<int>::iterator tempflagl;
       list<int>::iterator flagl[2001];
       list<int>::iterator vl[2001];
       list<listinttype>::iterator vlayer[2001];
       int i;

       for(i=1;i<=numofvertex;i++)
          visited[i]=0;
       
        for(i=1;i<=numofvertex;i++)
          bucket.push_front(i);
       
       Qlist.push_back(bucket);
       flaglist.push_back(0);
       
        Qiter=Qlist.begin()->end();
       Qiter--;
       for(i=1;i<=numofvertex;i++)
       {
          vl[i]=Qiter;
          vlayer[i]=Qlist.begin();
          flagl[i]=flaglist.begin();
          if(i!=numofvertex)
             Qiter--;
       }
       
       
       list<int>::iterator connectgraphiter;
       list<listinttype>::iterator Qlayeriter;
       

       

       int biggest;
       int tempnumofvertex;

       
       tempnumofvertex=numofvertex;
       
       while(tempnumofvertex--)
       {
          Qlayeriter=Qlist.begin();
          biggest=*(Qlayeriter->begin());
          sortedorder[numofvertex-tempnumofvertex]=biggest;
          visited[biggest]=1;
          Qlayeriter->pop_front();
          
          if(Qlayeriter->size()==0)
          {
             Qlist.erase(Qlayeriter);
             flaglist.erase(flagl[biggest]);
          }

          
          for(connectgraphiter=connectgraph[biggest].begin();connectgraphiter!=connectgraph[biggest].end();connectgraphiter++)
          {
             if(visited[*connectgraphiter])
                continue;
             Qiter=vl[*connectgraphiter];
             Qlayeriter=vlayer[*connectgraphiter];
             Qlayeriter->erase(Qiter);
             
              if(*flagl[*connectgraphiter]==1)
             {
                Qlayeriter--;
                Qiter=Qlayeriter->begin();
                Qlayeriter->insert(Qiter,*connectgraphiter);

                Qiter--;
                vl[*connectgraphiter]=Qiter;
                vlayer[*connectgraphiter]=Qlayeriter;
             }
             else
             {
                bucket.clear();
                bucket.push_front(*connectgraphiter);
                Qlist.insert(Qlayeriter,bucket);

                Qlayeriter--;
                Qiter=Qlayeriter->begin();
                vl[*connectgraphiter]=Qiter;
                vlayer[*connectgraphiter]=Qlayeriter;

                *flagl[*connectgraphiter]=1;
                flaglist.insert(flagl[*connectgraphiter],0);
                
             }
             tempflagl=flagl[*connectgraphiter];
             flagl[*connectgraphiter]--;
             Qlayeriter++;
             if(Qlayeriter->size()==0)
             {
                Qlist.erase(Qlayeriter);
                flaglist.erase(tempflagl);
             }
          }
          for(flagiter=flaglist.begin();flagiter!=flaglist.end();flagiter++)
             if(*flagiter==1)
                *flagiter=0;         
       
       }
    }
    inline bool checkpeo(int numofvertex)//perfecteliminationorder
    {
       list<int>::iterator iter;
       int max;
       
       for(int i=numofvertex;i>=1;i--)
       {
          int flag=0;
          for(iter=connectgraph[i].begin();iter!=connectgraph[i].end();iter++)
             if(sortedorder[*iter]<sortedorder[i])
             {
                if(flag==0)
                {
                   max=*iter;
                   flag=1;
                }
                else if(sortedorder[max]<sortedorder[*iter])
                   max=*iter;
             }
          if(flag==0)
             continue;
          for(iter=connectgraph[i].begin();iter!=connectgraph[i].end();iter++)
             if(max!=*iter&&sortedorder[*iter]<sortedorder[i]&&!connectarray[*iter][max])
                return 0;
       }
       return 1;
    }

    int main()
    {
       int numofvertex,numofedge;
       int fromnode,tonode;
       int i,j;
       
       while(scanf("%d %d",&numofvertex,&numofedge)&&numofvertex!=0&&numofedge!=0)
       {
          
          for(i=1;i<=numofvertex;i++)
             connectgraph[i].clear();

          for(i=1;i<=numofvertex;i++)
             for(j=1;j<=numofvertex;j++)
                connectarray[i][j]=0;
          
          while(numofedge--)
          {
             scanf("%d %d",&fromnode,&tonode);
             connectgraph[fromnode].push_back(tonode);
             connectgraph[tonode].push_back(fromnode);
             connectarray[fromnode][tonode]=1;
             connectarray[tonode][fromnode]=1;
          }

          mcs(numofvertex);
          if(!checkpeo(numofvertex))
             printf("Imperfect\n\n");
          else
             printf("Perfect\n\n");
       }
       return 0;
    }



    /*********************************************
             MCS
    *********************************************/
    /*
    bool Used[2001];
    int Set1[2001];
    void mcs(int n)
    {
       int id,i,j,Max,MaxValue;
       int Link[2001];
       for(int i=1;i<=2000;i++)
       {
          Used[i]=false;
          Set1[i]=0;
       }
        Set1[n]=1;
       Used[1]=true;
       for(id=n-1;id>=1;id--)
       {
          for(i=1;i<=n;i++)
             Link[i]=0;
          for(i=1;i<=n;i++)
          {
             if(Used[i]==false)
             {
                for(j=1;j<=n-id;j++)
                {
                   if(connectarray[i][Set1[n-j+1]]==true)
                      Link[i]++;
                }
             }
          }
          MaxValue=0;
          for(i=1;i<=n;i++)
             if(Link[i]>MaxValue)
             {
                MaxValue=Link[i];
                Max=i;
             }
          Set1[id]=Max;Used[Max]=true;

       }
       for(i=1;i<=n;i++)
          sortedorder[i]=Set1[n-i+1];   
    }
    */

[/code]

zghenry
    Newbie
     
    Posts: 1
    Joined: Wed, Jul 23, 2008 06:05

Top