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

`npm i directed-graph-typed --save`

`yarn add directed-graph-typed`

Data Structure | Unit Test | Performance Test | API Docs |
---|---|---|---|

Directed Graph | DirectedGraph |

Data Structure Typed | C++ STL | java.util | Python collections |
---|---|---|---|

DirectedGraph<V, E> | - | - | - |

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 |

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 |

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. |