Month: March 2018

Programs in Python for BFS

Posted on Updated on

Breadth-first search (BFS) is an algorithm used for traversing graph data structures. BFS implements a specific strategy for visiting all the nodes (vertices) of a graph. BFS starts with a node, then it checks the neighbours of the initial node, then the neighbours of the neighbours, and so on.

I’ve created a connected graph with 7 nodes and 8 edges. The edges are undirected and unweighted.  Distance between two nodes will be measured based on the number of edges separating two vertices.   I use the adjacency list to represent the above graph. An effective/elegant method for implementing adjacency lists in Python is using dictionaries. The keys of the dictionary represent nodes, the values have a list of neighbours.


The following screen shot represents representation of the above graph and output shows the result of running Breadth First Search (BFS) algorithm.  Can you explain the output?  Can you write program in Python ?

Send your suggestions and comments to

Best answer will be rewarded.


Created and edited by Dr. Ashwin I Mehta  at Vissicomp Technology

Please check the schedule or reach at

For more details Call us @9320957718 / 17






De Moivre’s theorem

Posted on Updated on







2D Transformation ( Important Notes For 2nd year BSCIT SEM 4 )

Posted on Updated on

Composite Transformation:

We can set up a matrix for any sequence of transformations as a composite transformation matrix by calculating the matrix product of the individual transformations. Forming products of transformation matrices is often referred to as a concatenation, or composition, of matrices.


If two successive translation vectors (tx1, ty1 ) and (tx2, ty2) are applied to a coordinate position P, the final transformed location P’ is calculated as

P’= T (tx2, ty2) * {T (tx1,ty1) * P}

= {T (tx2, ty2) * T(tx1,ty1)} * P

where  P and P’ are represented as homogeneous-coordinate column vectors. We can verify this result by calculating the matrix product for the two associative groupings Also, the composite transformation matrix for this sequence of translation  is


T (tx2,ty2) * T(tx1,ty1) = T( tx1+tx2 , ty1+ty2)

which demonstrates  that two successive translation are additive.


Two successive rotations  applied to point P produce the transformed position

P’ = R(θ2) *{R(θ1) *P}

P’= {R(θ2) * R(θ1)} * P

By multiplying the two rotation matrices, we can verify that two successive rotations are addictive.

R(θ2)* R(θ1) = R(θ1 + θ2)

so that the final rotated coordinates can be calculated with the composite rotation matrix as

P’=R(θ1 + θ2) * P


Concatenating transformation matrices for two successive scaling operations produces the following composite scaling matrix:


The resulting matrix in this case indicates that successive scaling operations are multiplicative. That is, if we were to triple the size of an object twice in succession, the final size would be nine times that of the original.

General Fixed-Point Scaling


Above figure  illustrates a transformation sequence to produce scaling with respect to a selected fixed position (xf , yf) using a scaling function that can only scale relative to the coordinate origin.

  1. Translate object so that the fixed point coincides with the coordinate origin.
  2. Scale the object with respect to the coordinate origin.
  3. Use the inverse translation of step 1 to return the object to its original position

Concatenating the matrices for these three operations produces the required scaling matrix:


The transformation is automatically generated on systems that provide a scale function that accepts coordinates for the fixed point.

General Scaling Directions

Parameters s1 and s2 scale objects along the x and y directions. We can scale an object in other directions by rotating the object to align the desired scaling directions with the coordinate axes before applying the scaling transformation.

To accomplish the scaling without changing the orientation of the object, we first perform a rotation so that the directions for s, and s2 coincide with the x and y axes, respectively. Then the scaling transformation is applied, followed by an opposite rotation to return points to their original orientations.


The composite matrix resulting from the product of these three transformations is


Concatenation Properties

Matrix multiplication is associative. For any three matrices, A, B, and C, the matrix product A *B *C can be performed by first multiplying A and B or by first multiplying B and C:

                                A*B*C= (A*B)*C  = A*(B*C)

Therefore, we can evaluate matrix products using either a left-to-right or a right to left associative grouping. On the other hand, transformation products may not be commutative: The matrix product A. B is not equal to B – A, in general. This means that if we want to translate and rotate an object, we must be careful about the order in which the composite matrix is evaluated . For some special cases, such as a sequence of transformations all of the same kind, the multiplication of transformation matrices is commutative. As an example, two successive rotations could be performed in either order and the final position would be the same. This commutative property holds also for two successive translations or two successive scaling. Another commutative pair of operations is rotation and uniform scaling (sx  ,sy).


Basic transformations such as translation, rotation, and scaling are included in most graphics packages. Some packages provide a few additional transformations that are useful in certain applications. Two such transformations are reflection and shear.


A reflection is a transformation that produces a mirror image of an object. The mirror image for a two-dimensional reflection is generated relative to an axis of reflection by rotating the object 180″ about the reflection axis.

Reflection about the line y = 0, the x axis, is accomplished with the transformation matrix


A reflection about the y axis flips x coordinates while keeping y coordinates the same. The matrix for this transformation is


Reflection about origin

We flip both the x and y coordinates of a point by reflecting relative to an axis that is perpendicular to the xy plane and that passes through the coordinate origin. This transformation, referred to as a reflection relative to the coordinate origin, has the matrix representation


Reflection axis as the diagonal line y = x

If we chose the reflection axis as the diagonal line y = x (Fig. 5-20), the reflection matrix is


Reflection about the diagonal y = -x

To obtain a transformation matrix for reflection about the diagonal y = -x, we could concatenate matrices for the transformation sequence:


Reflections about any line y = mx  + b in the xy plane can be accomplished with a combination of translate-rotate-reflect transformations. In general, we first translate the Line so that it passes through the origin. Then we can rotate the line onto one of the coordinate axes and reflect about that axis. Finally, we restore the line to its original position with the inverse rotation and translation transformations.


A transformation that slants the shape of the object is called shear transformation. Two common shearing transformations are used.

X shear

The X shear preserves the y coordinates, but changes the x values which causes vertical lines to tilt right or left.


Any real number can be assigned to the shear parameter shx.  A coordinate position (x, y) is then shifted horizontally by an amount proportional to its distance (y value) from the x axis (y = 0). Setting shx to 2, for example, changes the square in Fig. 5-23 into a parallelogram. Negative values for shx shift coordinate positions to the left. We can generate x-direction shears relative to other reference lines with


Y Shear

The y shear preserves the x coordinates, but changes the y values which causes horizontal lines to transform into lines which slope up or down.


A y-direction shear relative to the line x = xref  is generated with the transformation matrix


Created By                                                                                          Edited By

Ankita Bamania                                                                                Ashwin mehta

You can contact us. 9320957718 / 17