Created
April 23, 2016 09:27
-
-
Save xamgore/4c6a06fdfc3c34d186fc524c185a0e49 to your computer and use it in GitHub Desktop.
check G² is not transitiv for any fuzzy relation G
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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]]} | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment