COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 774:4297098d9677 in lemon-0.x for src/work/marci


Ignore:
Timestamp:
08/30/04 14:01:47 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
Message:

Merge back the whole branches/hugo++ to trunk.

Location:
src/work/marci
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/bfs_dfs.h

    r671 r774  
    6161        bfs_queue.push(s);
    6262        graph->first(actual_edge, s);
    63         if (graph->valid(actual_edge)) {
    64           Node w=graph->bNode(actual_edge);
     63        if (actual_edge!=INVALID) {
     64          Node w=graph->head(actual_edge);
    6565          if (!reached[w]) {
    6666            bfs_queue.push(w);
    … …  
    7979    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    8080    operator++() {
    81       if (graph->valid(actual_edge)) {
    82         graph->next(actual_edge);
    83         if (graph->valid(actual_edge)) {
    84           Node w=graph->bNode(actual_edge);
     81      if (actual_edge!=INVALID) {
     82        ++actual_edge;
     83        if (actual_edge!=INVALID) {
     84          Node w=graph->head(actual_edge);
    8585          if (!reached[w]) {
    8686            bfs_queue.push(w);
    … …  
    9595        if (!bfs_queue.empty()) {
    9696          graph->first(actual_edge, bfs_queue.front());
    97           if (graph->valid(actual_edge)) {
    98             Node w=graph->bNode(actual_edge);
     97          if (actual_edge!=INVALID) {
     98            Node w=graph->head(actual_edge);
    9999            if (!reached[w]) {
    100100              bfs_queue.push(w);
    … …  
    118118    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    119119    /// Returns if a-node is examined.
    120     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     120    bool isANodeExamined() const { return actual_edge==INVALID; }
    121121    /// Returns a-node of the actual edge, so does if the edge is invalid.
    122122    Node aNode() const { return bfs_queue.front(); }
    … …  
    238238      actual_edge=dfs_stack.top();
    239239      //actual_node=G.aNode(actual_edge);
    240       if (graph->valid(actual_edge)/*.valid()*/) {
    241         Node w=graph->bNode(actual_edge);
     240      if (actual_edge!=INVALID/*.valid()*/) {
     241        Node w=graph->head(actual_edge);
    242242        actual_node=w;
    243243        if (!reached[w]) {
    … …  
    248248          b_node_newly_reached=true;
    249249        } else {
    250           actual_node=graph->aNode(actual_edge);
    251           graph->next(dfs_stack.top());
     250          actual_node=graph->tail(actual_edge);
     251          ++dfs_stack.top();
    252252          b_node_newly_reached=false;
    253253        }
    … …  
    267267    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    268268    /// Returns if a-node is examined.
    269     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     269    bool isANodeExamined() const { return actual_edge==INVALID; }
    270270    /// Returns a-node of the actual edge, so does if the edge is invalid.
    271271    Node aNode() const { return actual_node; /*FIXME*/}

  • src/work/marci/iterator_bfs_demo.cc

    r642 r774  
    55
    66#include <sage_graph.h>
    7 //#include <smart_graph.h>
     7#include <hugo/smart_graph.h>
    88#include <bfs_dfs.h>
    99#include <hugo/graph_wrapper.h>
    … …  
    2929int main (int, char*[])
    3030{
    31   //typedef SmartGraph Graph;
    32   typedef SageGraph Graph;
     31  typedef SmartGraph Graph;
     32  //typedef SageGraph Graph;
    3333
    3434  typedef Graph::Node Node;
    … …  
    9292   
    9393    cout << "bfs and dfs iterator demo on the directed graph" << endl;
    94     for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
     94    for(Graph::NodeIt n(G); n!=INVALID; ++n) {
    9595      cout << node_name[n] << ": ";
    9696      cout << "out edges: ";
    97       for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
     97      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
    9898        cout << edge_name[e] << " ";
    9999      cout << "in edges: ";
    100       for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
     100      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
    101101        cout << edge_name[e] << " ";
    102102      cout << endl;
    … …  
    108108    while (!bfs.finished()) {
    109109      //cout << "edge: ";
    110       if (G.valid(bfs)) {
     110      if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
    111111        cout << edge_name[bfs] << /*endl*/", " <<
    112           node_name[G.aNode(bfs)] <<
    113           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    114           node_name[G.bNode(bfs)] <<
     112          node_name[G.tail(bfs)] <<
     113          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     114          node_name[G.head(bfs)] <<
    115115          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    116116           ": is not newly reached.");
    … …  
    142142      ++dfs;
    143143      //cout << "edge: ";
    144       if (G.valid(dfs)) {
     144      if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
    145145        cout << edge_name[dfs] << /*endl*/", " <<
    146           node_name[G.aNode(dfs)] <<
    147           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    148           node_name[G.bNode(dfs)] <<
     146          node_name[G.tail(dfs)] <<
     147          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     148          node_name[G.head(dfs)] <<
    149149          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    150150           ": is not newly reached.");
    … …  
    168168   
    169169    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
    170     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     170    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
    171171      cout << node_name[GW::Node(n)] << ": ";
    172172      cout << "out edges: ";
    173       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     173      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
    174174        cout << edge_name[e] << " ";
    175175      cout << "in edges: ";
    176       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     176      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
    177177        cout << edge_name[e] << " ";
    178178      cout << endl;
    … …  
    184184    while (!bfs.finished()) {
    185185      //cout << "edge: ";
    186       if (gw.valid(GW::OutEdgeIt(bfs))) {
     186      if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
    187187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    188           node_name[gw.aNode(bfs)] <<
    189           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    190           node_name[gw.bNode(bfs)] <<
     188          node_name[gw.tail(bfs)] <<
     189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     190          node_name[gw.head(bfs)] <<
    191191          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    192192           ": is not newly reached.");
    … …  
    218218      ++dfs;
    219219      //cout << "edge: ";
    220       if (gw.valid(GW::OutEdgeIt(dfs))) {
     220      if (GW::OutEdgeIt(dfs)!=INVALID) {
    221221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    222           node_name[gw.aNode(dfs)] <<
    223           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    224           node_name[gw.bNode(dfs)] <<
     222          node_name[gw.tail(dfs)] <<
     223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     224          node_name[gw.head(dfs)] <<
    225225          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    226226           ": is not newly reached.");
    … …  
    236236  }
    237237
     238//   {
     239//     typedef UndirGraphWrapper<const Graph> GW;
     240//     GW gw(G);
     241   
     242//     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
     243   
     244//     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
     245//     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     246//       cout << node_name[GW::Node(n)] << ": ";
     247//       cout << "out edges: ";
     248//       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     249//      cout << edge_name[e] << " ";
     250//       cout << "in edges: ";
     251//       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     252//      cout << edge_name[e] << " ";
     253//       cout << endl;
     254//     }
     255// //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
     256// //       cout << edge_name.get(e) << " ";
     257// //     }
     258// //     cout << endl;
     259
     260//     cout << "bfs from t ..." << endl;
     261//     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
     262//     bfs.pushAndSetReached(t);
     263//     while (!bfs.finished()) {
     264//       //cout << "edge: ";
     265//       if (gw.valid(GW::OutEdgeIt(bfs))) {
     266//      cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
     267//        node_name[gw.aNode(bfs)] <<
     268//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     269//        node_name[gw.bNode(bfs)] <<
     270//        (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     271//         ": is not newly reached.");
     272//       } else {
     273//      cout << "invalid" << /*endl*/", " <<
     274//        node_name[bfs.aNode()] <<
     275//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     276         
     277//        "invalid.";
     278//       }
     279//       cout << endl;
     280//       ++bfs;
     281//     }
     282
     283//     cout << "    /-->    ------------->            "<< endl;
     284//     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     285//     cout << "  / |          |    /  /->     \\     "<< endl;
     286//     cout << " /  |          |   /  |    ^    \\  "<< endl;
     287//     cout << "s   |          |  /   |    |     \\->  t "<< endl;
     288//     cout << " \\  |          | /    |    |     /->  "<< endl;
     289//     cout << "  \\ |       --/ /     |    |    /     "<< endl;
     290//     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     291//     cout << "    \\-->    ------------->         "<< endl;
     292   
     293//     cout << "dfs from t ..." << endl;
     294//     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
     295//     dfs.pushAndSetReached(t);
     296//     while (!dfs.finished()) {
     297//       ++dfs;
     298//       //cout << "edge: ";
     299//       if (gw.valid(GW::OutEdgeIt(dfs))) {
     300//      cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
     301//        node_name[gw.aNode(dfs)] <<
     302//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     303//        node_name[gw.bNode(dfs)] <<
     304//        (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     305//         ": is not newly reached.");
     306//       } else {
     307//      cout << "invalid" << /*endl*/", " <<
     308//        node_name[dfs.aNode()] <<
     309//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     310         
     311//        "invalid.";
     312//       }
     313//       cout << endl;
     314//     }
     315//   }
     316
     317
     318
    238319  {
    239     typedef UndirGraphWrapper<const Graph> GW;
     320    typedef BidirGraphWrapper<const Graph> GW;
    240321    GW gw(G);
    241322   
    242323    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
    243324   
    244     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    245     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
     325    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
     326//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
     327//       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
     328//     }
     329    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
    246330      cout << node_name[GW::Node(n)] << ": ";
    247331      cout << "out edges: ";
    248       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     332      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
    249333        cout << edge_name[e] << " ";
    250334      cout << "in edges: ";
    251       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
     335      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
    252336        cout << edge_name[e] << " ";
    253337      cout << endl;
    … …  
    263347    while (!bfs.finished()) {
    264348      //cout << "edge: ";
    265       if (gw.valid(GW::OutEdgeIt(bfs))) {
     349      if (GW::OutEdgeIt(bfs)!=INVALID) {
    266350        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    267           node_name[gw.aNode(bfs)] <<
    268           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    269           node_name[gw.bNode(bfs)] <<
     351          node_name[gw.tail(bfs)] <<
     352          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     353          node_name[gw.head(bfs)] <<
    270354          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    271355           ": is not newly reached.");
    … …  
    297381      ++dfs;
    298382      //cout << "edge: ";
    299       if (gw.valid(GW::OutEdgeIt(dfs))) {
     383      if (GW::OutEdgeIt(dfs)!=INVALID) {
    300384        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    301           node_name[gw.aNode(dfs)] <<
    302           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    303           node_name[gw.bNode(dfs)] <<
     385          node_name[gw.tail(dfs)] <<
     386          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     387          node_name[gw.head(dfs)] <<
    304388          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    305389           ": is not newly reached.");
    … …  
    314398    }
    315399  }
    316 
    317 
    318 
    319   {
    320     typedef BidirGraphWrapper<const Graph> GW;
    321     GW gw(G);
    322    
    323     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
    324    
    325     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    326     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
    327       cout << node_name[GW::Node(n)] << ": ";
    328       cout << "out edges: ";
    329       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
    330         cout << edge_name[e] << " ";
    331       cout << "in edges: ";
    332       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
    333         cout << edge_name[e] << " ";
    334       cout << endl;
    335     }
    336 //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
    337 //       cout << edge_name.get(e) << " ";
    338 //     }
    339 //     cout << endl;
    340 
    341     cout << "bfs from t ..." << endl;
    342     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    343     bfs.pushAndSetReached(t);
    344     while (!bfs.finished()) {
    345       //cout << "edge: ";
    346       if (gw.valid(GW::OutEdgeIt(bfs))) {
    347         cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
    348           node_name[gw.aNode(bfs)] <<
    349           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    350           node_name[gw.bNode(bfs)] <<
    351           (bfs.isBNodeNewlyReached() ? ": is newly reached." :
    352            ": is not newly reached.");
    353       } else {
    354         cout << "invalid" << /*endl*/", " <<
    355           node_name[bfs.aNode()] <<
    356           (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    357          
    358           "invalid.";
    359       }
    360       cout << endl;
    361       ++bfs;
    362     }
    363 
    364     cout << "    /-->    ------------->            "<< endl;
    365     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
    366     cout << "  / |          |    /  /->     \\     "<< endl;
    367     cout << " /  |          |   /  |    ^    \\  "<< endl;
    368     cout << "s   |          |  /   |    |     \\->  t "<< endl;
    369     cout << " \\  |          | /    |    |     /->  "<< endl;
    370     cout << "  \\ |       --/ /     |    |    /     "<< endl;
    371     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
    372     cout << "    \\-->    ------------->         "<< endl;
    373    
    374     cout << "dfs from t ..." << endl;
    375     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    376     dfs.pushAndSetReached(t);
    377     while (!dfs.finished()) {
    378       ++dfs;
    379       //cout << "edge: ";
    380       if (gw.valid(GW::OutEdgeIt(dfs))) {
    381         cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
    382           node_name[gw.aNode(dfs)] <<
    383           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    384           node_name[gw.bNode(dfs)] <<
    385           (dfs.isBNodeNewlyReached() ? ": is newly reached." :
    386            ": is not newly reached.");
    387       } else {
    388         cout << "invalid" << /*endl*/", " <<
    389           node_name[dfs.aNode()] <<
    390           (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
    391          
    392           "invalid.";
    393       }
    394       cout << endl;
    395     }
    396   }
    397 
    398 
    399400
    400401  return 0;
Note: See TracChangeset for help on using the changeset viewer.