Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2021 | Book

Introduction Read chapter Read first chapter

Algebraic Graph Algorithms

A Practical Guide Using Python

Author: Prof. Dr. K. Erciyes

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This textbook discusses the design and implementation of basic algebraic graph algorithms, and algebraic graph algorithms for complex networks, employing matroids whenever possible. The text describes the design of a simple parallel matrix algorithm kernel that can be used for parallel processing of algebraic graph algorithms. Example code is presented in pseudocode, together with case studies in Python and MPI. The text assumes readers have a background in graph theory and/or graph algorithms.

Table of Contents

Frontmatter
1. Introduction
Abstract
This chapter serves as an informal introduction to the basic concepts used in the book, which are graphs and matrices, along with implementation ideas. It contains a very brief introduction to Python programming language, main challenges in algebraic graph algorithms and a detailed description of the contents of the book.
K. Erciyes

Background

Frontmatter
2. A Short Review of Python
Abstract
We review basic Python features with emphasis on the properties we will use to implement algebraic graph algorithms in this chapter. We start with main data structures which are the lists, arrays, dictionaries and sets. We then review control flow methods with decision and loop structures. The last part of the chapter contains module descriptions, input/output and standard library features.
K. Erciyes
3. Basic Matrix Computations
Abstract
In this chapter, we review basic matrix theory and matrix algebra with algorithms to perform matrix operations. We first define matrices, describe operations on matrices and review basic matrix types. Matrix multiplications are basic operations we will use in various algebraic graph algorithms and we describe algorithms for this purpose in detail. We conclude with matrix determinant, matrix inverse and matrix eigenvalues and eigenvectors. We implement most of the algorithms with available functions from Python libraries.
K. Erciyes
4. Graphs, Matrices and Matroids
Abstract
This chapter forms the basic background on graphs, matrices and matroids. We start with the definitions and notations of graphs followed by main graph types, graph operations and graph traversals in the first section. We then look at ways of defining graph in terms of matrices and conclude with a data structure called matroids which we will use to design some specific type of graph algorithms.
K. Erciyes
5. Parallel and Sparse Matrix Computations
Abstract
Parallel processing is performed by distributing tasks and/or data of computation to a number of processors. We first briefly review parallel processing concepts in this chapter. Two ways of achieving this goal are shared memory and distributed memory approaches as we describe. We then look at ways of parallelizing matrix multiplications using Python, which is a building block of many matrix and algebraic graph algorithms. The last part of the chapter deals with sparse matrices that have zeros as majority of its elements. We look at ways of representing them in memory and discuss basic operations such as multiplication that make use of sparse matrix property.
K. Erciyes

Graph Algorithms

Frontmatter
6. Trees
Abstract
A tree is graph that does not contain any cycles. A tree may be used to model many real network structures such as the administration of an organization. We first provide a method to construct a spanning tree in this chapter. We then review few algorithms to construct a minimum spanning tree of a weighted graph.
K. Erciyes
7. Shortest Paths
Abstract
Finding the shortest shortest path between two vertices in a weighted graph has many applications. A fundamental implementation involves sending packets over shortest routes, therefore, in shortest possible time between two routers in a computer network. This so-called routing problem is commonly solved by converting a graph routing algorithm to a distributed one in the form of a network protocol to be executed by each router. We look at basic graph algorithms to find shortest paths in a weighted graph in this chapter.
K. Erciyes
8. Connectivity and Matching
Abstract
A connected directed or undirected graph has paths between every pair of its vertices and an unconnected graph has more than one component. The connectivity of a computer network represented by a graph must be maintained for correct operation. We investigate algorithms to test connectivity and discovering the components of directed and undirected graphs in the first part of this chapter. We then look at the matching problem which is finding a disjoint set of edges in a graph. This problem is basically finding the maximum number of matching edges in an undirected graph and finding disjoint edges with a maximum/minimum possible total weight in a weighted graph.
K. Erciyes
9. Subgraph Search
Abstract
A subgraph of a graph contains some of its vertices and edges. Some subgraphs have certain properties that can be used by many diverse applications. In this chapter, we survey a number of special subgraphs, algorithms on how to detect them using graph algebraic properties.
K. Erciyes
10. Large Graph Analysis
Abstract
Large graphs consist of thousands of vertices and tens of thousands of edges between these vertices. Visualization and analysis of these graphs is difficult and new measures to evaluate structures of these graphs are needed. In this chapter, we review basic parameters to evaluate the structures of these graphs and conclude with main models of large networks.
K. Erciyes
11. Graph Partitioning and ClusteringGraph partitioning
Abstract
Partitioning and clustering are two main operations on graphs that find a wide range of applications. Graph partitioning aims at balanced partitions with minimum interactions between partitions. However, graph clustering algorithms attempt to discover densely populated regions of graphs. We review algebraic algorithms for these problems and provide Python implementations of these algorithms in this chapter.
K. Erciyes
Backmatter
Metadata
Title
Algebraic Graph Algorithms
Author
Prof. Dr. K. Erciyes
Copyright Year
2021
Electronic ISBN
978-3-030-87886-3
Print ISBN
978-3-030-87885-6
DOI
https://doi.org/10.1007/978-3-030-87886-3

Premium Partner

    Image Credits