equal
deleted
inserted
replaced
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; |