Abas Zuraida Abal - Simulation for applied graph theory using visual C++

SIMULATION

FOR APPLIED GRAPH THEORY

USING VISUAL C++

S HAHARUDDIN S ALLEH

Z URAIDA A BAL A BAS

MATLAB is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This books use or discussion of MATLAB software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB software.

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

2016 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed on acid-free paper

Version Date: 20160513

International Standard Book Number-13: 978-1-4987-2101-1 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Library of Congress Cataloging-in-Publication Data

Names: Salleh Shaharuddin, 1956- | Abas, Zuraida Abal.

Title: Simulation for applied graph theory using Visual C++ / Shaharuddin Salleh and Zuraida Abal Abas.

Description: Boca Raton : Taylor & Francis, 2017. | A CRC title. | Includes

bibliographical references and index.

Identifiers: LCCN 2016008211 | ISBN 9781315353777 (hard back)

Subjects: LCSH: Graph theory--Data processing. | Microsoft Visual C++

Classification: LCC QA166 .S24 2017 | DDC 511/.502855133--dc23

LC record available at http://lccn.loc.gov/2016008211

Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com

and the CRC Press Web site at
http://www.crcpress.com

To Ruby, Ila, Liya, and Azri.

To Mas Hariadi, Ahmad Aqhil, and Nuranna.

Thank you for all the support.

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 todays 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 . 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.