COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 3:272a5677bd6d in lemon-0.x for src


Ignore:
Timestamp:
12/13/03 16:44:50 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@15
Message:
  • Marci type iterator constructors
  • src/demo/bfsdemo.cc: demo for bfs.h
  • cosmetical changes
Location:
src
Files:
1 added
5 edited

Legend:

Unmodified
Added
Removed

  • src/include/bfs.h

    r2 r3  
    3939 
    4040 
    41 //   Nem jo! Osszeakad a masik Set-tel
     41//   Nem jo! Osszeakad a masik Put-tel
    4242//   class do_nothing_map {};
    4343//   template <typename V,typename T>
    44 //   void Set(const do_nothing_map &p,const V &v,const T &t) {}
     44//   void Put(const do_nothing_map &p,const V &v,const T &t) {}
    4545 
    4646  struct do_nothing_map {
    4747  template <typename V,typename T>
    48   static void Set(V v,T t) {}
     48  static void Put(V v,T t) {}
    4949  };
    5050 
    … …  
    5454  public:
    5555    typedef T value_type;
    56     static void Set(const I &i, const T &t) {(*i).*M=t;}
     56    static void Put(const I &i, const T &t) {(*i).*M=t;}
    5757    static T Get(const I i) {return (*i).*M;}
    5858    T &operator[](I i) {return (*i).*M;}
    … …  
    6161  /*
    6262     template <typename C,typename I,typename T, T C::*M>
    63      void Set(class_element_map<C,T,M> p,I i, T t)
     63     void Put(class_element_map<C,T,M> p,I i, T t)
    6464     {
    6565     i->*M=t;   
    … …  
    6868
    6969  template <typename P,typename I,typename T>
    70   inline void Set(P &p,const I &i, const T &t)
    71   {
    72     p.Set(i,t);   
     70  inline void Put(P &p,const I &i, const T &t)
     71  {
     72    p.Put(i,t);   
    7373  };
    7474  template <typename P,typename I>
    … …  
    126126      bfs_node_data<G> NodeType::*d;
    127127      typedef bool value_type;
    128       void Set(typename G::NodeIterator &i, const value_type &t)
     128      void Put(typename G::NodeIterator &i, const value_type &t)
    129129      {((*i).*d).visited=t;}
    130130      value_type Get(const typename G::NodeIterator &i) const
    … …  
    137137      bfs_node_data<G> NodeType::*d;
    138138      typedef typename G::EdgeIterator value_type;
    139       void Set(typename G::NodeIterator &i, const value_type &t)
     139      void Put(typename G::NodeIterator &i, const value_type &t)
    140140      {((*i).*d).tree=t;}
    141141      value_type Get(const typename G::NodeIterator &i) const
    … …  
    148148      bfs_node_data<G> NodeType::*d;
    149149      typedef int value_type;
    150       void Set(typename G::NodeIterator &i, const value_type &t)
     150      void Put(typename G::NodeIterator &i, const value_type &t)
    151151      {((*i).*d).dist=t;}
    152152      value_type Get(const typename G::NodeIterator &i) const
    … …  
    159159      bfs_node_data<G> NodeType::*d;
    160160      typedef int value_type;
    161       void Set(typename G::NodeIterator &i,  const value_type &t)
     161      void Put(typename G::NodeIterator &i,  const value_type &t)
    162162      {((*i).*d).priority=t;}
    163163      value_type Get(const typename G::NodeIterator &i) const
    … …  
    176176    bfs_static_maps(const bfs_node_data<G> NodeType::*dd)
    177177    {
    178       SetDataField(dd);
     178      PutDataField(dd);
    179179    }
    180180   
    … …  
    211211   
    212212    for(Gr.GetFirst(n);n.isValid();++n)
    213       Set(maps.visited,n,false);
     213      Put(maps.visited,n,false);
    214214   
    215215    queue<Q_T> Q;
    … …  
    218218    q.dist=0;
    219219    Q.push(q);
    220     Set(maps.visited,start_node,true);
    221     //      Set(maps::tree,start_node,?????);
    222     Set(maps.dist,start_node,0);
    223     Set(maps.priority,start_node,pr++);
     220    Put(maps.visited,start_node,true);
     221    //      Put(maps::tree,start_node,?????);
     222    Put(maps.dist,start_node,0);
     223    Put(maps.priority,start_node,pr++);
    224224   
    225225    do {
    … …  
    231231          q.dist=d;
    232232          Q.push(q);
    233           Set(maps.visited,m,true);
    234           Set(maps.tree,m,e);
    235           Set(maps.dist,m,d);
    236           Set(maps.priority,m,pr++);
     233          Put(maps.visited,m,true);
     234          Put(maps.tree,m,e);
     235          Put(maps.dist,m,d);
     236          Put(maps.priority,m,pr++);
    237237        }
    238238    } while(!Q.empty());

  • src/include/graph.h

    r2 r3  
    5858     
    5959      NodeIterator() {;}
     60      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
     61      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();}
    6062      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
    6163     
    … …  
    149151    {
    150152    public:
     153      InEdgeIterator() {}
     154      InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
     155      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
     156
    151157      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
    152158      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
    … …  
    170176    {
    171177    public:
     178      OutEdgeIterator() {}
     179      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
     180      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
     181
    172182      OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
    173183      OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
    … …  
    193203     
    194204    public:
     205      SymEdgeIterator() {}
     206      SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
     207      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
     208
    195209      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
    196210      SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
    … …  
    217231     
    218232    public:
     233      AllEdgeIterator() {}
     234      AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
     235      {
     236        e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
     237      } 
     238
    219239      AllEdgeIterator &GoNext()
    220240      {
    … …  
    249269    typedef SymEdgeIterator DeletingSymEdgeIterator;
    250270   
    251     const NodeIterator &FirstNode()
     271    const NodeIterator FirstNode()
    252272    {
    253273      NodeIterator i;
    … …  
    285305   
    286306    //Vagy beginnode()?
    287     const DeletingEdgeIterator &FirstOut(const NodeIterator &n)
     307    const DeletingEdgeIterator FirstOut(const NodeIterator &n)
    288308    {
    289309      EdgeIterator i;
    … …  
    291311      return i;
    292312    }
    293     const DeletingEdgeIterator &FirstIn(const NodeIterator &n)
     313    const DeletingEdgeIterator FirstIn(const NodeIterator &n)
    294314    {
    295315      EdgeIterator i;
    … …  
    297317      return i;
    298318    }
    299     const DeletingSymEdgeIterator &FirstSym(const NodeIterator &n)
     319    const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
    300320    {
    301321      EdgeIterator i;
    … …  
    369389   
    370390    int NodeNum() { OldGraph<N,E>::NodeNum(); }
    371     int Clean() { OldGraph<N,E>::Clean(); }
     391    void Clean() { OldGraph<N,E>::Clean(); }
    372392
    373393    Graph() : _FST(this) {}

  • src/include/oldgraph.h

    r1 r3  
    112112  int NodeNum() {return nodenum;};
    113113  int EdgeNum();
    114   int MaxNode() {return nodes_size;};
    115   int FirstNode() {return firstnode;};
    116   int NextNode(int n) {return nodes[n].next;};
    117   int PrevNode(int n) {return nodes[n].prev;};
    118   N& operator()(int n) {return *(N*)(nodes[n].data);};
    119   N& Data      (int n) {return *(N*)(nodes[n].data);};
     114  int MaxNode() const {return nodes_size;};
     115  int FirstNode() const {return firstnode;};
     116  int NextNode(int n) const {return nodes[n].next;};
     117  int PrevNode(int n) const {return nodes[n].prev;};
     118  N& operator()(int n) const {return *(N*)(nodes[n].data);};
     119  N& Data      (int n) const {return *(N*)(nodes[n].data);};
    120120  int AddNode();
    121   void AddNodeBlock(int n) {for(int i=0;i<n;i++) AddNode();}
     121  void AddNodeBlock(int n) const {for(int i=0;i<n;i++) AddNode();}
    122122  int AddNode(int n);
    123123  void Delete(int n);
    124   int isaNode(int n) {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
    125  
    126   int InDeg(int n) {return nodes[n].indeg;};
    127   int OutDeg(int n) {return nodes[n].outdeg;};
    128   EdgePoint FirstIn(int n) {return nodes[n].firstin;};
    129   EdgePoint FirstOut(int n) {return nodes[n].firstout;};
    130 
    131   E& operator()(EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
    132   E& Data      (EdgePoint e) {return *(E*)(((edge_t*)e)->data);};
    133   int From(EdgePoint e) {return e->from;};
    134   int To(EdgePoint e) {return e->to;};
    135   EdgePoint NextIn(EdgePoint e)
     124  int isaNode(int n) const
     125        {return n>=0&&n<nodes_size&&nodes[n].indeg!=FREE_NODE;};
     126 
     127  int InDeg(int n) const {return nodes[n].indeg;};
     128  int OutDeg(int n) const {return nodes[n].outdeg;};
     129  EdgePoint FirstIn(int n) const {return nodes[n].firstin;};
     130  EdgePoint FirstOut(int n) const {return nodes[n].firstout;};
     131
     132  E& operator()(EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
     133  E& Data      (EdgePoint e) const {return *(E*)(((edge_t*)e)->data);};
     134  int From(EdgePoint e) const {return e->from;};
     135  int To(EdgePoint e) const {return e->to;};
     136  EdgePoint NextIn(EdgePoint e) const
    136137    {return e->nextin;};
    137   EdgePoint NextOut(EdgePoint e)
     138  EdgePoint NextOut(EdgePoint e)const
    138139    {return e->nextout;};
    139140  EdgePoint AddEdge(int f, int t);
    … …  
    142143  //  EdgePoint Edge(E &d)
    143144  //    {return (EdgePoint)(((char*)&d)-(char*)&(((edge_t*)NULL)->data));};
    144   E& operator()(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
    145   E& Data(int f, int t) {return *(E*)(((edge_t*)Edge(f,t))->data);};
     145  E& operator()(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
     146  E& Data(int f, int t) const {return *(E*)(((edge_t*)Edge(f,t))->data);};
    146147  void Delete(int f, int t) {Delete(Edge(f,t));};
    147148  void Reverse(EdgePoint e);
    … …  
    149150  // Functions for EdgeIndex
    150151 
    151   EdgePoint Edge(EdgeIndex i)
     152  EdgePoint Edge(EdgeIndex i) const
    152153    { return (EdgePoint)(edges[i.block]->fields+i.index);};
    153   EdgeIndex Index(EdgePoint e) { return e->index;};
    154   EdgeIndex Index(int f, int t) { EdgePoint e; return Edge(f,t)->index; }
     154  EdgeIndex Index(EdgePoint e) const { return e->index;};
     155  EdgeIndex Index(int f, int t) const { EdgePoint e; return Edge(f,t)->index; }
    155156  void Delete(EdgeIndex i) { Delete(Edge(i));};
    156   E& operator()(EdgeIndex i)
     157  E& operator()(EdgeIndex i) const
    157158     {return *(E*)(edges[i.block]->fields[i.index].data);};
    158   E& Data(EdgeIndex i)
     159  E& Data(EdgeIndex i) const
    159160     {return *(E*)(edges[i.block]->fields[i.index].data);};
    160161  EdgePoint AddEdge(int f, int t,EdgeIndex in);
    … …  
    164165  // Operators for symmetric graphs:
    165166
    166   EdgePoint FirstEdge(int n)
     167  EdgePoint FirstEdge(int n) const
    167168    { return (EdgePoint)(FirstIn(n)?FirstIn(n):FirstOut(n));};
    168   EdgePoint NextEdge(int n,EdgePoint e)
     169  EdgePoint NextEdge(int n,EdgePoint e) const
    169170    { return From(e)==n?NextOut(e):(NextIn(e)?NextIn(e):FirstOut(n)); };
    170   int Opposite(EdgePoint e,int n)
     171  int Opposite(EdgePoint e,int n) const
    171172    { return From(e)+To(e)-n; };
    172173 
    … …  
    223224template<class N, class E> void OldGraph<N,E>::destroy()
    224225{
    225   edge_block *oe;
    226226  int i;
    227227 

  • src/work/graphdemo.cc

    r2 r3  
    2727typedef Graph<NodeData,EdgeData> TestGraph;
    2828
    29 /*
    30 struct isVis_map {};
    31 bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
    32 void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
    33 */
    34 
    35 class my_bfs_maps
    36 {
    37 public:
    38   //isVis_map visited;  //node->bool (RW)
    39   class_element_map<TestGraph::NodeIterator,
    40                     TestGraph::NodeType,
    41                     bool,
    42                     &NodeData::isVis> visited;
    43   struct _tree_map_t {
    44     typedef TestGraph::EdgeIterator value_type;
    45     void Set(const TestGraph::NodeIterator &n,const value_type &t)
    46     {
    47       cout << t.From()->id << "->" << t.To()->id << '\n';
    48     }
    49   } tree;
    50   do_nothing_map dist;   //node->int (W)
    51   do_nothing_map priority; //node->int (W)
    52   //priority_map priority; //node->int (W)
    53 };
    54 
    55 
    56 
    57 
    58 class IGraph
    59 {
    60 public:
    61 
    62   //  struct NodeType {bfs_node_data<TestGraph> bfs;};
    63   struct NodeType {bool isVis;};
    64 
    65   vector<NodeType> nodes;
    66  
    67   class NodeIterator
    68   {
    69   public:
    70     IGraph *G;
    71     int n;
    72     NodeIterator &operator ++() { n++; return *this;}
    73     NodeType &operator *() const { return G->nodes[n];}
    74     NodeType *operator ->() const { return &(G->nodes[n]);}
    75     bool isValid() const {return n<=5000;}
    76     int Index() {return n;} //csak a kiirashoz kell
    77   };
    78 
    79   void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
    80 
    81   class OutEdgeIterator
    82   {   
    83   public:
    84     IGraph *G;
    85     int f,t;
    86     int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
    87     OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
    88     bool isValid() const {return t<=5000;}
    89     NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
    90     NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
    91     NodeIterator Anode() const {return From();}
    92     NodeIterator Bnode() const {return To();}
    93   };
    94 
    95   typedef OutEdgeIterator EdgeIterator;
    96   void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
    97   {i.G=this;i.f=n.n;i.t=0;++i;}
    98 
    99   IGraph() : nodes(5000) {}
    100 };
    101 
    102 class IMaps_t
    103 {
    104 public:
    105 //     class_element_map<IGraph::NodeIterator,
    106 //                  IGraph::NodeType,
    107 //                  bool,
    108 //                  &IGraph::NodeType::isVis> visited;
    109   struct _visited_map_t {
    110     typedef bool value_type;
    111     void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
    112     value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
    113   } visited;
    114   struct _tree_map_t {
    115     typedef IGraph::EdgeIterator value_type;
    116     void Set(const IGraph::NodeIterator &n,const value_type &t)
    117     { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
    118   } tree;
    119   do_nothing_map dist;   //node->int (W)
    120   do_nothing_map priority; //node->int (W)
    121 };
    122 
    123 void main()
     29int main()
    12430{
    12531  TestGraph G;
    126   TestGraph::NodeIterator n,m,o,p,q;
    127   TestGraph::OutEdgeIterator e,f,g,h;
    128   int i,j,k;
     32  TestGraph::NodeIterator n,m;
     33  TestGraph::OutEdgeIterator e;
     34  int i;
    12935
    13036 
    … …  
    17076   
    17177  ;
    172   for(n=G.First();n.isValid();++n)
     78  for(n=G.First();n.isValid();++n) //Demo
    17379    {
    17480      e=G.First(n);
    17581      while(e.isValid())
    176         if((e->id)%2) G.Delete(e++);
     82        if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
    17783        else ++e;
    17884    }
    … …  
    19399    }
    194100 
    195   n=G.First();
    196 
    197 
    198   //G.Clean();
    199 
    200   cout << "\n\n\n BFS \n\n\n";
    201   //my_bfs_maps Maps;
    202   //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
     101  // For Marci's sake
    203102 
    204   /// bfs(G,n,Maps);
    205 
    206   cout << '\n';
    207 
    208   IGraph IG;
    209   IMaps_t IMaps;
    210 
    211   IGraph::NodeIterator in;
    212   IG.GetFirst(in);
    213   ++in;
    214   bfs(IG,in,IMaps);
    215  
    216  
     103  {
     104    G.Clean();
     105   
     106    for(int i=1;i<=10;i++) G.AddNode()->id=i;
     107   
     108   
     109    {  //I would'n say I'm really happy with this.
     110      int i;
     111      for(TestGraph::NodeIterator n(G);n.isValid();n++)
     112        for(TestGraph::NodeIterator m(G);m.isValid();++m)
     113          if(n!=m) G.AddEdge(n,m)->id=++i;
     114    }
     115   
     116    for(TestGraph::NodeIterator n(G);n.isValid();++n) //Demo
     117      {
     118        TestGraph::OutEdgeIterator e(G,n);
     119        while(e.isValid())
     120          if((e->id)%2) G.Delete(e++);  //it may be nice to have a postfix ++
     121          else ++e;
     122      }
     123   
     124    for(TestGraph::AllEdgeIterator a(G);a.isValid();++a)
     125      cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
     126   
     127    cout << "\n\n\n";
     128   
     129    for(TestGraph::NodeIterator n(G);n.isValid();++n)
     130      {
     131        cout << n->id << "->";
     132        for(TestGraph::OutEdgeIterator e(G,n);e.isValid();++e)
     133          cout << e->id << ":" << e.To()->id << ' ';
     134        cout << '\n';
     135      }
     136  }
    217137}

  • src/work/makefile

    r2 r3  
    1 graphdemo: graphdemo.cc ../include/graph.h ../include/bfs.h \
     1CXXFLAGS=-g -Wall -I../include
     2
     3none:
     4        @echo 'Please use one of these forms:'
     5        @echo '   make all'
     6        @echo '   make clean'
     7        @echo '   make graphdemo'
     8        @echo '   make bfsdemo'
     9
     10all: graphdemo bfsdemo
     11
     12clean:
     13        rm graphdemo bfsdemo
     14graphdemo: graphdemo.cc ../include/graph.h \
    215        ../include/oldgraph.h makefile
    3         g++ -g -I../include -o graphdemo graphdemo.cc
     16        g++ $(CXXFLAGS) -o graphdemo graphdemo.cc
     17
     18bfsdemo: bfsdemo.cc ../include/graph.h ../include/bfs.h \
     19        ../include/oldgraph.h makefile
     20        g++ $(CXXFLAGS) -o bfsdemo bfsdemo.cc
Note: See TracChangeset for help on using the changeset viewer.