TransitiveAlgorithms

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

TransitiveAlgorithms

(★ 6)

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

TransitiveAlgorithms Latest Version Download

Download Latest Version (.zip)

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

TransitiveAlgorithms Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

TransitiveAlgorithms

TransitiveAlgorithms Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README