What
Brief
This is a standalone Directed Graph data structure from the data-structure-typed collection. If you wish to access more
data structures or advanced features, you can transition to directly installing the
complete data-structure-typed package
How
install
npm
npm i directed-graph-typed --save
yarn
yarn add directed-graph-typed
snippet
API docs & Examples
API Docs
Live Examples
Examples Repository
Data Structures
| Data Structure |
Unit Test |
Performance Test |
API Docs |
| Directed Graph |
 |
|
DirectedGraph |
Standard library data structure comparison
| Data Structure Typed |
C++ STL |
java.util |
Python collections |
| DirectedGraph<V, E> |
- |
- |
- |
Benchmark
directed-graph
| test name | time taken (ms) | executions per sec | sample deviation |
|---|
| 1,000 addVertex | 0.10 | 9534.93 | 8.72e-7 |
| 1,000 addEdge | 6.30 | 158.67 | 0.00 |
| 1,000 getVertex | 0.05 | 2.16e+4 | 3.03e-7 |
| 1,000 getEdge | 22.31 | 44.82 | 0.00 |
| tarjan | 210.90 | 4.74 | 0.01 |
| tarjan all | 214.72 | 4.66 | 0.01 |
| topologicalSort | 172.52 | 5.80 | 0.00 |
Built-in classic algorithms
| Algorithm |
Function Description |
Iteration Type |
| Graph DFS |
Traverse a graph in a depth-first manner, starting from a given node, exploring along one path as deeply as
possible, and backtracking to explore other paths. Used for finding connected components, paths, etc.
|
Recursion + Iteration |
| Graph BFS |
Traverse a graph in a breadth-first manner, starting from a given node, first visiting nodes directly connected
to the starting node, and then expanding level by level. Used for finding shortest paths, etc.
|
Recursion + Iteration |
| Graph Tarjan's Algorithm |
Find strongly connected components in a graph, typically implemented using depth-first search. |
Recursion |
| Graph Bellman-Ford Algorithm |
Finding the shortest paths from a single source, can handle negative weight edges |
Iteration |
| Graph Dijkstra's Algorithm |
Finding the shortest paths from a single source, cannot handle negative weight edges |
Iteration |
| Graph Floyd-Warshall Algorithm |
Finding the shortest paths between all pairs of nodes |
Iteration |
| Graph getCycles |
Find all cycles in a graph or detect the presence of cycles. |
Recursion |
| Graph getCutVertexes |
Find cut vertices in a graph, which are nodes that, when removed, increase the number of connected components in
the graph.
|
Recursion |
| Graph getSCCs |
Find strongly connected components in a graph, which are subgraphs where any two nodes can reach each other.
|
Recursion |
| Graph getBridges |
Find bridges in a graph, which are edges that, when removed, increase the number of connected components in the
graph.
|
Recursion |
| Graph topologicalSort |
Perform topological sorting on a directed acyclic graph (DAG) to find a linear order of nodes such that all
directed edges go from earlier nodes to later nodes.
|
Recursion |
Software Engineering Design Standards
| Principle |
Description |
| Practicality |
Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names. |
| Extensibility |
Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures. |
| Modularization |
Includes data structure modularization and independent NPM packages. |
| Efficiency |
All methods provide time and space complexity, comparable to native JS performance. |
| Maintainability |
Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns. |
| Testability |
Automated and customized unit testing, performance testing, and integration testing. |
| Portability |
Plans for porting to Java, Python, and C++, currently achieved to 80%. |
| Reusability |
Fully decoupled, minimized side effects, and adheres to OOP. |
| Security |
Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects. |
| Scalability |
Data structure software does not involve load issues. |
zrwusa