Transitivity Demo
Transitivity algorithms are heavily applied to graphs in order to answer reachability
questions such as
"Is it possible to reach node x from y?"
. Common application fields are social networks, dependency graphs, bioinformatics,
citation graphs or criminal networks in which possible relations between two entities
have to be quickly identified and investigated.
Algorithms
The user can select one of the available algorithms from the algorithms' combo box.
Selecting the
Original Graph
will bring the graph to its original state without the transitive edges.
Transitive Closure
Transitivity Closure is applied in order to answer the question whether there exists a
directed path between two nodes. The algorithm adds an edge to the graph for each pair of
nodes, that are not direct neighbors, but connected by a path in the graph. The transitive
edges are visualized in red color.
Transitive Reduction
Transitivity Reduction is the reverse operation to transitive closure which removes edges
between any two nodes if there exists another path that connects them. This means that in
the end, the graph remains with as few edges as possible but has the same reachability
relation as before. The user can choose to show or hide transitive edges using the
-Button of the toolbar.
Graph Information