The tool for visualization is Microsoft Visual C++. This popular software has the standard C++ combined with the Microsoft Foundation Classes (MFC) libraries for Windows visualization. This book explains how to create a graph interactively, solve problems in graph theory with minimum number of C++ codes, and provide friendly interfaces that makes learning the topics an interesting one. Each topic in the book comes with working Visual C++ codes which can easily be adapted as solutions to various problems in science and engineering.
Author(s): Shaharuddin Salleh; Zuraida Abal Abas
Publisher: CRC Press
Year: 2016
Language: English
Pages: 339
Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
Preface
Authors
1. Graph Theory
1.1 Introductory Concepts
1.1.1 Paths in a Graph
1.1.2 Subgraph
1.1.3 Tree
1.2 Spectral Graph Theory
2. Visualization with MFC
2.1 Windows Programming
2.2 Microsoft Foundation Classes
2.2.1 Windows Interface Design
2.2.2 Color Management
2.2.3 Device Context
2.3 Writing the Simplest Windows Program
2.3.1 Initializing an Application with Windows
2.3.2 Creating the Main Window
2.3.3 Displaying a Text Message
2.3.4 Code2A: Skeleton Program
2.4 Windows Resources for Text and Graphics
2.4.1 Setting Up the Device Context
2.4.2 Formatted Text Output
2.4.3 Setting the Pen Color
2.4.4 Defining a Point in Windows
2.4.5 Plotting a Point in Windows
2.4.6 Drawing a Line
2.4.7 Drawing a Polygon
2.4.8 Drawing an Empty Rectangle
2.4.9 Drawing a Solid-Filled Color Rectangle
2.4.10 Drawing an Ellipse
2.4.11 Drawing a Circle
2.4.12 Clearing a Portion of Window
2.4.13 Clearing the Whole Window
2.4.14 Code2B: Graphics Drawing
2.5 Event and Event Handler
2.6 Windows Control Resources
2.6.1 Edit Box
2.6.2 Static Box
2.6.3 Push Button
2.6.4 List View Window
2.7 Displaying a Graph
2.7.1 Designing the Work Area
2.7.2 Data Structure of a Graph
2.7.3 Random Placement of Nodes
2.7.4 Code2C: Displaying a Graph
2.8 Hexagonal Network
2.8.1 Code2D: Designing a Hexagonal Network
3. Graph Coloring
3.1 Background
3.2 Node Coloring Problem
3.2.1 Node Coloring and Eigenvalues
3.2.2 Power Method for Finding the Most Dominant Eigenvalue
3.2.3 Code3A: Power Method for Estimating the Chromatic Number
3.3 Greedy Algorithm
3.3.1 Code3B: Node Coloring Using a Greedy Algorithm
3.4 Channel Assignment on Wireless Mesh Networks
3.4.1 Problem Statement
3.4.2 Code3C: Constrained Single-Channel Assignment
4. Computing the Shortest Path
4.1 Problem Description
4.2 Single-Source Shortest Path Problem
4.2.1 Dijkstra’s Algorithm
4.2.2 Code4A: Implementing Dijkstra’s Algorithm
4.3 Floyd-Warshall’s Method for the All-Pairs Shortest Paths
4.3.1 Code4B: Implementing Floyd-Warshall’s Algorithm
4.4 Mini-GPS
4.4.1 Code4C: Implementing the Mini-GPS
4.5 Multicolumn Interconnection Network
4.5.1 Code4D: Multicolumn Interconnection Network
5. Computing the Minimum Spanning Tree
5.1 Problem Description
5.2 Algorithms for Computing Minimum Spanning Tree
5.2.1 Kruskal’s Algorithm
5.2.2 Prim’s Algorithm
5.2.3 Code5A: Kruskal’s Algorithm
5.3 Case Study of the Pavement Construction Problem
5.3.1 Code5B: Pavement Construction
5.4 Case Study of a Broadcasting Problem
5.4.1 Code5C: Broadcasting Problem
6. Computing the Maximum Clique
6.1 Problem Description
6.1.1 Greedy Algorithm for Finding the Maximum Clique
6.1.2 Code6A: Implementing the Greedy Algorithm
6.2 Computing the Multiple Cliques of a Graph
6.2.1 Greedy Algorithm for Finding the Multicliques
6.2.2 Code6B: Implementing the Greedy Algorithm
6.3 Application of Clustering for Social Networking
6.3.1 Code6C: Social Network Application
7. Triangulation Application
7.1 Convex Hull
7.2 Algorithms for Computing the Convex Hull
7.2.1 Gift Wrapping Algorithm
7.2.2 Graham’s Scan Algorithm
7.2.3 Onion Peeling Algorithm
7.2.4 Code7A: Onion Peeling and Graham’s Scan
7.3 Delaunay Triangulation
7.3.1 Triangulating a Set of Points
7.3.2 Delaunay’s Gift Wrapping Algorithm
7.3.3 Bowyer-Watson’s Algorithm
7.3.4 Code7B: Implementing Delaunay’s Gift Wrapping Algorithm
8. Scheduling Application
8.1 Scheduling Problem
8.1.1 Gantt Chart
8.2 Dynamic Job Scheduling
8.2.1 Scheduling Model
8.2.2 Code8A: Dynamic Machine Scheduling
8.3 Task Scheduling on Multiprocessor Systems
8.3.1 Multiprocessor Systems
8.3.2 Task Graph
8.3.3 Code8B: Task Scheduling on a Four-Processor System
9. Target Detection Application
9.1 Target Detection Problem
9.2 Target Detection Using Radar and Antennas
9.2.1 Transmission Models
9.2.2 Code9A: Centralized Target Detection
9.3 Wireless Sensor Networks
9.3.1 Problems in Wireless Sensor Networks
9.3.2 Target Coverage Problem and Its Graph Model
9.3.3 Code9B: Directional Sensors for Distributed Target Detection
10. Network Routing Application
10.1 Network Routing Problem
10.2 Routing in a Reconfigurable Mesh Network
10.2.1 Code10A: Bus Drawing in a Mesh Network
10.3 Single-Row Routing
10.3.1 Code10B: Realizing Single-Row Routing
References
Index
