IMPLEMENTATION OF COMMONLY USED GRAPH ALGORITHMS IN MATLAB

1. Converts from/to adjacency matrix/adjacency list representations
2. Generate random connected graphs given n and m– directed/undirected
3. Generate random acyclic graphs given n and m
4. Test for connectivity in a given graph (weakly/strongly connected in directed case)
5. Test for the existence of cycles in a given graph
6. Generate all spanning trees of a given graph
7. Generate minimum spanning tree of a given graph with a given cost matrix - Kruskal’s (Disjoint Set DS)
8. Generate maximum cost spanning tree of a given graph
9. Generate maximum leaf spanning tree of a given graph (uses backtracking)
10. Find all-pairs shortest paths
11. Find transitive closure of a given graph
12. Find whether or not the given directed/undirected graph is Eulerian
13. Find Euler cycle/path in a given directed/undirected graph
14. Find cut vertex/edge using depth first search
15. Plot the resultant graph using AT&T graphviz graph visualization toolkit
16. View/save the resultant adjacency matrix/list

Read the detailed report

View presentation (Zipped PowerPoint file)

DOWNLOAD SOFTWARE

For further information contact Soshant Bali (sbali@ittc.ku.edu) or Abdul Jabbar Mohammed (jabbar@ku.edu)