Advanced Search

Question: Is there any bugs in GraphTheory['TransitiveReduction']?

Question:Is there any bugs in GraphTheory['TransitiveReduction']?

sursumCorda 1219 Maple 2023
graphtheory
April 16 2023
1

According to this help page, 

the transitive reduction of graph G, is the graph with the fewest edges that still shares the same reachability as G (but might contain new edges not present in G). 

However, in Maple 2023, things become strange; different branches return distinct numbers of edges: 
(33 arcs or 40 arcs?)

> 

restart;
> 

with(GraphTheory):
> 

showstat(TransitiveReduction, 4)


GraphTheory:-TransitiveReduction := proc(G::GRAPHLN, $)
local D, V, T, i, j, k, A, M, n, flags, B;
       ...
   4   if _EnvDisableExt <> true then
           ...
       elif D <> (':-directed') then
           ...
       else
           ...
       end if;
       ...
end proc
 

  
> 

G__0 := Digraph({[2, 8], [3, 1], [4, 9], [5, 10], [6, 19], [7, 12], [8, 13], [9, 3], [10, 4], [10, 14], [11, 5], [11, 15], [12, 6], [12, 16], [13, 7], [13, 17], [14, 9], [15, 10], [15, 18], [16, 19], [17, 12], [17, 20], [18, 14], [19, 11], [19, 21], [20, 22], [21, 18], [22, 16], [22, 23], [23, 19]})

G__0 := `Graph 1: a directed graph with 23 vertices and 30 arc(s)`

 (1)
> 

G__1 := TransitiveReduction(G__0)

G__1 := `Graph 2: a directed graph with 23 vertices and 33 arc(s)`

 (2)
> 

_EnvDisableExt := trueG__2 := TransitiveReduction(G__0)

G__2 := `Graph 3: a directed graph with 23 vertices and 40 arc(s)`

 (3)
> 

IsIsomorphic(G__1, G__2)

false

 (4)
> 

 


 

Download TransReduction.mws

Any bugs? 

G__0 := GraphTheory:-Digraph({[3, 1], [9, 3], [4, 9], [14, 9], [10, 4], [5, 10], [15, 10], [11, 5], [19, 11], [12, 6], [7, 12], [17, 12], [13, 7], [8, 13], [2, 8], [10, 14], [18, 14], [11, 15], [6, 19], [16, 19], [23, 19], [13, 17], [15, 18], [21, 18], [12, 16], [22, 16], [22, 23], [20, 22], [19, 21], [17, 20]}):
Please Wait...