lemon/planarity.h
changeset 955 7f6eeffe3cd1
parent 828 5fd7fafc4470
child 999 00f8d9f9920d
equal deleted inserted replaced
2:29265c806571 3:0f96c547c2ff
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   138     };
   138     };
   139 
   139 
   140     template <typename Graph>
   140     template <typename Graph>
   141     class PlanarityChecking {
   141     class PlanarityChecking {
   142     private:
   142     private:
   143       
   143 
   144       TEMPLATE_GRAPH_TYPEDEFS(Graph);
   144       TEMPLATE_GRAPH_TYPEDEFS(Graph);
   145 
   145 
   146       const Graph& _graph;
   146       const Graph& _graph;
   147 
   147 
   148     private:
   148     private:
   149       
   149 
   150       typedef typename Graph::template NodeMap<Arc> PredMap;
   150       typedef typename Graph::template NodeMap<Arc> PredMap;
   151       
   151 
   152       typedef typename Graph::template EdgeMap<bool> TreeMap;
   152       typedef typename Graph::template EdgeMap<bool> TreeMap;
   153       
   153 
   154       typedef typename Graph::template NodeMap<int> OrderMap;
   154       typedef typename Graph::template NodeMap<int> OrderMap;
   155       typedef std::vector<Node> OrderList;
   155       typedef std::vector<Node> OrderList;
   156 
   156 
   157       typedef typename Graph::template NodeMap<int> LowMap;
   157       typedef typename Graph::template NodeMap<int> LowMap;
   158       typedef typename Graph::template NodeMap<int> AncestorMap;
   158       typedef typename Graph::template NodeMap<int> AncestorMap;
   219                      order_map, order_list, node_data, merge_roots);
   219                      order_map, order_list, node_data, merge_roots);
   220             }
   220             }
   221           }
   221           }
   222 
   222 
   223           for (typename MergeRoots::Value::iterator it =
   223           for (typename MergeRoots::Value::iterator it =
   224                  merge_roots[node].begin(); 
   224                  merge_roots[node].begin();
   225                it != merge_roots[node].end(); ++it) {
   225                it != merge_roots[node].end(); ++it) {
   226             int rn = *it;
   226             int rn = *it;
   227             walkDown(rn, i, node_data, order_list, child_lists,
   227             walkDown(rn, i, node_data, order_list, child_lists,
   228                      ancestor_map, low_map, embed_arc, merge_roots);
   228                      ancestor_map, low_map, embed_arc, merge_roots);
   229           }
   229           }
   430 
   430 
   431               int yn = node_data[rn].prev;
   431               int yn = node_data[rn].prev;
   432               Node ynode = order_list[yn];
   432               Node ynode = order_list[yn];
   433 
   433 
   434               bool rd;
   434               bool rd;
   435               if (!external(xnode, rorder, child_lists, 
   435               if (!external(xnode, rorder, child_lists,
   436                             ancestor_map, low_map)) {
   436                             ancestor_map, low_map)) {
   437                 rd = true;
   437                 rd = true;
   438               } else if (!external(ynode, rorder, child_lists,
   438               } else if (!external(ynode, rorder, child_lists,
   439                                    ancestor_map, low_map)) {
   439                                    ancestor_map, low_map)) {
   440                 rd = false;
   440                 rd = false;