Posts Tagged ‘cycle’
Pollard Rho Brent Integer Factorization
Pollard Rho is an integer factorization algorithm, which is quite fast for large numbers. It is based on Floyd’s cycle-finding algorithm and on the observation that two numbers x and y are congruent modulo p with probability 0.5 after numbers have been randomly chosen.
Algorithm Input : A number N to be factorized Output : A divisor of N If x mod 2 is 0 return 2 Choose random x and c y = x g = 1 while g=1 x = f(x) y = f(f(y)) g = gcd(x-y,N) return g
Note that this algorithm may not find the factors and will return failure for composite n. In that case, use a different f(x) and try again. Note, as well, that this algorithm does not work when n is a prime number, since, in this case, d will be always 1. We choose f(x) = x*x + c. Here’s a python implementation :
def pollardRho(N): if N%2==0: return 2 x = random.randint(1, N-1) y = x c = random.randint(1, N-1) g = 1 while g==1: x = ((x*x)%N+c)%N y = ((y*y)%N+c)%N y = ((y*y)%N+c)%N g = gcd(abs(x-y),N) return g
In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd’s cycle-finding algorithm with the related Brent’s cycle finding method. It is quite faster than pollard rho. Here’s a python implementation :
def brent(N): if N%2==0: return 2 y,c,m = random.randint(1, N-1),random.randint(1, N-1),random.randint(1, N-1) g,r,q = 1,1,1 while g==1: x = y for i in range(r): y = ((y*y)%N+c)%N k = 0 while (k<r and g==1): ys = y for i in range(min(m,r-k)): y = ((y*y)%N+c)%N q = q*(abs(x-y))%N g = gcd(q,N) k = k + m r = r*2 if g==N: while True: ys = ((ys*ys)%N+c)%N g = gcd(abs(x-ys),N) if g>1: break return g
-fR0DDY
All Pair Shortest Path (APSP)
Question : Find shortest paths between all pairs of vertices in a graph.
Floyd-Warshall Algorithm
It is one of the easiest algorithms, and just involves simple dynamic programming. The algorithm can be read from this wikipedia page.
#define SIZE 31 #define INF 1e8 double dis[SIZE][SIZE]; void init(int N) { for (k=0;k<N;k++) for (i=0;i<N;i++) dis[i][j]=INF; } void floyd_warshall(int N) { int i,j,k; for (k=0;k<N;k++) for (i=0;i<N;i++) for (j=0;j<N;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } int main() { //input size N init(N); //set values for dis[i][j] floyd_warshall(N); }
We can also use the algorithm to
- find the shortest path
- we can use another matrix called predecessor matrix to construct the shortest path.
- find negative cycles in a graph.
- If the value of any of the diagonal elements is less than zero after calling the floyd-warshall algorithm then there is a negative cycle in the graph.
- find transitive closure
- to find if there is a path between two vertices we can use a boolean matrix and use and-& and or-| operators in the floyd_warshall algorithm.
- to find the number of paths between any two vertices we can use a similar algorithm.
NJOY!!
-fR0DDY
Number of Cycles in a Graph
Question : Find the number of simple cycles in a simple graph.
Simple Graph – An undirected graph that has no loops and no more than one edge between any two different vertices.
Simple Cycle – A closed (simple) path, with no other repeated vertices or edges other than the starting and ending vertices.
Given a graph of N vertices and M edges, we will look at an algorithm with time complexity O(2NN2). We will use dynamic programming to do so. Let there be a matrix map, such that map[i][j] is equal to 1 if there is a edge between i and j and 0 otherwise. Let there be another array f[1<<N][N] which denotes the number of simple paths.
Let, i denote a subset S of our vertices k be the smallest set bit of i then f[i][j] is the number of simple paths from j to k that contains vertices only from the set S.
In our algorithm first we will find f[i][j] and then check if there is a edge between k and j, if yes, we can complete every simple path from j to k into a simple cycle and hence we add f[i][j] to our result of total number of simple cycles.Now how to find f[i][j].
For very subset i we iterate through all edges j. Once we have set k, we look for all vertices 'l' that can be neighbors of j in our subset S. So if l is a vertex in subset S and there is edge from j to l then f[i][j] = f[i][j] + the number of simple paths from l to i in the subset {S – j}. Since a simple graph is undirected or bidirectional, we have counted every cycle twice and so we divide our result by 2. Here's a sample C++ code which takes N, M and the edges as input.
#include<iostream> using namespace std; #define SIZE 20 bool map[SIZE][SIZE],F; long long f[1<<SIZE][SIZE],res=0; int main() { int n,m,i,j,k,l,x,y; scanf("%d%d",&n,&m); for (i=0;i<m;i++) { scanf("%d%d",&x,&y); x--;y--; if (x>y) swap(x,y); map[x][y]=map[y][x]=1; f[(1<<x)+(1<<y)][y]=1; } for (i=7;i<(1<<n);i++) { F=1; for (j=0;j<n;j++) if (i&(1<<j) && f[i][j]==0) { if (F) { F=0; k=j; continue; } for (l=k+1;l<n;l++) { if (i&(1<<l) && map[j][l]) f[i][j]+=f[i-(1<<j)][l]; } if (map[k][j]) res+=f[i][j]; } } printf("%lld\n",res/2); }
NJOY!
-fR0DDY