check G² is not transitiv for any fuzzy relation G

transitiv.go

// check G² is not transitiv for any fuzzy relation / graph G
// G² = G ∘ G, where ∘ is min-max composition

package main

import "fmt"
import "math"

type Matrix struct {
	size  int
	field [][]float64
}

func min(a, b float64) float64 {
	if a < b {
		return a
	}
	return b
}
func max(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}

func NewMatrix(size int, nums ...float64) Matrix {
	field := make([][]float64, size)

	for i := 0; i < size; i++ {
		field[i] = make([]float64, size)

		for j := 0; j < size; j++ {
			idx := i*size + j
			if idx < len(nums) {
				field[i][j] = nums[idx]
			}
		}
	}

	return Matrix{size, field}
}

func (a Matrix) Product(b Matrix) Matrix {
	r := NewMatrix(a.size)

	for i := 0; i < a.size; i++ {
		for j := 0; j < a.size; j++ {
			sum := 0.0

			for c := 0; c < a.size; c++ {
				sum = max(sum, min(a.field[i][c], b.field[c][j]))
			}

			r.field[i][j] = sum
		}
	}

	return r
}

func Check(a, b Matrix, predicate func(float64, float64) bool) bool {
	for i := 0; i < a.size; i++ {
		for j := 0; j < a.size; j++ {
			if !predicate(a.field[i][j], b.field[i][j]) {
				return false
			}
		}
	}

	return true
}

func (a Matrix) Equals(b Matrix) bool {
	return Check(a, b, func(ax, bx float64) bool { return ax == bx; })
}

func (a Matrix) IsSubOf(b Matrix) bool {
	return Check(a, b, func(ax, bx float64) bool { return ax <= bx })
}

func (a Matrix) Square() Matrix { return a.Product(a) }

func (a Matrix) Quad() Matrix { return a.Square().Square() }

func (a Matrix) IsTransitiv() bool { return a.Quad().IsSubOf(a.Square()) }

func pow(c, s int) int {
	return int(math.Pow(float64(c), float64(s)))
}

func Generate(size int, viewer func(Matrix) bool) {
	vars := []float64{0,  1}
	count := len(vars)

	field_len := size*size
	field := make([]float64, field_len)

	for bitmask, end := 0, pow(count, field_len); bitmask < end; bitmask++ {
		b := bitmask

		for i := 0; i < field_len; i++ {
			field[i], b = vars[b % count], b / count
		}

		if !viewer(NewMatrix(size, field...)) { break; }
	}
}

func main() {
	//a := NewMatrix(3,  0, 0.3, 0.3,  0.4, 0.3, 0.8,  0.2, 0.3, 0.4)
	//fmt.Println( a.Product(a).Equals( NewMatrix(3,  0.3, 0.3, 0.3,  0.3, 0.3, 0.4,  0.3, 0.3, 0.4) ))

	for size := 1; size < 200; size++ {
		Generate(size, func(matr Matrix) bool {
			if !matr.IsTransitiv() {
				fmt.Println(matr)
				return false
			}
			return true
		})
		//fmt.Println()
	}

	fmt.Println("end")
}

/*
{3 [[0 1 1] [1 1 0] [0 0 0]]}
{4 [[0 1 1 0] [1 1 0 0] [0 0 0 0] [0 0 0 0]]}
{5 [[0 1 1 0 0] [1 1 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]]}
{6 [[0 1 1 0 0 0] [1 1 0 0 0 0] [0 0 0 0 0 0] [0 0 0 0 0 0] [0 0 0 0 0 0] [0 0 0 0 0 0]]}
{7 [[0 1 1 0 0 0 0] [1 1 0 0 0 0 0] [0 0 0 0 0 0 0] [0 0 0 0 0 0 0] [0 0 0 0 0 0 0] [0 0 0 0 0 0 0] [0 0 0 0 0 0 0]]}
*/