warshall.c 1.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
  1. #include "defs.h"
  2. transitive_closure(R, n)
  3. unsigned *R;
  4. int n;
  5. {
  6. register int rowsize;
  7. register unsigned mask;
  8. register unsigned *rowj;
  9. register unsigned *rp;
  10. register unsigned *rend;
  11. register unsigned *ccol;
  12. register unsigned *relend;
  13. register unsigned *cword;
  14. register unsigned *rowi;
  15. rowsize = WORDSIZE(n);
  16. relend = R + n*rowsize;
  17. cword = R;
  18. mask = 1;
  19. rowi = R;
  20. while (rowi < relend)
  21. {
  22. ccol = cword;
  23. rowj = R;
  24. while (rowj < relend)
  25. {
  26. if (*ccol & mask)
  27. {
  28. rp = rowi;
  29. rend = rowj + rowsize;
  30. while (rowj < rend)
  31. *rowj++ |= *rp++;
  32. }
  33. else
  34. {
  35. rowj += rowsize;
  36. }
  37. ccol += rowsize;
  38. }
  39. mask <<= 1;
  40. if (mask == 0)
  41. {
  42. mask = 1;
  43. cword++;
  44. }
  45. rowi += rowsize;
  46. }
  47. }
  48. reflexive_transitive_closure(R, n)
  49. unsigned *R;
  50. int n;
  51. {
  52. register int rowsize;
  53. register unsigned mask;
  54. register unsigned *rp;
  55. register unsigned *relend;
  56. transitive_closure(R, n);
  57. rowsize = WORDSIZE(n);
  58. relend = R + n*rowsize;
  59. mask = 1;
  60. rp = R;
  61. while (rp < relend)
  62. {
  63. *rp |= mask;
  64. mask <<= 1;
  65. if (mask == 0)
  66. {
  67. mask = 1;
  68. rp++;
  69. }
  70. rp += rowsize;
  71. }
  72. }