Basic Graph Algorithms for Data Scientists

This live repo aims to cover basic graph algorithms implemented in C++ (for performance reasons) used in data science. It's meant for educational purposes and will continue to evole.

Introduction

This repo covers basic graph algorithms for directed and undirected graphs with/without weights on edges. Graph description is read from a file with ascii format.

Base graph data structure is targeted for sparse graphs efficiency. For example, it maintains adjancy list and pointrs. Here are big-O time and space complexities.

	RAM	node-add	edge-add	node-remove	edge-remove	query
Adjacency List	[n]+[e]	1	1	[n]+[e]	[e]	[e]
Incident List	[n]+[e]	1	1	[e]	[e]	[e]

Legend:

• Two vertices are called adjacent if they are connected by an edge.
• Two edges are called incident, if they share a vertex.

Basic Graph

namespacebasicGraph {
...
classbNode {
private:
string name_; // node name
set<const bEdge*, edgeCompare> edgelist_; // incident list
...
}/
classbEdge {
private:const bNode* n1_; // from node for directd graphsconst bNode* n2_; // to node for directed graphs
...
};
...
classbGraph {
private:bool isDirected_;
set<const bNode*, nodeCompare> nodeset_;
set<const bEdge*, edgeCompare> edgeset_;
...
};
}

For more details, refer to graph.h.

Algorithms Covered

• DFS
• Transpose
• Topological Sort
• Strongly Connected Components
• Prim's Mimimal Spanning Tree
• Kruskal's Mimimal Spanning Tree
• Dijkstra's Single Source Shortest Path to All Nodes
• A* (aka Astar) Source-Destination Pair Shortest Path Finder Algorithm

Graph File Format

graph (un)directed`
<node-x> <node-y> [edge-weight]

Example Graph File

# Comment, ignored by the graph reader
graph directed
n1 n2 2
n1 n3 4
n2 n3 1
n2 n4 4
n2 n5 2
n3 n5 3
n4 n6 2
n5 n4 3
n5 n6 2

Application

How to Compile

cd src
<c++-compiler> *.cpp -o bgaMain.exe

How to Run

bgaMain.exe <graph-file>

Example run

$ src/bgaMain.exe test/dgraph5.txt

created graph with 6 nodes and 9 edges.
type 'help' for more options

help

 help
print
search <root_node>
sort
mst [prim|kruskal]
path <root_node>
quit

print

graph directed
n2 n3 1
n1 n2 2
...

path n1

nd dist_from_src edge
== ============= ====
n1 0 [none n1 0]
n2 2 [n1 n2 2]
n3 3 [n2 n3 1]

Disclaimer

This is a quick and dirty code produced over weekends. Main objective behind this repository is purely educational. It has quite a bit of room for improvement. Feel free to reach out if you spot weakness, bug, enancement or simply a suggestion.