ceph/src/boost/boost/graph/minimum_degree_ordering.hpp

   1 //-*-c++-*-
   2 //=======================================================================
   3 // Copyright 1997-2001 University of Notre Dame.
   4 // Authors: Lie-Quan Lee, Jeremy Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef MINIMUM_DEGREE_ORDERING_HPP
  12 #define MINIMUM_DEGREE_ORDERING_HPP
  13
  14 #include <vector>
  15 #include <boost/assert.hpp>
  16 #include <boost/config.hpp>
  17 #include <boost/pending/bucket_sorter.hpp>
  18 #include <boost/detail/numeric_traits.hpp> // for integer_traits
  19 #include <boost/graph/graph_traits.hpp>
  20 #include <boost/property_map/property_map.hpp>
  21
  22 namespace boost {
  23
  24   namespace detail {
  25
  26     //
  27     // Given a set of n integers (where the integer values range from
  28     // zero to n-1), we want to keep track of a collection of stacks
  29     // of integers. It so happens that an integer will appear in at
  30     // most one stack at a time, so the stacks form disjoint sets.
  31     // Because of these restrictions, we can use one big array to
  32     // store all the stacks, intertwined with one another.
  33     // No allocation/deallocation happens in the push()/pop() methods
  34     // so this is faster than using std::stack's.
  35     //
  36     template <class SignedInteger>
  37     class Stacks {
  38       typedef SignedInteger value_type;
  39       typedef typename std::vector<value_type>::size_type size_type;
  40     public:
  41       Stacks(size_type n) : data(n) {}
  42
  43       //: stack
  44       class stack {
  45         typedef typename std::vector<value_type>::iterator Iterator;
  46       public:
  47         stack(Iterator _data, const value_type& head)
  48           :  data(_data), current(head) {}
  49
  50         // did not use default argument here to avoid internal compiler error
  51         // in g++.
  52         stack(Iterator _data)
  53           : data(_data), current(-(std::numeric_limits<value_type>::max)()) {}
  54
  55         void pop() {
  56           BOOST_ASSERT(! empty());
  57           current = data[current];
  58         }
  59         void push(value_type v) {
  60           data[v] = current;
  61           current = v;
  62         }
  63         bool empty() {
  64           return current == -(std::numeric_limits<value_type>::max)();
  65         }
  66         value_type& top() { return current; }
  67       private:
  68         Iterator data;
  69         value_type current;
  70       };
  71
  72       // To return a stack object
  73       stack make_stack()
  74         { return stack(data.begin()); }
  75     protected:
  76       std::vector<value_type> data;
  77     };
  78
  79
  80     // marker class, a generalization of coloring.
  81     //
  82     // This class is to provide a generalization of coloring which has
  83     // complexity of amortized constant time to set all vertices' color
  84     // back to be untagged. It implemented by increasing a tag.
  85     //
  86     // The colors are:
  87     //   not tagged
  88     //   tagged
  89     //   multiple_tagged
  90     //   done
  91     //
  92     template <class SignedInteger, class Vertex, class VertexIndexMap>
  93     class Marker {
  94       typedef SignedInteger value_type;
  95       typedef typename std::vector<value_type>::size_type size_type;
  96
  97       static value_type done()
  98       { return (std::numeric_limits<value_type>::max)()/2; }
  99     public:
 100       Marker(size_type _num, VertexIndexMap index_map)
 101         : tag(1 - (std::numeric_limits<value_type>::max)()),
 102           data(_num, - (std::numeric_limits<value_type>::max)()),
 103           id(index_map) {}
 104
 105       void mark_done(Vertex node) { data[get(id, node)] = done(); }
 106
 107       bool is_done(Vertex node) { return data[get(id, node)] == done(); }
 108
 109       void mark_tagged(Vertex node) { data[get(id, node)] = tag; }
 110
 111       void mark_multiple_tagged(Vertex node) { data[get(id, node)] = multiple_tag; }
 112
 113       bool is_tagged(Vertex node) const { return data[get(id, node)] >= tag; }
 114
 115       bool is_not_tagged(Vertex node) const { return data[get(id, node)] < tag; }
 116
 117       bool is_multiple_tagged(Vertex node) const
 118         { return data[get(id, node)] >= multiple_tag; }
 119
 120       void increment_tag() {
 121         const size_type num = data.size();
 122         ++tag;
 123         if ( tag >= done() ) {
 124           tag = 1 - (std::numeric_limits<value_type>::max)();
 125           for (size_type i = 0; i < num; ++i)
 126             if ( data[i] < done() )
 127               data[i] = - (std::numeric_limits<value_type>::max)();
 128         }
 129       }
 130
 131       void set_multiple_tag(value_type mdeg0)
 132       {
 133         const size_type num = data.size();
 134         multiple_tag = tag + mdeg0;
 135
 136         if ( multiple_tag >= done() ) {
 137           tag = 1-(std::numeric_limits<value_type>::max)();
 138
 139           for (size_type i=0; i<num; i++)
 140             if ( data[i] < done() )
 141               data[i] = -(std::numeric_limits<value_type>::max)();
 142
 143           multiple_tag = tag + mdeg0;
 144         }
 145       }
 146
 147       void set_tag_as_multiple_tag() { tag = multiple_tag; }
 148
 149     protected:
 150       value_type tag;
 151       value_type multiple_tag;
 152       std::vector<value_type> data;
 153       VertexIndexMap id;
 154     };
 155
 156     template< class Iterator, class SignedInteger,
 157        class Vertex, class VertexIndexMap, int offset = 1 >
 158     class Numbering {
 159       typedef SignedInteger number_type;
 160       number_type num; //start from 1 instead of zero
 161       Iterator   data;
 162       number_type max_num;
 163       VertexIndexMap id;
 164     public:
 165       Numbering(Iterator _data, number_type _max_num, VertexIndexMap id)
 166         : num(1), data(_data), max_num(_max_num), id(id) {}
 167       void operator()(Vertex node) { data[get(id, node)] = -num; }
 168       bool all_done(number_type i = 0) const { return num + i > max_num; }
 169       void increment(number_type i = 1) { num += i; }
 170       bool is_numbered(Vertex node) const {
 171         return data[get(id, node)] < 0;
 172       }
 173       void indistinguishable(Vertex i, Vertex j) {
 174         data[get(id, i)] = - (get(id, j) + offset);
 175       }
 176     };
 177
 178     template <class SignedInteger, class Vertex, class VertexIndexMap>
 179     class degreelists_marker {
 180     public:
 181       typedef SignedInteger value_type;
 182       typedef typename std::vector<value_type>::size_type size_type;
 183       degreelists_marker(size_type n, VertexIndexMap id)
 184         : marks(n, 0), id(id) {}
 185       void mark_need_update(Vertex i) { marks[get(id, i)] = 1;  }
 186       bool need_update(Vertex i) { return marks[get(id, i)] == 1; }
 187       bool outmatched_or_done (Vertex i) { return marks[get(id, i)] == -1; }
 188       void mark(Vertex i) { marks[get(id, i)] = -1; }
 189       void unmark(Vertex i) { marks[get(id, i)] = 0; }
 190     private:
 191       std::vector<value_type> marks;
 192       VertexIndexMap id;
 193     };
 194
 195     // Helper function object for edge removal
 196     template <class Graph, class MarkerP, class NumberD, class Stack,
 197       class VertexIndexMap>
 198     class predicateRemoveEdge1 {
 199       typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 200       typedef typename graph_traits<Graph>::edge_descriptor edge_t;
 201     public:
 202       predicateRemoveEdge1(Graph& _g, MarkerP& _marker,
 203                            NumberD _numbering, Stack& n_e, VertexIndexMap id)
 204         : g(&_g), marker(&_marker), numbering(_numbering),
 205           neighbor_elements(&n_e), id(id) {}
 206
 207       bool operator()(edge_t e) {
 208         vertex_t dist = target(e, *g);
 209         if ( marker->is_tagged(dist) )
 210           return true;
 211         marker->mark_tagged(dist);
 212         if (numbering.is_numbered(dist)) {
 213           neighbor_elements->push(get(id, dist));
 214           return true;
 215         }
 216         return false;
 217       }
 218     private:
 219       Graph*   g;
 220       MarkerP* marker;
 221       NumberD  numbering;
 222       Stack*   neighbor_elements;
 223       VertexIndexMap id;
 224     };
 225
 226     // Helper function object for edge removal
 227     template <class Graph, class MarkerP>
 228     class predicate_remove_tagged_edges
 229     {
 230       typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 231       typedef typename graph_traits<Graph>::edge_descriptor edge_t;
 232     public:
 233       predicate_remove_tagged_edges(Graph& _g, MarkerP& _marker)
 234         : g(&_g), marker(&_marker) {}
 235
 236       bool operator()(edge_t e) {
 237         vertex_t dist = target(e, *g);
 238         if ( marker->is_tagged(dist) )
 239           return true;
 240         return false;
 241       }
 242     private:
 243       Graph*   g;
 244       MarkerP* marker;
 245     };
 246
 247     template<class Graph, class DegreeMap,
 248              class InversePermutationMap,
 249              class PermutationMap,
 250              class SuperNodeMap,
 251              class VertexIndexMap>
 252     class mmd_impl
 253     {
 254       // Typedefs
 255       typedef graph_traits<Graph> Traits;
 256       typedef typename Traits::vertices_size_type size_type;
 257       typedef typename detail::integer_traits<size_type>::difference_type
 258         diff_t;
 259       typedef typename Traits::vertex_descriptor vertex_t;
 260       typedef typename Traits::adjacency_iterator adj_iter;
 261       typedef iterator_property_map<vertex_t*,
 262         identity_property_map, vertex_t, vertex_t&> IndexVertexMap;
 263       typedef detail::Stacks<diff_t> Workspace;
 264       typedef bucket_sorter<size_type, vertex_t, DegreeMap, VertexIndexMap>
 265         DegreeLists;
 266       typedef Numbering<InversePermutationMap, diff_t, vertex_t,VertexIndexMap>
 267         NumberingD;
 268       typedef degreelists_marker<diff_t, vertex_t, VertexIndexMap>
 269         DegreeListsMarker;
 270       typedef Marker<diff_t, vertex_t, VertexIndexMap> MarkerP;
 271
 272       // Data Members
 273
 274       // input parameters
 275       Graph& G;
 276       int delta;
 277       DegreeMap degree;
 278       InversePermutationMap inverse_perm;
 279       PermutationMap perm;
 280       SuperNodeMap supernode_size;
 281       VertexIndexMap vertex_index_map;
 282
 283       // internal data-structures
 284       std::vector<vertex_t> index_vertex_vec;
 285       size_type n;
 286       IndexVertexMap index_vertex_map;
 287       DegreeLists degreelists;
 288       NumberingD numbering;
 289       DegreeListsMarker degree_lists_marker;
 290       MarkerP marker;
 291       Workspace work_space;
 292     public:
 293       mmd_impl(Graph& g, size_type n_, int delta, DegreeMap degree,
 294                InversePermutationMap inverse_perm,
 295                PermutationMap perm,
 296                SuperNodeMap supernode_size,
 297                VertexIndexMap id)
 298         : G(g), delta(delta), degree(degree),
 299         inverse_perm(inverse_perm),
 300         perm(perm),
 301         supernode_size(supernode_size),
 302         vertex_index_map(id),
 303         index_vertex_vec(n_),
 304         n(n_),
 305         degreelists(n_ + 1, n_, degree, id),
 306         numbering(inverse_perm, n_, vertex_index_map),
 307         degree_lists_marker(n_, vertex_index_map),
 308         marker(n_, vertex_index_map),
 309         work_space(n_)
 310       {
 311         typename graph_traits<Graph>::vertex_iterator v, vend;
 312         size_type vid = 0;
 313         for (boost::tie(v, vend) = vertices(G); v != vend; ++v, ++vid)
 314           index_vertex_vec[vid] = *v;
 315         index_vertex_map = IndexVertexMap(&index_vertex_vec[0]);
 316
 317         // Initialize degreelists.  Degreelists organizes the nodes
 318         // according to their degree.
 319         for (boost::tie(v, vend) = vertices(G); v != vend; ++v) {
 320           put(degree, *v, out_degree(*v, G));
 321           degreelists.push(*v);
 322         }
 323       }
 324
 325       void do_mmd()
 326       {
 327         // Eliminate the isolated nodes -- these are simply the nodes
 328         // with no neighbors, which are accessible as a list (really, a
 329         // stack) at location 0.  Since these don't affect any other
 330         // nodes, we can eliminate them without doing degree updates.
 331         typename DegreeLists::stack list_isolated = degreelists[0];
 332         while (!list_isolated.empty()) {
 333           vertex_t node = list_isolated.top();
 334           marker.mark_done(node);
 335           numbering(node);
 336           numbering.increment();
 337           list_isolated.pop();
 338         }
 339         size_type min_degree = 1;
 340         typename DegreeLists::stack list_min_degree = degreelists[min_degree];
 341
 342         while (list_min_degree.empty()) {
 343           ++min_degree;
 344           list_min_degree = degreelists[min_degree];
 345         }
 346
 347         // check if the whole eliminating process is done
 348         while (!numbering.all_done()) {
 349
 350           size_type min_degree_limit = min_degree + delta; // WARNING
 351           typename Workspace::stack llist = work_space.make_stack();
 352
 353           // multiple elimination
 354           while (delta >= 0) {
 355
 356             // Find the next non-empty degree
 357             for (list_min_degree = degreelists[min_degree];
 358                  list_min_degree.empty() && min_degree <= min_degree_limit;
 359                  ++min_degree, list_min_degree = degreelists[min_degree])
 360               ;
 361             if (min_degree > min_degree_limit)
 362               break;
 363
 364             const vertex_t node = list_min_degree.top();
 365             const size_type node_id = get(vertex_index_map, node);
 366             list_min_degree.pop();
 367             numbering(node);
 368
 369             // check if node is the last one
 370             if (numbering.all_done(supernode_size[node])) {
 371               numbering.increment(supernode_size[node]);
 372               break;
 373             }
 374             marker.increment_tag();
 375             marker.mark_tagged(node);
 376
 377             this->eliminate(node);
 378
 379             numbering.increment(supernode_size[node]);
 380             llist.push(node_id);
 381           } // multiple elimination
 382
 383           if (numbering.all_done())
 384             break;
 385
 386           this->update( llist, min_degree);
 387         }
 388
 389       } // do_mmd()
 390
 391       void eliminate(vertex_t node)
 392       {
 393         typename Workspace::stack element_neighbor = work_space.make_stack();
 394
 395         // Create two function objects for edge removal
 396         typedef typename Workspace::stack WorkStack;
 397         predicateRemoveEdge1<Graph, MarkerP, NumberingD,
 398                              WorkStack, VertexIndexMap>
 399           p(G, marker, numbering, element_neighbor, vertex_index_map);
 400
 401         predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker);
 402
 403         // Reconstruct the adjacent node list, push element neighbor in a List.
 404         remove_out_edge_if(node, p, G);
 405         //during removal element neighbors are collected.
 406
 407         while (!element_neighbor.empty()) {
 408           // element absorb
 409           size_type e_id = element_neighbor.top();
 410           vertex_t element = get(index_vertex_map, e_id);
 411           adj_iter i, i_end;
 412           for (boost::tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){
 413             vertex_t i_node = *i;
 414             if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
 415               marker.mark_tagged(i_node);
 416               add_edge(node, i_node, G);
 417             }
 418           }
 419           element_neighbor.pop();
 420         }
 421         adj_iter v, ve;
 422         for (boost::tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) {
 423           vertex_t v_node = *v;
 424           if (!degree_lists_marker.need_update(v_node)
 425               && !degree_lists_marker.outmatched_or_done(v_node)) {
 426             degreelists.remove(v_node);
 427           }
 428           //update out edges of v_node
 429           remove_out_edge_if(v_node, p2, G);
 430
 431           if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes
 432             supernode_size[node] += supernode_size[v_node];
 433             supernode_size[v_node] = 0;
 434             numbering.indistinguishable(v_node, node);
 435             marker.mark_done(v_node);
 436             degree_lists_marker.mark(v_node);
 437           } else {                           // not indistinguishable nodes
 438             add_edge(v_node, node, G);
 439             degree_lists_marker.mark_need_update(v_node);
 440           }
 441         }
 442       } // eliminate()
 443
 444
 445       template <class Stack>
 446       void update(Stack llist, size_type& min_degree)
 447       {
 448         size_type min_degree0 = min_degree + delta + 1;
 449
 450         while (! llist.empty()) {
 451           size_type deg, deg0 = 0;
 452
 453           marker.set_multiple_tag(min_degree0);
 454           typename Workspace::stack q2list = work_space.make_stack();
 455           typename Workspace::stack qxlist = work_space.make_stack();
 456
 457           vertex_t current = get(index_vertex_map, llist.top());
 458           adj_iter i, ie;
 459           for (boost::tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) {
 460             vertex_t i_node = *i;
 461             const size_type i_id = get(vertex_index_map, i_node);
 462             if (supernode_size[i_node] != 0) {
 463               deg0 += supernode_size[i_node];
 464               marker.mark_multiple_tagged(i_node);
 465               if (degree_lists_marker.need_update(i_node)) {
 466                 if (out_degree(i_node, G) == 2)
 467                   q2list.push(i_id);
 468                 else
 469                   qxlist.push(i_id);
 470               }
 471             }
 472           }
 473
 474           while (!q2list.empty()) {
 475             const size_type u_id = q2list.top();
 476             vertex_t u_node = get(index_vertex_map, u_id);
 477             // if u_id is outmatched by others, no need to update degree
 478             if (degree_lists_marker.outmatched_or_done(u_node)) {
 479               q2list.pop();
 480               continue;
 481             }
 482             marker.increment_tag();
 483             deg = deg0;
 484
 485             adj_iter nu = adjacent_vertices(u_node, G).first;
 486             vertex_t neighbor = *nu;
 487             if (neighbor == u_node) {
 488               ++nu;
 489               neighbor = *nu;
 490             }
 491             if (numbering.is_numbered(neighbor)) {
 492               adj_iter i, ie;
 493               for (boost::tie(i,ie) = adjacent_vertices(neighbor, G);
 494                    i != ie; ++i) {
 495                 const vertex_t i_node = *i;
 496                 if (i_node == u_node || supernode_size[i_node] == 0)
 497                   continue;
 498                 if (marker.is_tagged(i_node)) {
 499                   if (degree_lists_marker.need_update(i_node)) {
 500                     if ( out_degree(i_node, G) == 2 ) { // is indistinguishable
 501                       supernode_size[u_node] += supernode_size[i_node];
 502                       supernode_size[i_node] = 0;
 503                       numbering.indistinguishable(i_node, u_node);
 504                       marker.mark_done(i_node);
 505                       degree_lists_marker.mark(i_node);
 506                     } else                        // is outmatched
 507                       degree_lists_marker.mark(i_node);
 508                   }
 509                 } else {
 510                   marker.mark_tagged(i_node);
 511                   deg += supernode_size[i_node];
 512                 }
 513               }
 514             } else
 515               deg += supernode_size[neighbor];
 516
 517             deg -= supernode_size[u_node];
 518             degree[u_node] = deg; //update degree
 519             degreelists[deg].push(u_node);
 520             //u_id has been pushed back into degreelists
 521             degree_lists_marker.unmark(u_node);
 522             if (min_degree > deg)
 523               min_degree = deg;
 524             q2list.pop();
 525           } // while (!q2list.empty())
 526
 527           while (!qxlist.empty()) {
 528             const size_type u_id = qxlist.top();
 529             const vertex_t u_node = get(index_vertex_map, u_id);
 530
 531             // if u_id is outmatched by others, no need to update degree
 532             if (degree_lists_marker.outmatched_or_done(u_node)) {
 533               qxlist.pop();
 534               continue;
 535             }
 536             marker.increment_tag();
 537             deg = deg0;
 538             adj_iter i, ie;
 539             for (boost::tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) {
 540               vertex_t i_node = *i;
 541               if (marker.is_tagged(i_node))
 542                 continue;
 543               marker.mark_tagged(i_node);
 544
 545               if (numbering.is_numbered(i_node)) {
 546                 adj_iter j, je;
 547                 for (boost::tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) {
 548                   const vertex_t j_node = *j;
 549                   if (marker.is_not_tagged(j_node)) {
 550                     marker.mark_tagged(j_node);
 551                     deg += supernode_size[j_node];
 552                   }
 553                 }
 554               } else
 555                 deg += supernode_size[i_node];
 556             } // for adjacent vertices of u_node
 557             deg -= supernode_size[u_node];
 558             degree[u_node] = deg;
 559             degreelists[deg].push(u_node);
 560             // u_id has been pushed back into degreelists
 561             degree_lists_marker.unmark(u_node);
 562             if (min_degree > deg)
 563               min_degree = deg;
 564             qxlist.pop();
 565           } // while (!qxlist.empty()) {
 566
 567           marker.set_tag_as_multiple_tag();
 568           llist.pop();
 569         } // while (! llist.empty())
 570
 571       } // update()
 572
 573
 574       void build_permutation(InversePermutationMap next,
 575                              PermutationMap prev)
 576       {
 577         // collect the permutation info
 578         size_type i;
 579         for (i = 0; i < n; ++i) {
 580           diff_t size = supernode_size[get(index_vertex_map, i)];
 581           if ( size <= 0 ) {
 582             prev[i] = next[i];
 583             supernode_size[get(index_vertex_map, i)]
 584               = next[i] + 1;  // record the supernode info
 585           } else
 586             prev[i] = - next[i];
 587         }
 588         for (i = 1; i < n + 1; ++i) {
 589           if ( prev[i-1] > 0 )
 590             continue;
 591           diff_t parent = i;
 592           while ( prev[parent - 1] < 0 ) {
 593             parent = - prev[parent - 1];
 594           }
 595
 596           diff_t root = parent;
 597           diff_t num = prev[root - 1] + 1;
 598           next[i-1] = - num;
 599           prev[root-1] = num;
 600
 601           parent = i;
 602           diff_t next_node = - prev[parent - 1];
 603           while (next_node > 0) {
 604             prev[parent-1] = - root;
 605             parent = next_node;
 606             next_node = - prev[parent - 1];
 607           }
 608         }
 609         for (i = 0; i < n; i++) {
 610           diff_t num = - next[i] - 1;
 611           next[i] = num;
 612           prev[num] = i;
 613         }
 614       } // build_permutation()
 615     };
 616
 617   } //namespace detail
 618
 619
 620   // MMD algorithm
 621   //
 622   //The implementation presently includes the enhancements for mass
 623   //elimination, incomplete degree update, multiple elimination, and
 624   //external degree.
 625   //
 626   //Important Note: This implementation requires the BGL graph to be
 627   //directed.  Therefore, nonzero entry (i, j) in a symmetrical matrix
 628   //A coresponds to two directed edges (i->j and j->i).
 629   //
 630   //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum
 631   //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19
 632   template<class Graph, class DegreeMap,
 633            class InversePermutationMap,
 634            class PermutationMap,
 635            class SuperNodeMap, class VertexIndexMap>
 636   void minimum_degree_ordering
 637     (Graph& G,
 638      DegreeMap degree,
 639      InversePermutationMap inverse_perm,
 640      PermutationMap perm,
 641      SuperNodeMap supernode_size,
 642      int delta,
 643      VertexIndexMap vertex_index_map)
 644   {
 645     detail::mmd_impl<Graph,DegreeMap,InversePermutationMap,
 646       PermutationMap, SuperNodeMap, VertexIndexMap>
 647       impl(G, num_vertices(G), delta, degree, inverse_perm,
 648            perm, supernode_size, vertex_index_map);
 649     impl.do_mmd();
 650     impl.build_permutation(inverse_perm, perm);
 651   }
 652
 653 } // namespace boost
 654
 655 #endif // MINIMUM_DEGREE_ORDERING_HPP