2021 | Book

# Algebraic Graph Algorithms

## A Practical Guide Using Python

Author: Prof. Dr. K. Erciyes

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

2021 | Book

Author: Prof. Dr. K. Erciyes

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

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.

Advertisement

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.