Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

r""" 

Compact structure for fast operations on less than 32 vertices 

  

This module implements a digraph structure meant to be used in Cython in 

**highly enumerative** algorithms. It can store graphs on less than 

``sizeof(int)`` vertices and perform several basic operations **quickly** 

(add/remove arcs, count the out-neighborhood of a set of vertices or return its 

cardinality). 

  

**Sets and integers :** 

  

In the following code, sets are represented as integers, where the ith bit is 

set if element i belongs to the set. 

""" 

from __future__ import print_function 

  

from libc.stdint cimport uint8_t 

from cysignals.memory cimport check_allocarray, check_calloc, sig_free 

  

cdef class FastDigraph: 

  

def __cinit__(self, D): 

r""" 

Constructor for ``FastDigraph``. 

  

If the input parameter ``D`` is a Graph, it is handled as a symmetric 

DiGraph. 

""" 

if D.order() > 8*sizeof(int): 

raise OverflowError("Too many vertices. This structure can only encode digraphs on at most %i vertices"%(8*sizeof(int))) 

  

self.n = D.order() 

self.graph = <int *>check_calloc(self.n, sizeof(int)) 

  

cdef int i, j 

cdef int tmp 

  

# When the vertices are not consecutive integers 

cdef dict vertices_to_int = {} 

self.int_to_vertices = {} 

for i,v in enumerate(D.vertices()): 

vertices_to_int[v] = i 

self.int_to_vertices[i] = v 

  

if D.is_directed(): 

for u in D: 

tmp = 0 

for v in D.neighbors_out(u): 

tmp |= 1 << vertices_to_int[v] 

self.graph[vertices_to_int[u]] = tmp 

else: 

for u in D: 

tmp = 0 

for v in D.neighbors(u): 

tmp |= 1 << vertices_to_int[v] 

self.graph[vertices_to_int[u]] = tmp 

  

self.degree = <int *>check_allocarray(self.n, sizeof(int)) 

for i in range(self.n): 

self.degree[i] = popcount32(self.graph[i]) 

  

def __dealloc__(self): 

r""" 

Destructor. 

""" 

sig_free(self.graph) 

sig_free(self.degree) 

  

def print_adjacency_matrix(self): 

r""" 

Displays the adjacency matrix of ``self``. 

""" 

cdef int i,j 

for 0<= i<self.n: 

for 0<= j <self.n: 

print(((self.graph[i]>>j)&1), end="") 

print("") 

  

cdef inline int compute_out_neighborhood_cardinality(FastDigraph g, int S): 

r""" 

Returns the cardinality of `N^+(S)\S`. 

  

INPUT: 

  

- ``g`` a FastDigraph 

- S (integer) an integer describing the set 

""" 

cdef int i 

cdef int tmp = 0 

for i in range(g.n): 

tmp |= g.graph[i] & (-((S >> i)&1)) 

  

tmp &= (~S) 

return popcount32(tmp) 

  

cdef inline int popcount32(int i): 

""" 

Returns the number of '1' bits in a 32-bits integer. 

  

If sizeof(int) > 4, this function only returns the number of '1' 

bits in (i & ((1<<32) - 1)). 

""" 

i = i - ((i >> 1) & 0x55555555); 

i = (i & 0x33333333) + ((i >> 2) & 0x33333333); 

return ((i + (i >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24; 

  

  

# If you happened to be doubting the consistency of the popcount32 function 

# above, you can give the following doctest a try. It is not tested 

# automatically by Sage as it takes a *LONG* time to run (around 5 minutes), but 

# it would report any problem if it finds one. 

  

def test_popcount(): 

""" 

Correction test for popcount32. 

  

EXAMPLES:: 

  

sage: from sage.graphs.graph_decompositions.fast_digraph import test_popcount 

sage: test_popcount() # not tested 

""" 

cdef int i = 1 

# While the last 32 bits of i are not equal to 0 

while (i & ((1<<32) - 1)) : 

if popcount32(i) != slow_popcount32(i): 

print("Error for i = ", str(i)) 

print("Result with popcount32 : " + str(popcount32(i))) 

print("Result with slow_popcount32 : " + str(slow_popcount32(i))) 

i += 1 

  

  

cdef inline int slow_popcount32(int i): 

# Slow popcount for 32bits integers 

cdef int j = 0 

cdef int k 

  

for k in range(32): 

j += (i>>k) & 1 

  

return j