Lex-Minimizer

In this notebook, we will demonstrate the use of functions that computes the inf-minimizer (CompInfMin) and lex-minimizer (CompLexMin), as well as other experiments. You can find all source code in lex.jl.



In [1]:

    
pwd()









    Out[1]:





"/home/xshi0x63/Desktop/YINS/Laplacians.jl/notebooks"



In [3]:

    
push!(LOAD_PATH,"../src")
using Laplacians



In [4]:

    
using PyPlot



In [5]:

    
include("../src/lex.jl") # for development









    Out[5]:





CompLexMin (generic function with 1 method)

IterLex Functions

simIterLexUnwtd(...) runs IterLex on a uniformly weighted graph for a specific number of iterations;
checkLexUnwtd(...) checks the correctness of the assignment up to LEX_EPS;
simIterLex(...) runs IterLex on any weighted graph;
checkLex(...) checks the correctness of the assignment up to LEX_EPS;

Simple examples

Path Graphs

A path graph with n vertices. Let vertex 1 and n be terminals, with voltages 0 and 1 respectively.



In [ ]:

    
# Set up
n = 10
Pn = pathGraph(n)

isTerm = zeros(Bool, n)
isTerm[1] = true
isTerm[n] = true

initVal = zeros(n)
initVal[n] = 1.0



In [ ]:

    
# inf-minimizer
infMinVolt = CompInfMin(Pn, isTerm, initVal)
println(infMinVolt)
println(MaxEdgeGrad(Pn, infMinVolt))

# lex-minimizer
lexMinVolt = CompLexMin(Pn, isTerm, initVal)

println(lexMinVolt)



In [ ]:

    
# default error tolerance
LEX_EPS



In [ ]:

    
t1 = 5
asgnmt = simIterLexUnwtd(t1, Pn, isTerm, initVal)
@printf("After %d iterations: %s\n", t1, checkLexUnwtd(Pn, isTerm, initVal, asgnmt, fatal = false))

t2 = 500
asgnmt = simIterLexUnwtd(t2, Pn, isTerm, initVal)
@printf("After %d iterations: %s\n", t2, checkLexUnwtd(Pn, isTerm, initVal, asgnmt, fatal = false))



In [ ]:

    
iterVolt = copy(initVal)
i = 0
# the last parameter is to tell CheckLex not to complain when it sees a value that's worse than epsilon approx
while (!CheckLex(Pn, isTerm, initVal, iterVolt, LEX_EPS, false))
    i += 1
    iterVolt = simIterLexUnwtd(1, Pn, isTerm, iterVolt)
end
@printf("After %d iterations, IterLex on path graph with %d vertices has an error <= %.2e", i, n, LEX_EPS)

Plotting the number of iteration needed vs. number of nodes in the path graph, we can see that it takes about O(n^2) iterations.



In [ ]:

    
MAXN = 20
iterArr = zeros(Int64, MAXN)
for n in 3:MAXN
    Pn = pathGraph(n)

    isTerm = zeros(Bool, n)
    isTerm[1] = true
    isTerm[n] = true

    initVal = zeros(n)
    initVal[n] = 1.0
    iterVolt = copy(initVal)
    i = 0
    while (!CheckLex(Pn, isTerm, initVal, iterVolt, 1e-14, false))
        i += 1
        iterVolt = simIterLexUnwtd(1, Pn, isTerm, iterVolt)
    end
    iterArr[n] = i
end

x = collect(1:20)
x2 = x .* x * 5 # estimate
y = copy(iterArr)
plot(x, y, linewidth=1.0, "o-", x, x2, "g^--")

Star Graph



In [ ]:

    
# Star Graph: simplest example:
# picking the right pair of neighbors to average
n = 5
Sn = zeros(n, n)
Sn[1,:] = a = [0, 1/20, 1/20, 1/10, 1/18]
Sn[:,1] = a'
Sn = sparse(Sn)

isTerm = ones(Bool, n)
isTerm[1] = false

initVal = [0.0, 20, -5, -5, 17]

asgnmt = simIterLex(1, Sn, isTerm, initVal)



In [ ]:

    
checkLex(Sn, isTerm, initVal, asgnmt, fatal = false)

Random Graph



In [ ]:

    
n = 20
G = chimera(n)



In [ ]:

    
isTerm = zeros(Bool, n)
# arbitrary terminal values
isTerm[1] = true
isTerm[5] = true
isTerm[11] = true
isTerm[18] = true

initVal = zeros(Float64, n)
initVal[1] = 0.0
initVal[5] = 13
initVal[11] = 7
initVal[18] = 11



In [ ]:

    
infMinVolt = CompInfMin(G, isTerm, initVal)
println(infMinVolt)
println(MaxEdgeGrad(G, infMinVolt))



In [ ]:

    
lexMinVolt = simIterLex(500, G, isTerm, initVal)
println(lexMinVolt)
println(MaxEdgeGrad(G, lexMinVolt))
println(checkLex(G, isTerm, initVal, lexMinVolt))

termFreeShortestPaths gives the shortest paths from the vertex start to every other vertex without going through a terminal;



In [6]:

    
G = readIJV("testLexGraph.txt")
n = G.n









    Out[6]:





20



In [7]:

    
isTerm = zeros(Bool, n)
# arbitrary terminal values
isTerm[1] = true
isTerm[5] = true
isTerm[19] = true

initVal = zeros(Float64, n)
initVal[1] = 0.0
initVal[5] = 13
initVal[19] = 11









    Out[7]:





11



In [ ]:



In [ ]:

    
include("../src/lex.jl")



In [ ]:

    
lexMinVolt = CompLexMin(G, isTerm, initVal)



In [ ]:

    
checkLex(G, isTerm, initVal, lexMinVolt)



In [ ]:

    
setLexDebugFlag(true)
LEX_DEBUG



In [ ]:

    
lexMinVolt



In [ ]:



In [ ]:

    
MaxEdgeGrad(G, lexMinVolt)