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>
18 u8 ** clib_ptclosure_alloc (int n)
26 vec_validate (rv, n-1);
27 for (i = 0; i < n; i++)
30 vec_validate (row, n-1);
37 void clib_ptclosure_free (u8 ** ptc)
40 int n = vec_len (ptc);
45 for (i = 0; i < n; i++)
53 void clib_ptclosure_copy (u8 ** dst, u8 **src)
56 u8 * src_row, * dst_row;
60 for (i = 0; i < vec_len(dst); i++)
64 clib_memcpy (dst_row, src_row, n);
69 * compute the positive transitive closure
70 * of a relation via Warshall's algorithm.
73 * Warshall, Stephen (January 1962). "A theorem on Boolean matrices".
74 * Journal of the ACM 9 (1): 11–12.
76 * foo[i][j] = 1 means that item i
77 * "bears the relation" to item j.
79 * For example: "item i must be before item j"
81 * You could use a bitmap, but since the algorithm is
82 * O(n**3) in the first place, large N is inadvisable...
86 u8 ** clib_ptclosure (u8 ** orig)
93 prev = clib_ptclosure_alloc (n);
94 cur = clib_ptclosure_alloc (n);
96 clib_ptclosure_copy (prev, orig);
98 for (k = 0; k < n; k++)
100 for (i = 0; i < n; i++)
102 for (j = 0; j < n; j++)
104 cur[i][j] = prev[i][j] || (prev[i][k] && prev[k][j]);
107 clib_ptclosure_copy (prev, cur);
109 clib_ptclosure_free (prev);