TransitiveAlgorithms

KO | EN

gitlite — search

#typescript #ai-agents #deepseek-harness #dsh-plugin #open-source #ai #cli #dsh #claude-code #codex #developer-tools #react

TransitiveAlgorithms

★ 6 Open GitHub ↗

Transitive Closure (DFS and Floyd-Warshall). Transitive Reduction (Path Matrix).

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Transitive Algorithms
- Transitive Closure (DFS and Floyd-Warshall).
- Transitive Reduction (Path Matrix).

## Transitive Closure
Transitive closure finds additional connection between two vertices.  
For example, if graph has connection such as 0 -> 1 -> 2 then algorithm add another connection 0 -> 2.

### 1. Method with DFS (Depth First Search)
If you use method with DFS you receive two additional connections 0 -> 0 and 2 -> 2.  
Time complexity: O(V^2)

### 2. Method with Floyd-Warshall
Floyd-Warshall algorithm doesn't finds thats self-connections, but it have O(V^3) time complexity.  
  
Look at the picture below for better comprehesion of this issues.

![Transitive closure](https://raw.githubusercontent.com/lucasrabiec/TransitiveAlgorithms/master/client/TransitiveAlgorithms.Client/Data/TransitiveClosure.png)
#

## Transitive Reduction
Transitive reduction removes redundant connections. This library uses an additional method which transforms graph into a path matrix.  
Without this method algorithm doesn't remove 0 -> 1 connection in example called ***Hard***.

![Transitive closure](https://raw.githubusercontent.com/lucasrabiec/TransitiveAlgorithms/master/client/TransitiveAlgorithms.Client/Data/TransitiveReduction.png)

> Diagrams made in [Draw.io](https://www.draw.io)

TransitiveAlgorithms

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README