- Notifications
You must be signed in to change notification settings - Fork3
srohit0/DataScienceGraphAlgorithms
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
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.
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 forsparse 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.
namespacebasicGraph {...classbNode {private:string name_;// node nameset<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 tograph.h.
- 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 (un)directed`<node-x> <node-y> [edge-weight]Example Graph File
# Comment, ignored by the graph readergraph directedn1 n2 2n1 n3 4n2 n3 1n2 n4 4n2 n5 2n3 n5 3n4 n6 2n5 n4 3n5 n6 2cd src<c++-compiler> *.cpp -o bgaMain.exe bgaMain.exe <graph-file>
$ src/bgaMain.exe test/dgraph5.txt
created graph with 6 nodes and 9 edges.type 'help' for more optionshelp
help print search <root_node> sort mst [prim|kruskal] path <root_node> quitgraph directedn2 n3 1n1 n2 2...path n1
nd dist_from_src edge== ============= ====n1 0 [none n1 0]n2 2 [n1 n2 2]n3 3 [n2 n3 1]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.
About
Selected Graph Algorithms
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.