01-05-2013, 04:05 PM
A MINI PROJECT REPORT ON MINIMUM SPANNING TREE
MINIMUM SPANNING.docx (Size: 510.67 KB / Downloads: 34)
INTRODUCTION
Computer Graphics:
Computer graphics is concerned with all aspects of producing pictures or images using a computer. The field began humbly almost 50 years ago, with the display of a few lines on a cathode-ray-tube (CRT). Now we can create images by computers that are indistinguishable from photographs of real objects. One of the software used is OpenGL..
Three-dimensional graphics have many uses in modern computer applications. Applications for real-time 3D graphics range from interactive games and simulations to data visualization for scientific, medical, or business fields. Higher-end 3D graphics find their way into movies and technical and educational publications as well.
AIM OF THE PROJECT:
The aim of this project is to construct a minimum spanning tree from an undirected cyclic graph.
A spanning tree is a tree in which all the nodes are connected without forming a loop.
A graph will have only one minimum spanning tree if and only if the weights associated with all the edges in the graph are distinct.
OpenGL:
Open graphics library is a standard specification defining a cross platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex 3D scenes and simple primitives.
OpenGL is widely used in CAD, vertical reality, scientific visualization, flight simulation and video games. OpenGL specifies a set of commands or immediately executes functions. Each command directs a drawing action or causes a special effect. A list of these commands can be created by repetitive effects.
OpenGL is independent of windowing characteristics of each operating system. But provides special GLU routines for each operating system that enables OpenGL to work with the system’s windowing environment.
OpenGL comes with a large number of building capabilities. These include hidden surface removal, alpha blending, antialiasing, texture mapping, pixel operation, viewing, modeling transformation and atmospheric effects. Functions in the OpenGL library have names that begin with the letters GL and are stored in a library usually referred to as GL. The second is the OpenGL utility library (GLU).this library uses only GL functions in GLU can be created from the core GL library.
HOW TO IMPLEMENT:
Kruskal’s algorithm–This algorithm selects n-1 edges one at a time. The Algorithm selects the least cost edge from a set of edges and deletes the edge from the set. Then it checks whether the selected edge results in a cycle when added to the list of already selected edges to form a minimum Spanning Tree. If no cycles are formed, the selected edge is added to the list of edges selected to form a minimum spanning tree. The selected edge which results in a cycle is neglected. The procedure is repeated till all n-1 edges are selected and there are no more edges to consider. If n-1 edges are selected, the selected edges results in a minimum spanning tree, otherwise, spanning tree does not exist.
CODE DESCRIPTION:
The aim of this program is to compute the minimum spanning tree for a given graph. The graph is cyclic, weighted and undirected. A weighted graph is the one in which cost (weight) of each edge is specified.
The first thing to be done is to include the header files and make all the declarations. In the declarations section, we have variables which are used to store the values when any keyboard event occurs.
Now we start with the main function, here, the GLUT library is initialized and the display and keyboard callback are set. Also, the window is created and its name, size and position are specified.
Next is the display function (display) callback in which we call the function to display the first page. On the first page the project name is given and a message saying “press enter to continue”. When the user presses the enter key, control goes to the keyboard function where another function is called to display the menu.
CONCLUSION
Our objective of computing the minimum spanning tree for a graph is completed. This mini project gave us a means for better understanding of the OpenGL concept through its practical implementation.
I had a great experience in the course of designing this package. This project on “Minimum Spanning Tree” has helped me in learning and discovering many things as pertaining to the topic of OpenGL. We have tried our best potential to incorporate all the basic requirements of Linux OS through VMware in Windows OS.
It is user friendly. It enables the user to interact effectively and easily. This package has been implemented using optimized algorithm and thus is fast. Special attention has been provided to the interfaces that make its use comfortable. We hope this package proves to be flexible in all respect to one and all.