analytics

Friday, November 13, 2015

A standard form for adjacency matrices to solve the graph isomorphism problem

Supposing you have some graph with no more than one edge between vertices:
Here A, B, and C are all connected to themselves but they don't have to be, the above graph has adjacency matrix:
Indicating with a 1 where a row, column pair of vertices are connected...

Now a problem is to find a standard form for this and all  adjacency matrices corresponding to isomorphic graphs, though maybe the vertices are labeled differently...

First define a row's C to be a binary number corresponding to the row with the most significant digit to the right.. for example the first row above reads as 1100 so that would be the binary number for decimal 3 or 2^0 + 2^1

The algorithm I'm proposing is to simultaneously swap two rows and corresponding columns producing a new matrix if it increases a row's C with importance towards the top row. For example, swap two columns and corresponding rows if it either increases the first row's C or if that's not possible,  the second rows C while also not making the first row's C less, or if that's not possible swap so the third row's C is increased while at the same time not making row 1's and row 2's C less, etc... Each iteration of the algorithm I call an "improvement" of the adjacency matrix, the algorithm is done when no more improvements are possible...



Above is 3 steps of the algorithm describing which rows and columns are to be swapped highlighted in red and which row is improved on the new matrix after the swapping... The final matrix on the right can not be improved by the above definition by swapping any pair of rows and  corresponding columns... I think the exact specifics of how to choose which rows and corresponding columns is not important to the final result which by definition can not be improved...

So the final matrix is I believe in a standard form for all adjacency matrices corresponding to isomorphic graphs. In other words all adjacency matrices corresponding to isomorphic graphs and only to isomorphic graphs will improve to a particular unique standard matrix at the end of the algorithm...


Wednesday, November 11, 2015

Easier Bezier by 2nd derivative smoothing

So supposing you have n points on the plane with n greater than or equal to 4 and you want to find a smooth curve through them, you could do a n-degree bezier curve through them but that takes exponential time with respect to n to calculate or you could use bezier splines of a lesser degree but if you use , say, quadratic bezier splines through the n points directly there is a smoothness problem... The approach I'll outline below is to generate with a formula the 2*n-1 "halfway" points between known points then use quadratic bezier curves to interpolate but the way the "halfway" points are calculated gives a smooth final result...

So first we take our n points and label them A(2*(j)-1) for j from 0 to n, and from here on call them A(i)... Then we use this formula:
 This formula is saying that the 2nd derivative by divided differences at a point should be the average of the 2nd derivative at the point before it and the point after it...

Now here is a python program to figure out what the i values should be in the formula above to get the right number of equations for the number of new "halfway" points :

n=7
d = 1.0*(2*n-6)/(n-2)
for i in range(0, n-1):
    print(round(3+i*d))

For n=4 we get:
3,4,5

For n = 5 an odd number of points, we need 4 equations for the 4 in between points so we make the i's using the program::
3,4,6,7

For n = 6 there are 5 in between points we need equations for so we make the i's:
 3,4,6,8,9

For n = 7:
3,5,6,8,9,11


For n = 6 we know the six points A1, A3, A5, A7, A9,A11 and we want to know A2, A4, A6, A8, A10 so we use the i values from the program {3,4,6,8,9} and get five equations to solve:




Then the third step is to use these newly generated points to compute the quadratic Bezier paths between odd labeled points (I used a graphics program to manually draw the Beziers so they don't go exactly through the center of each point but mathematically they would)...




Compare this to using quadratic Beziers directly...

And there are some issues using just Beziers with even number of points about how exactly to divide the curve into quadratics because you need groups of 3 points for quadratic Beziers...

Monday, November 9, 2015

4 point sigmoidal elliptical curve

H and J are used to smoothly blend from one elliptical parameterization to another to produce the curve... the final curve is parameterized over [-pi/2] to [pi]... It might be good for something like designing fonts because it can do circular arcs that are found in a lot of letters well that bezier splines don't manage very well...

Sunday, November 8, 2015

Elliptical Pizza Theorem


So to find the ellipse you find 2 additional points with the formulas above and then the well known method for drawing a conic through 5 points: conic through 5 points.. I think it does a nice job of describing how a pizza will look with perspective if lines perpendicular to the viewing plane are drawn to the right, top, and left of the pizza, calling those P1, P2, and P3 respectively...

**UPDATE**


Actually I was suggesting my above answer to the people at geogebra.org and they told me about this nice parametric equation that only needs the center point and any 2 points on the ellipse, where A is the center:

f(t)=A+(B-A)*sin(t)+(C-A)*cos(t), 

at 0 it equals C, at 1/2)*Pi it equals B, then at 2*pi back to C! 
This one just wows me after as hard as I worked to figure out the one above...
And from that I derived this one:

f(t) = (1/2)*D+(1/2)*B+((1/2)*B-(1/2)*D)*sin(t)+(C-(1/2)*D-(1/2)*B)*cos(t)


Which given 3 points on the ellipse parameterizes it so that between B and D is the shorter axis...

f(pi) gives the opposing point on the long axis that C is on...


Alternative Ellipse:


Friday, November 6, 2015

Experimental comparison of G-decomposition of waves vs. Fourier

Here F is the Fourier style decomposition, for 5 points , and G is the new decomposition I've been working with, written also for five points:




So I tried not to cherry pick these values, I've gotten similar results with every set of points I've tried so far, but let's let the points be [1,1],[3,2],[5,5],[7,3],[9,2] and solve for the coefficients:




I think the problem with the Fourier is that it maxes to 6 height when the largest point is only 5, the G decomposition seems more reasonable,



**Note**
I don't know if the exponents in G cause the coefficients to get too large with a large number of points that will require some more investigation...And of course using powers of trigonometric functions might make them too costly to computer, but there might be some use cases where that isn't as important as the best fit to the points... There might even be some variations between these two where you use some small powers of sines and cosines and some multiples of frequencies...

Wednesday, November 4, 2015

algebraic boolean algebra to prove De Morgan's laws

For 2 binary variables, which may also represent truth and falseness, we can solve for algebraic expressions representing the usual boolean operations like below... we just solve
a*x+b*y+c*x*y+d
algebraically for the four conditions in the truth table to get the coefficients...
Here I solve for ~(x OR y)
 which is:
So the equation above ranging over the binary parameters is:
regular OR is:
and it's easily proven that to negate any expression multiply the expression by -1 and add 1, the OR above is -1*(NOR) +1 for example, and the NOR is -1*(OR) +1 as well. Just see that any time the expression evaluates to 1,  1*(-1)+1 = 0 and when it evaluates to 0, 0*(-1)+1 = 1

So to prove de Morgan's laws we need an AND as well...
So de Morgan's laws are that  ~(x AND y) = (~x OR ~y)...
So ~AND is the same as -x*y + 1 to negate x*y, and then we multiply each variable in the or expression by -1 and add 1 to get...
And simplification shows we have equality...

**Powers and composing**

Sometimes when composing by substituting one of these expressions in for a variable in another, you get powers of a variable, but this is resolved by noting that any counting number power of 1 is 1 and any likewise for 0 is 0... For example This is substituing (X or Y) in for x and ~(x OR y) in for Y in the expression for (x AND y):
In the above the powers of a variable were removed to get to the bottom line to show that (x OR y) AND ~(x OR y) is always false or 0... I think this type of exponent elimination and algebraic simplification makes the 16 possible basic expressions from the 16 truth tables closed under composition...

**3 or more variables**

For 3 variables you solve this equation for the 8 possibilities of the unknowns:
and in general you have coefficients for multiplying the variables 0 at a time (the constant factor),  1 at a time, 2 at a time, etc. up to n at a time for n variables... This is 2^n coefficients because the number of coefficients is the same cardinality as the power set on n items which is 2^n, and there are 2^n possiblities of variables making 2^n linear equations in the coefficients so it can be solved...

**Fuzzy Logic**

Using the expression for OR which is x +y - x*y, I wonder if it's true that if x has a 25% chance of happening and y has a 37% chance of happening, that we can plug in those values and get:

That x OR y has a 52% chance of happening, I'll have to write a program and see whether empirically this checks out... For fuzzy logic you'd have to do away with the rule that exponents disappear of course...

Sunday, November 1, 2015

median heaps and a sorting method

Suppose you have a list of some sortable items indexed naturally starting at 1:
L=2,4,7,9,3,1,5,8,6
Imagine building a heap but not a max heap or a min heap but a median heap, where the property is that position n is greater than or equal to position 2*n and less than or equal to position 2*n+1. Or thinking of it as a tree, that the left child is less than or equal to the parent which is less than or equal to the right child... So looking at the above list:

Start with the first three items:
H=2,4,7
H(1)=2, H(2)=4, H(3)=7 so this does not yet have the property that H(2*n) <= H(n) <= H(2*n+1) for n=1
so we rearrange those 3 items so the property is true:
4,2,7
Now the property is satisfied so we add two more numbers from the list
4,2,7,9,3
H(2) =2 H(4)=9 H(5)=3 so we have to rearrange those three numbers to satisfy the property
4,3,7,2,9
Now since H(2) changed we have to again see whether H(2)<= H(1) <=H(3) which it is
so add another two numbers
4,3,7,2,9,1,5
and H(3)=7 H(6)=1 H(7) = 5 so we have to rearrange to make the property true...
4,3,5,2,9,1,7
And since H(3) changed we have to check whether H(2) <= H(1) <=H(3) which it is
so we add two more
4,3,5,2,9,1,7,8,6
H(8) is not less than or equal to H(4) and H(4) less than or equal to H(9) so we rearrange:
4,3,5,6,9,1,7,2,8
Now H(2) is not between H(4) and H(5) so we rearrange:
4,6,5,3,9,1,7,2,8
And now H(1) is not between H(2) and H(3) so again rearrange:
5,4,6,3,9,1,7,2,8




Graphically it looks like this:

Now the median heap is built... notice that position n is greater than or equal to position 2*n
and less than position 2*n+1, it happens that the first number is the median and the left branches are less than the right branches, but this won't always be the case. So a second step can make it so that that is the case which may break the median heap property but is nicer for sorting, say...
It's possible to recurse the two steps on the two new half lists to eventually get a completely ordered list...

**Example**
The following is the output from the source code below for n=15, in general the list has to have an odd number of items for this code to run
input:
[86 57 24 16 53 91 2 87 83 58 22 89 91 89 33]
output:
[58 53 89 24 86 57 89 16 87 22 83 2 91 33 91]
See the root is the median of the set of numbers and all the odd positions are less than the even positions... Note that this does not have the median heap property because n=5 is 86 which is not between n=10 22 and n=11 83 because the second step broke the median heap property to make it so the root became the median and all even positions are less than the odd positions... I'll mark the spot where the second step begins in the code with a comment...

**Go source code**
package main

import (
    "fmt"
    "math/rand"
    "time"
)
func t(a int, b int, c int) (int, int, int, bool){
    if (b <= a && a <= c){
        return a,b,c, false
    }
    if (c <= a && a <=b){
        return a,c,b, true
    }
    if (a <= b && b <= c){
        return b,a,c, true
    }
    if (c <=b && b <= a){
        return b,c,a, true
    }
    if (a <= c && c <= b){
        return c,a,b, true
    }
    return c,b,a, true
}
func hc(h [] int, o int) ([] int){
    f := true
    for f == true{
        a ,b ,c, f2 := t(h[o],h[2*o+1], h[2*o+2])
        f = f2
        h[o] = a
        h[2*o+1] = b
        h[2*o+2] = c
        o = int(o/2.0)
    }
    return h
}
func main() {
    l := make([] int, 15)
    h := make([] int, 15)
    rand.Seed(time.Now().UnixNano())
    
    for i:=0; i<15; i++{
        l[i] = rand.Intn(100)
    }
    fmt.Println(l)
    h[0] = l[0]
    for i:=0; i<int(len(l)/2.0); i++{
        h[2*i+1] = l[2*i+1]
        h[2*i+2] = l[2*i+2]
        h = hc(h, i)
    }
    //Second step breaking median heap property begins
    for i:=1; i< len(h); i+=2{
        f :=false
        h[0], h[i], h[i+1], f = t(h[0], h[i], h[i+1])
        if f == true{
            i =1
        }
    }
    fmt.Println(h)
}