Algorithm and Data Structure Repository

Depth First Search and Breadth First Search

• C source files: dfs_bfs.c dfs_bfs.h
• Example program: dfs_bfs_test.c
• DFS picture
• BFS picture
• Description

Tarjan's Algorithm (Strongly Connected Components)

• C source files: sc.c sc.h
• Example program: sc_test.c
• Picture
• Description

Dijkstra's Algorithm

Two implementations are given which differ by the data structure used for the frontier set.

Implemented with a one-dimentional array:

• C program source file: da_simple.c
• Picture
• Description

Implemented with a heap:

• C source files: da.c da.h
• example program: da_test.c

Floyd's Algorithm

• C program source file: floyd.c

Minimal Spanning Tree Algorithms

Currently only Prim's minimal spanning tree algorithm is implemented.

• C source files: mst.c mst.h
• Example program: mst_test.c

Maximum Flow Algorithms

The Ford and Fulkerson, Dinic, MPM, and Karzonov maximum flow algorithms are implemented.

• C source files: mf.c mf.h
• Example program: mf_test.c
• Picture
• Description
• CPU time measurements

• C Source files: sort.c sort.h
• Example program: sort_test.c

Some CPU time data is available for a performance comparison of functions in sort.c, and the qsort() function provided by the C header <stdlib.h>.

Quicksort

• Picture
• Description

Mergesort

• Picture
• Description

Radix Sort

• Picture
• Description

Heap Sort

• Build-heap picture
• Heap-sort picture
• Description

• C source files: search.c search.h
• Example program: search_test.c

Currently only binary search is implemented.

Convex Hulls

An implementation of Graham's scan for simple 2-dimensional convex hulls.

• C source files: chull.c chull.h
• Demonstration program (X Windows): run_chull.c
• Makefile

• Directed graph C source files: dgraph.c dgraph.h
• Undirected graph C source files: graph.c graph.h

These C source files are used by the graph algorithms in this repository.

Common Files

A description of all the heaps implemented is provided.

The header file heap_info.h defines a common structure type for heaps so that they can be used interchangeably. A program which uses this common structure type is then able to use different heaps interchangeably. The heap implementation of Dijkstra's algorithm is an example of this.

• Example program: [Dijkstra's Algorithm]
• Test data - using heaps in Dijkstra's algorithm: 2-3 heap test data, trinomial heap test data

Binary Heap

• C source files: bheap.c bheap.h

Fibonacci Heap

• C source files: fheap.c fheap.h

2-3 Heap

The trees in a 2-3 heap can be viewed in two different ways, and this leads to two different 2-3 heap implementations.

Implemented using linked lists of child nodes:

• C source files: ttheap.c ttheap.h
• 2-3 heap representation using pointers: (picture)

Implemented using linked lists of child node-pairs:

• C source files: ttheap2.c ttheap2.h
• 2-3 heap representation using node-pair pointers: (picture)

In the node-pair implementation the linked list of child nodes is defined differently. Nodes have an extra pointer which points to an optional partner node with which the node forms a node-pair. Each node has a boolean field which identifies whether it is the "extra" node a node-pair.

Trinomial heap

The extended trinomial heap implementation supports O(1) worst case time for decrease_key:

• C source files: triheap_ext.c triheap_ext.h
• extended trinomial heap representation: (picture)

The basic trinomial heap implementation supports O(1) amortized time for decrease_key:

• C source files: triheap.c triheap.h
• basic trinomial heap representation: (picture)

Common Files

The header file dict_info.h defines a common structure type that each dictionary can provide. A program which uses this common structure type is then able to use different dictionaries interchangeably, as done by the supplied example program.

• Example program: dict_test.c
• Experimental data: cpu time results

Binary Search Tree

• C source files: bst.c bst.h
• Example program: bst_test.c
• Picture
• Description

AVL Tree

• C source files: avl.c avl.h
• Example program: avl_test.c
• Picture
• Description

2-3 Tree

Standard 2-3 tree:

• C source files: tree23.c tree23.h
• Example program: tree23_test.c
• Picture
• Description

Modified 2-3 tree, supporting delete_min() in O(1) worst case time:

• C source files: tree23_ext.c tree23_ext.h
• Example program: tree23_ext_test.c
• Description

Red-Black Tree

• C source files: rbtree.c rbtree.h
• Example program: rbtree_test.c
• Picture
• Description

Hash Table

• C source files: hashtbl.c hashtbl.h
• Example program: hash_test.c
• Picture
• Description

Skip List

• C source files: skip_list.c skip_list.h
• Example program: skip_list_test.c
• Picture
• Description

Digital Search Tree

• C source files: dst.c dst.h
• Example program: dtree_test.c
• Pictures: (insert) (delete)
• Description

Radix Search Trie

• C source files: rst.c rst.h
• Example program: rst_test.c
• Pictures: (insert) (delete)
• Description

A standard implementation of directed graphs is used by Dijkstra's algorithm.

• Directed graphs: dgraph.cpp dgraph.h

Various heaps for use in Dijkstra's algorithm are provided. These are all derived from a common base class.

• Heap base class: heap.h

The individual heap implementations are given below:

• Fibonacci heap: fheap.cpp fheap.h
• 2-3 heap: heap23.cpp heap23.h
• trinomial heap: triheap.cpp triheap.h
• extended trinomial heap (with O(1) worst-case time for decrease-key operations): triheap_ext.cpp triheap_ext.h
• radix heap: radixheap.cpp radixheap.h, (description)

Since the radix heap works specifically with Dijkstra's algorithm, it is described separately from the other heaps. A description of other heaps can be found in the heaps section of the main algorithm repository

Dijkstra's algorithm was implemented with the ability to use any of the above heaps.

• Dijkstra's algorithm: dijkstra.cpp dijkstra.h

Example Usage (Experiment Code)

The following example program demonstrates how to use the different heap implementations with Dijkstra's algorithm.

• directed graph generation: dgraph_factory.cpp dgraph_factory.h
• main program: run_dijkstra.cpp

In addition, the following experiment code can be used to compare the different instances of Dijkstra's algorithm on different graphs.

• directed graph providers: dgraphp.h dgraphp_lib.h
• experiment: exp_sp.cpp exp_sp.h
• main program: run_exp.cpp

• alg.tar.gz contains all of the algorithm repository source code and makefiles.

Algorithms

• Graph algorithms: graphalg.tar.gz
• Sorting algorithms: sorting.tar.gz
• Searching algorithms: searching.tar.gz

Data Structures

• Graphs: graphs.tar.gz - source files for graphs used by algorithms in this repository.
• Heaps: heaps.tar.gz
• Dictionaries: dict.tar.gz

Related

• Timing library: timing.tar.gz

• Shortest Path Algorithms and Priority Queues in C++: spalgs.tar.gz