2 * Copyright (c) 2016 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 #include <vppinfra/ptclosure.h>
19 clib_ptclosure_alloc (int n)
27 vec_validate (rv, n - 1);
28 for (i = 0; i < n; i++)
31 vec_validate (row, n - 1);
39 clib_ptclosure_free (u8 ** ptc)
42 int n = vec_len (ptc);
47 for (i = 0; i < n; i++)
56 clib_ptclosure_copy (u8 ** dst, u8 ** src)
59 u8 *src_row, *dst_row;
63 for (i = 0; i < vec_len (dst); i++)
67 clib_memcpy (dst_row, src_row, n);
72 * compute the positive transitive closure
73 * of a relation via Warshall's algorithm.
76 * Warshall, Stephen (January 1962). "A theorem on Boolean matrices".
77 * Journal of the ACM 9 (1): 11–12.
79 * foo[i][j] = 1 means that item i
80 * "bears the relation" to item j.
82 * For example: "item i must be before item j"
84 * You could use a bitmap, but since the algorithm is
85 * O(n**3) in the first place, large N is inadvisable...
90 clib_ptclosure (u8 ** orig)
97 prev = clib_ptclosure_alloc (n);
98 cur = clib_ptclosure_alloc (n);
100 clib_ptclosure_copy (prev, orig);
102 for (k = 0; k < n; k++)
104 for (i = 0; i < n; i++)
106 for (j = 0; j < n; j++)
108 cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]);
111 clib_ptclosure_copy (prev, cur);
113 clib_ptclosure_free (prev);
120 * fd.io coding-style-patch-verification: ON
123 * eval: (c-set-style "gnu")