Count the number of Prime Cliques in an undirected graph | Python3 implementation to Count the number of Prime Cliques in an undirected graph ; Stores the vertices ; Graph ; Degree of the vertices ; To store the count of prime cliques ; Function to create Sieve to check primes ; false here indicates that it is not prime ; Condition if prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to check if the given set of vertices in store array is a clique or not ; Run a loop for all set of edges ; If any edge is missing ; Function to find the count of all the cliques having prime size ; Check if any vertices from i + 1 can be inserted ; Add the vertex to store ; If the graph is not a clique of size k then it cannot be a clique by adding another edge ; Increase the count of prime cliques if the size of current clique is prime ; Check if another edge can be added ; Driver code
MAX = 100 NEW_LINE store = [ 0 for i in range ( MAX ) ] NEW_LINE n = 0 NEW_LINE graph = [ [ 0 for j in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE d = [ 0 for i in range ( MAX ) ] NEW_LINE ans = 0 NEW_LINE def SieveOfEratosthenes ( prime , p_size ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE p = 2 NEW_LINE while ( p * p <= p_size ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT for i in range ( p * 2 , p_size + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def is_clique ( b ) : NEW_LINE INDENT for i in range ( 1 , b ) : NEW_LINE INDENT for j in range ( i + 1 , b ) : NEW_LINE INDENT if ( graph [ store [ i ] ] [ store [ j ] ] == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT def primeCliques ( i , l , prime ) : NEW_LINE INDENT global ans NEW_LINE for j in range ( i + 1 , n + 1 ) : NEW_LINE INDENT store [ l ] = j NEW_LINE if ( is_clique ( l + 1 ) ) : NEW_LINE INDENT if ( prime [ l ] ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT primeCliques ( j , l + 1 , prime ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT edges = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 1 ] , [ 4 , 3 ] , [ 4 , 5 ] , [ 5 , 3 ] ] NEW_LINE size = len ( edges ) NEW_LINE n = 5 NEW_LINE prime = [ True for i in range ( n + 2 ) ] NEW_LINE SieveOfEratosthenes ( prime , n + 1 ) NEW_LINE for i in range ( size ) : NEW_LINE INDENT graph [ edges [ i ] [ 0 ] ] [ edges [ i ] [ 1 ] ] = 1 NEW_LINE graph [ edges [ i ] [ 1 ] ] [ edges [ i ] [ 0 ] ] = 1 NEW_LINE d [ edges [ i ] [ 0 ] ] += 1 NEW_LINE d [ edges [ i ] [ 1 ] ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE primeCliques ( 0 , 1 , prime ) NEW_LINE print ( ans ) NEW_LINE DEDENT