# Graph Toolbox

Graph Toolbox contains useful algorithms including graph traversal (BFS, DFS), topological ordering and includes some metrics calculations.

Author: Akos Szoke aszoke@mit.bme.hu

Web site: http://www.kese.hu

Toolbox Source: https://bitbucket.org/aszoke/

### Features

• findCC - find the connected components (CC) of graphs on NON-DIRECTED SCG (based on set unioning)
• findMSTKruskal - find the minimum spanning tree (MFT) of graphs on NON-DIRECTED SCG /by Kruskal/
• findMSTPrim - find the minimum spanning tree (MFT) of graphs on NON-DIRECTED SCG /by Prim/
• findPath - find (the shortest) path between two nodes on NON-WEIGHTED SCG (based on revealBFSTree)
• findSemiCC - find the semi connected components (SemiCC) of graphs on SCG (based on DFS: complabels)
• findStronglyCC - find the strongly connected components (SCC) of graphs on SCG (based on DFS: applied DFS on G and G')
• produceCCPrec - produce precedence matrix for the connected components (CC) of graphs
• produceStronglyCC - produce strongly connected components (SCC) graph from an SCG (based on findSCC)
• revealBFSTree - breadth-first search (graph traversal algorithm) on JOINT SG
• revealDFSTree - depth-first search (graph traversal algorithm) on SCG (based on DFS) /by Moore/
• sortTopol - topological ordering of DAGs (based on DFS: ordering nodes according to the their finish times in decreasing order) /by Knuth/
• graphanalysis - some important metrics calculations on SG

Note: globalConsts.m initializes global constants

### Theoretical Notes

The following graph properties are defined and used in the toolbox:

• connection: single, multiple
• loop: loop is possible
• direction: directed, non-directed
• cyclic: cyclic, acyclic
• joint: joint, disjoint
• weight: weighted, non-weighted

The following graph types are defined and used in the toolbox:

• single connected graph (SCG): single connected
• simple (SG): single connected, no loop
• digraph (DG): (bipartitate, 2-colorable) directed
• DAG: directed acyclic
• tree graph (TG): no loop
• component graph (CG): jointed nodes
• strongly connected component graph (SCCG): co-joined nodes

## Usage

using the functions in the feature list

### Example

test_graph_toolbox.m

The generated log of the example can be found in test_graph_toolbox.html.

Note: Due to the Bitbucket HTML preview restriction (see HTML rendering for generated doc), in order to view the Test run samples in HTML, use should use the GitHub & BitBucket HTML Preview service. (Copy the link below and paste into the text box that can be found in the service.)

### Test data

see them in the example