Simulation for Applied Graph Theory Using Visual C++ has been written to promote the use of Visual C++ in scientific computing. C++ is a beautiful language that has been responsible for shaping the modern world today. The language has contributed to many device drivers in electronic equipment and serves as the main engine in much of today's great software, and as a tool for research, teaching, and learning.
Graph theory is a diverse area of mathematics that deals with the abstraction of problems into mathematical structures called graphs that consist of objects and the pairwise interaction between the objects. A typical engineering problem, for example, involves thousands of interacting objects and finds its solution by first modeling its form into a graph. For example, there are many interacting variables to consider in designing the traffic flow of the streets in a big city, and reducing the problem into a graph simplifies the whole solution. Most real-world problems are nonlinear in nature and they have many interacting variables. One step in its solution is the reduction of the problem into a graph which helps in producing the solution by applying the properties of the graph.
Many problems involving graph theory are nondeterministic polynomial (NP) time-complete where the solutions have exponential complexities as the sizes of the problems grow. The solutions often involve tedious and massive calculations that may not be possible without the use of a computer. Simulations on a computer are essential and, therefore, good techniques in programming contribute to good solutions. C++ is an excellent choice to do the simulations due to its support for object-oriented programming and high-performance numeric support.
This book will help graduate and undergraduate students, who are interested, to work on simulation problems on applied graph theory. The book has been written with the main objective of teaching simulation using the C++ programming language and applying it to some common problems in graph theory. It is our aim to promote C++ as a language for numerical simulation and modeling. C++ has all the necessary ingredients for numerical computing due to its flexible language format, its object-oriented methodology, and its support for high numerical precisions. Due to stiff competition, in the past C++ popularity has suffered from the emergence of several new languages such as Java and C#. These new languages have been developed with the main objective to handle web and network programming requirements. However, due to its flexibility, C++ is still dominant and widely practiced.
This book will not duplicate other good books in the market today that mostly touch on the fundamental concepts of graph theory. Many such books have algorithmic approaches for the topic, while some even include C++ programming in its simulation approach. In this book, we integrate simulation with visualization through user-friendly interfaces using Visual C++ for some of the most common graph theoretical problems. Simulation is an important component of any research and it is performed either through a primary language like C++, C#, and Java, or through a secondary language like MATLAB® and Mathematica. A good applied researcher is somebody who is strong in both the development of new findings and simulation for verifying the findings. This book works on these requirements to help in the simulation for project development involving graph theory.
Graph theory and C++ are two separate and diverse areas. It will not be possible to discuss all topics in graph theory in a single book. We selected some of the most common: introductory concepts in Chapter 1, graph creation using C++ in Chapter 2, graph coloring in Chapter 3, shortest path problem in Chapter 4, minimum spanning tree in Chapter 5, maximum clique problem in Chapter 6, and graph triangulation in Chapter 7. To benefit researchers who are doing work on applied areas we also include some selected applications of graph theory in Chapters 8, 9, and 10. The chapters should provide the reader with good simulation skills and working examples for producing good simulation work on applied graph theory areas such as optimization and network design.
In completing the work on this book, the authors would like to thank several people whose involvement have directly or indirectly contributed in its preparation. We thank Prof. Datuk Ir. Dr. Wahid Omar, vice chancellor of Universiti Teknologi Malaysia and Prof. Datuk Dr. Shahrin Sahib, vice chancellor of Universiti Teknikal Malaysia Melaka for their strong policy of encouraging publication through book writing. We thank our colleagues at Universiti Teknologi Malaysia: Norsarahaida Mohd. Amin, Zainal Abdul Aziz, Rohanin Ahmad, Ali Selamat, Ali Hassan, Zaitul Marlizawati, Arifah Bahar, Norzieha Mustapha, and K. Visvanathan. Special thanks are due to our colleagues at Universiti Teknikal Malaysia Melaka who provided support and encouragement: Burairah Hussin, Zaheera Zainal Abidin, Abdul Samad Shibghatullah, Ahmad Fadzli Nizam Abdul Rahman and Mohamad Raziff Ramli. We also extend our thanks to our research friends, Prof. Dr. Albert Zomaya of University of Sydney, Australia, Prof. Dr. K.L. Teo of Curtin University, Australia, Prof. Dr. Stephan Olariu of Old Dominion University, the United States, and Dr. Ismail Khalil of Johannes Kepler University, Austria.
Additional material is available from the CRC website: http://www.crcpress.com/product/isbn/9781498721011.

Preface xi

Authors xiii

1. Graph Theory 1

1.1 Introductory Concepts 1

      1.1.1 Paths in a Graph 5

      1.1.2 Subgraph 6

      1.1.3 Tree 7

1.2 Spectral Graph Theory 9

2. Visualization with MFC 11

2.1 Windows Programming 11

2.2 Microsoft Foundation Classes 13

      2.2.1 Windows Interface Design 14

      2.2.2 Color Management 15

      2.2.3 Device Context 16

2.3 Writing the Simplest Windows Program 17

      2.3.1 Initializing an Application with Windows 18

      2.3.2 Creating the Main Window 18

      2.3.3 Displaying a Text Message 18

      2.3.4 Code2A: Skeleton Program 18

2.4 Windows Resources for Text and Graphics 21

      2.4.1 Setting Up the Device Context 22

      2.4.2 Formatted Text Output 22

      2.4.3 Setting the Pen Color 23

      2.4.4 Defining a Point in Windows 23

      2.4.5 Plotting a Point in Windows 23

      2.4.6 Drawing a Line 23

      2.4.7 Drawing a Polygon 24

      2.4.8 Drawing an Empty Rectangle 25

      2.4.9 Drawing a Solid-Filled Color Rectangle 25

      2.4.10 Drawing an Ellipse 26

      2.4.11 Drawing a Circle 26

      2.4.12 Clearing a Portion of Window 27

      2.4.13 Clearing the Whole Window 27

      2.4.14 Code2B: Graphics Drawing 27

2.5 Event and Event Handler 31

2.6 Windows Control Resources 33

      2.6.1 Edit Box 33

      2.6.2 Static Box 34

      2.6.3 Push Button 35

      2.6.4 List View Window 36

2.7 Displaying a Graph 37

      2.7.1 Designing the Work Area 38

      2.7.2 Data Structure of a Graph 39

      2.7.3 Random Placement of Nodes 39

      2.7.4 Code2C: Displaying a Graph 40

2.8 Hexagonal Network 45

      2.8.1 Code2D: Designing a Hexagonal Network 47

3. Graph Coloring 59

3.1 Background 59

3.2 Node Coloring Problem 61

      3.2.1 Node Coloring and Eigenvalues 62

      3.2.2 Power Method for Finding the Most Dominant Eigenvalue 63

      3.2.3 Code3A: Power Method for Estimating the Chromatic Number 64

3.3 Greedy Algorithm 70

      3.3.1 Code3B: Node Coloring Using a Greedy Algorithm 71

3.4 Channel Assignment on Wireless Mesh Networks 78

      3.4.1 Problem Statement 79

      3.4.2 Code3C: Constrained Single-Channel Assignment 80

4. Computing the Shortest Path 89

4.1 Problem Description 89

4.2 Single-Source Shortest Path Problem 91

      4.2.1 Dijkstra's Algorithm 92

      4.2.2 Code4A: Implementing Dijkstra's Algorithm 94

4.3 Floyd-Warshall's Method for the All-Pairs Shortest Paths 101

      4.3.1 Code4B: Implementing Floyd-Warshall's Algorithm 102

4.4 Mini-GPS 110

      4.4.1 Code4C: Implementing the Mini-GPS 111

4.5 Multicolumn Interconnection Network 119

      4.5.1 Code4D: Multicolumn Interconnection Network 121

5. Computing the Minimum Spanning Tree 133

5.1 Problem Description 133

5.2 Algorithms for Computing Minimum Spanning Tree 134

      5.2.1 Kruskal's Algorithm 134

      5.2.2 Prim's Algorithm 136

      5.2.3 Code5A: Kruskal's Algorithm 139

5.3 Case Study of the Pavement Construction Problem 148

      5.3.1 Code5B: Pavement Construction 148

5.4 Case Study of a Broadcasting Problem 156

      5.4.1 Code5C: Broadcasting Problem 159

6. Computing the Maximum Clique 171

6.1 Problem Description 171

      6.1.1 Greedy Algorithm for Finding the Maximum Clique 172

      6.1.2 Code6A: Implementing the Greedy Algorithm 177

6.2 Computing the Multiple Cliques of a Graph 184

      6.2.1 Greedy Algorithm for Finding the Multicliques 184

      6.2.2 Code6B: Implementing the Greedy Algorithm 187

6.3 Application of Clustering for Social Networking 193

      6.3.1 Code6C: Social Network Application 196

7. Triangulation Application 203

7.1 Convex Hull 203

7.2 Algorithms for Computing the Convex Hull 205

      7.2.1 Gift Wrapping Algorithm 205

      7.2.2 Graham's Scan Algorithm 205

      7.2.3 Onion Peeling Algorithm 208

      7.2.4 Code7A: Onion Peeling and Graham's Scan 210

7.3 Delaunay Triangulation 217

      7.3.1 Triangulating a Set of Points 219

      7.3.2 Delaunay's Gift Wrapping Algorithm 222

      7.3.3 Bowyer-Watson's Algorithm 223

      7.3.4 Code7B: Implementing Delaunay's Gift Wrapping Algorithm 226

8. Scheduling Application 233

8.1 Scheduling Problem 233

      8.1.1 Gantt Chart 236

8.2 Dynamic Job Scheduling 237

      8.2.1 Scheduling Model 238

      8.2.2 Code8A: Dynamic Machine Scheduling 239

8.3 Task Scheduling on Multiprocessor Systems 249

      8.3.1 Multiprocessor Systems 250

      8.3.2 Task Graph 251

      8.3.3 Code8B: Task Scheduling on a Four-Processor System 255

9. Target Detection Application 271

9.1 Target Detection Problem 271

9.2 Target Detection Using Radar and Antennas 272

      9.2.1 Transmission Models 273

      9.2.2 Code9A: Centralized Target Detection 275

9.3 Wireless Sensor Networks 284

      9.3.1 Problems in Wireless Sensor Networks 286

      9.3.2 Target Coverage Problem and Its Graph Model 287

      9.3.3 Code9B: Directional Sensors for Distributed Target Detection 288

10. Network Routing Application 299

10.1 Network Routing Problem 299

10.2 Routing in a Reconfigurable Mesh Network 299

      10.2.1 Code10A: Bus Drawing in a Mesh Network 301

10.3 Single-Row Routing 311

      10.3.1 Code10B: Realizing Single-Row Routing 315

References 331

Index 335

Zuraida Abal Abas is currently a senior lecturer at the Department of Industrial Computing, Faculty of Information and Communication Technology, Universiti Teknikal Malaysia Melaka. She obtained her PhD in mathematics at Universiti Teknologi Malaysia; her MSc in operational research at London School of Economics, United Kingdom; and her BSc in industrial mathematics at Universiti Teknologi Malaysia. Her research interests are operational research, applied graph theory, modeling, and simulation.

中科院文献情报中心