What is a spanning tree?

Spanning tree is an important field in both mathematics and computer science. Mathematically, we define a spanning tree T of an un-directed and connected graph G as a tree consisting of all the vertices and all or some edges of the graph G.

- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it. 

- This means that every vertex of graph G is present in the spanning tree but there are no loops or cycles. 

- Also, every bridge of the given graph must be present in its spanning tree. 

- We can even say that a maximal set of the graph G’s edges containing no cycle or a minimal set of the graph G’s vertices forms a spanning tree. 

- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph. 

- There are a number of other optimization problems that require using the minimum spanning trees and other types of spanning trees. 

The other types of spanning trees include the following:

Ø  Maximum spanning tree

Ø  An MST spanning at least k number of vertices.

Ø  An MST having at the most k number of edges per vertex i.e., the degree constrained spanning tree.

Ø  Spanning tree having the largest no. of leaves (this type of spanning tree bears a close relation with the “smallest connected dominating set”).

Ø  Spanning tree with the fewest number of leaves (this spanning tree bears a close relation with the “Hamiltonian path problem”).

Ø  Minimum diameter spanning tree.

Ø  Minimum dilation spanning tree.

- One characteristic property of the spanning trees is that they do not have any cycles. 

- This also means that if you add just an edge to the tree, a cycle will be created. 

- We call this cycle as the fundamental cycle. 

- For each edge in the spanning there exists a distinct fundamental cycle and therefore there arises a one – to – one correspondence among the edges that are not present and the fundamental cycles. 

- For a graph G that is connected and has V vertices, there are V-1 edges in its spanning tree. 

- Therefore, for a general graph composed of E edges, its spanning tree will have E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree these fundamental cycles are used. 

- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.  

- If we delete even one edge from the spanning tree, two disjoint sets will be formed of the vertices. 

- The set of the edges that if taken out from the graph G partitioning the vertices in to same disjoint sets is defined as the fundamental cut set. 

- For a given graph G there are V-1 fundamental cut sets i.e., one corresponding to each spanning tree edge. 

- The fact that the edges of the cycles that do not appear in the spanning tree but only in the cut sets of the edges can be used to establish the relationship between the cycles and the cut sets.

What is Spanning Forest?

- The sub-graph generalizing the spanning tree concept is called the spanning forest. 

- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.

- For counting the number of spanning trees for a complete graph the formula used is known as the cayley’s formula.

Explain unstructured loops in detail?

Loops are one of the most important of the languages like C and C++. They have greatly reduced the drudgery of the programmers and developers which would otherwise have made the programming of a software system or application more hectic. The necessity of the loops cannot be ignored when it comes to the repetition of a particular executable statement or a block of statements in a program. 

In other words,

Say we have the below written statement in C++ programming language that we need to print only one time:

“hello! Welcome to C++ programming”

To print it one time we shall write the code like this:

Cout<<”hello! Welcome to C++ programming\n”;

Say now you need to print this statement a 100 times! What you are going to do- write the above C++ statement a 100 times? No! Certainly not! This is unfeasible and a complete waste of time! So what is the alternative that we have? Yes of course we have the “loops”. 

Using loop we will have to write only a small code instead of writing that C++ statement again and again for 100 times. Using loop we shall write like this:

For( int i = 1; i <=100; i++ )

{

Cout<<”hello! Welcome to C++ programming\n”;

}

The above loop is a for loop and it will the statement that we wish to be printed 100 times. See to how much extent our task has been reduced! This would not have been possible without loops. 

Loops generally are classified based on their types namely in to:

1. The while loop
2. The for loop
3. The do – while loop

But based up on their structure, they are classified in to two types:

1. Structured loops and
2. Unstructured loops

This article is all about the unstructured loops. We shall discuss them in detail. 

The Unstructured Loops

- The unstructured loops can be defined as the loops that are void of a single header or a node in the control flow graph that has all the nodes dominating the whole loop body. 

- The main problem that arises with these unstructured loops is of managing them.

- Managing them is such a hectic task.

- For analyzing the unstructured loops the programmers, developers and researchers have come up with so many ways but none of them seems to be so efficient.

- One of the ways is to use a control flow graph along with the scope graph corresponding to the function containing the unstructured loop to be analyzed. 

- This method involves attaching of each and every iteration counter with each of the loop header.

- Attaching the iteration counters in such a way can cause over estimation of the control flow. 

- So to overcome this problem, the iteration counters are attached to each basic block and this helps a great deal in achieving a lot of flow information. Even this way results in some disadvantage! 

- Therefore another method of managing the unstructured loops has been developed. 

- Another method has been developed for transforming the unstructured loops in structured ones. 

- If one looks at the unstructured loop with a view of the control flow graph they seem to have entry edges to one or more than one node all over the loop. 

- In another way we can say that an unstructured consists of parts of several different loops. 

- Several structured loops can also be merged in to an unstructured loop with the help of a code size optimizing compiler.

- A straight way has been developed for the elimination of the unstructured loops which is creating a scope with a single header for each entry of the loop. 

What is Cyclomatic Complexity and how it is computed?

Cyclomatic complexity measures the amount of decision logic in a single software module. It provides a quantitative measure of the logical complexity of a program. It gives the number of recommended test for software. When used in the context of basis path testing method, the value computed for Cyclomatic complexity defines the number for independent paths in the basis set of a program and provides us an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.
An independent path is any path through the program that introduces at least one new set of processing statements or a new condition.

Control flow graphs describe the logic structure of software module. Each flow consists of nodes and edges. Nodes are computation statements or expresions.
Edges represent transfer of control between nodes.Each possible execution path of a software module has a corresponding path from the entry to the exit node of the module's control flow graph.

Computing Cyclomatic Complexity
Cyclomatic complexity has a foundation in graph theory and provides us with extremely useful software metric. Complexity is computed in one of the three ways:
- The number of regions of the flow graph corresponds to the cyclomatic complexity.
- Cyclomatic complexity, V(G), for a flow graph, G is defined as:
V(G)= E-N+2
where E is the number of flow graph edges and N is the number of flow graph nodes.
- Cyclomatic complexity, V(G) for a flow graph, G is also defined as:
V(G)= P+1
where P is the number of predicate nodes contained in the flow graph G.