Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

Graph Theory in an Object Oriented Approach

Dixit Prasanna Kumar*, Sahoo Archana, Badajena Tushar Kumar

Director, Interface Software, Bhubaneswar

Abstract: Many real world situations can be describe by means of a diagram consisting of set of points connected by lines. Graph theory has many applications in different field. This paper show how various elements involved in graph theory including graph representations using computer system such as object oriented concept.

Keywords: Graph, vertex, edge, weighted graph, breadth first search

Citation: Dixit Prasanna Kumar, Sahoo Archana, Badajena Tushar Kumar, Graph Theory in an Object Oriented Approach. Journal of Computer Sciences and Applications, 3 (6). 123-126. January 2015. doi:10.12691/jcsa-3-6-2

1. Introduction

Graphs can be used to template many situations or problems in the real world, for example: the problem to find the path for a single walk can be modeled using a graph, where vertices represent cities and edges represent the roads, as shown in Figure 1.

Figure 1. A graph can be used to find the path between the districts

Other examples are:

•  the cities in a country and the streets that connect them;

•  telecommunication networks, like the Internet and the World Wide Web;

•  mathematical relationships like Fibonacci expansions using trees;

•  decisions trees and Bayesian networks;

•  project management, to manage dependencies between tasks;

•  bioinformatics: protein-protein interaction, residue interaction network, gene regulation;

•  electronic circuits: Kirchhoff laws are deeply related with the graph structure of circuits;

2. Review of Literature

2.1. A.K.Rath and A.K.Jagadev’s Procedure

According to the author the graphs are helps for solving a complex problem. There are many examples like find out the shortest path in a city from one area to another. BFS and DFS are two algorithms which are use for finding a path, without repeat the edge [1].

2.2. Y. Daniel Liang’s Procedure

According to the author the graph theoretical ideas can develop in 1736, when Leonard Euler published his paper based on the problem of Seven Bridges of Konigsberg [2]. This problem asks whether there is a continuous path that crosses each bridge only once. In graph, different terminologies are present and also their representation.

2.3. Bondy and Murty’s Procedure

According to the author the graph theory has found many applications in engineering and science.So many books have been published such as by Bondy and Murty. In real world situations can be described, diagram consisting of a set of points together with lines joining certain pairs of these points [3]. Bondy and Murty are both stressed the importance of efficient methods of solving problem. Several good algorithms are include and their efficiencies are analyzed.

2.4. Tero Harju’s Procedure

According to the author the graph theory can found in 1736 when Euler solve the Konigsberg bridge problem. Does there exist a walk crossing each of the seven bridges exactly once? There are no standard notations for graph theoretical objects. This is natural, because the names one uses for the objects reflect the applications.

2.5. Keijo Ruohonen’s Procedure

According to the author the graph is formed by vertices and edges connecting the vertices. Each vertex is indicated by a point and each edge by a line joining the points. There are various types of graphs present with own definitions such as simple graph, direct or indirect graph, weighted or unweighted graph and so on [5].

3. Graph Theory

Graph theory is useful in a graph problem, where a vertex can represent regions and the edges represent movement paths, or movement between the regions. In 1736 Leonard Euler was founded graph theory, when he solve the famous Seven Bridges of Konigsberg problem: Does there exist a walk crossing each of the seven bridges of Konigsberg exactly once? The Pregel river surrounding two central islands, as shown in Figure 2(a).

I1 and I2 are two islands, and P1 and P2 are the cities. Euler’s proof that no such path exists.

Proof: Euler First abstracted the city map into the sketch shown in Figure 2(a). Second, he replace city and islands with a dot, called vertex or a node, and each bridge with a line, called an edge, as shown in Figure 2(b). This structure with vertices and edges called graph.

Figure 2. Seven bridges connected islands and city http://upload.wikimedia.org/wikipedia/com mons/5/5d/Konigsberg_bridges.png

Let start a walk form any vertex, traversing all edges exactly once and return to the starting vertex. Euler proved that for such path to exist, each vertex must have an even number of edges. Therefore, this problem has no solution.

3.1. What is graph?

A graph is a mathematical structure that represents relationships among entities or objects in the real world, or graphs are represented graphically by drawing a dot or circle for vertex and drawing an arc or line between two vertices for edge. For example, the graph is fig 1 represents the roads and their distances among cities.

A graph is consists of a nonempty set of vertices, nodes and a set of edges that connect the vertices. For convenience, we define a graph as G = (V, E). where V represents a set of vertices E represents a set of edges For example, V and E for the graph in Figure 1 are:

V = {“Balangir”, “Sonapur”, “Bauda”, “Phulabani”, “Baragarh”, “Sambalpur”, “Jharasuguda”, “Sundargarh”, “Deogarh”, “Anugul”};

E = {{“Balangir”, “Sonapur”}, {“Sonapur”, “Bauda”}, {“Bauda”, “Phulabani”}, {“Balangir”, “Baragarh”}, { “Baragarh”, “Sambalpur”}, {“Sambalpur”,

“Jharasuguda”}, {“Sambalpur”, “Deogarh”}, {“Deogarh”, “Anugul”}, …};

3.1.1. Classification of graph

A graph is basically two types:

directed graph and undirected.

In a directed graph, each edge has a direction, which indicates that you can move from one vertex to the other through the edge. It is unidirectional in nature as shown in Figure 3(a).

In an undirected graph, you can move in both directions between vertices that is bidirectional in nature as shown in Figure 3(b).

Figure 3. Graphs in many forms

Edges may be weighted or unweighted. For example, each edge in the graph in Figure 3(c) has a weight that represents the distance between two nodes.

A complete graph is the one in which every two pairs of vertices are connected as shown in Figure 3(d).

A loop is an edge that links a vertex to itself. If two vertices are connected by two or more edges, these edges are called parallel edges as shown in Figure 3(e).

A simple graph is one that has no loops and parallel edges as shown in Figure 3(f).

3.1.2. Representing Vertices

The vertices can be store in an array. For example, you can store all the district names in the graph in fig 1 using array like:

String[ ] vertices = {“Balangir”, “Sonapur”, “Bauda”, “Phulabani”, “Baragarh”, “Sambalpur”, “Jharasuguda”, “Sundargarh”, “Deogarh”, “Anugul”};

The vertices can be objects of any type. For example, you may consider districts as objects that contain the information such as name, population, MLA, etc. Then all the objects are store in an array of object.

POJO CLASS

Object Graph Controller

All the vertex(district) are map to the District class. In Distance class, name and population are the variable of object in District class. So after mapping all the district name (anugul, sonapur, etc) becomes object of District class and object store in Bean factory. The variable of Edge class is vertex that means District class objects are variable of Edge class. The POJO class contains all the getter, setter method. In BFS class, we found the searching order of vertices.

This image shows these are two vertex or object in District class, and connecting both form a edge or edge object in Edge class.

3.1.3. Representing Edges

Edge array:

The edge can be represented using a two-dimensional array. For example, to represent the edges in the graph in Figure 1.

List of edge objects:

To represent the edges is to define edges as objects and store the edges in a java.util.ArrayList. For example, to represent the edges in the graph in Figure 1.

4. Conclusion

In this paper, the view point of vertex and edge connectivity is introduced. Graph theory is a deep area for programmers. It can be used to solve complex problems. Graph theory is difficult to understand and also for implement. If we implement it by using object oriented approach then it will be easy to implement.

References

[1]   | A.K. Rath, A.K. Jagadev, “Data Structures using C”, 2007.
[2]   | Y. Daniel Liang, “Introduction to Java Programming”, 2010.
[3]   | Tero Harju, “GRAPH THEORY”, University of Turku, Finland, 1994-2011.
[4]   | J. A. Bondy, U. S. Murty, “Graph Theory with Application”, University of Waterloo, Canada, 1976.
[5]   | Keijo Ruohonen, “Graph Theory”, 2013.