Topics

Homology groups for paths on 8-connected grids

o.lamarre7@...
 

Hi!
I've been playing around with this library and after going through the (great) documentation for it, I'm still stuck trying to implement what I believe to be rather basic: evaluate path homologies on already-known 8-connected grids.

Here's a sample problem to illustrate the situation: say we have an already-known 8-connected grid/map with known obstacles (shown in dark gray). Such a 2D map can be represented as a simplicial complex (containing k-0, k-1 and k-2 simplices). The space contained between the 2,5,6,9 vertices is a hole:

Now, I would like to compare different chains (with the same start and end vertices) and would like to tell whether they belong to the same homology group or not. In the following example, the red and green 1-chains should be considered homologous but the blue chain should belong to a different homology group:


I have attempted to implement this example in a very simply Dionysus example using Python:

import dionysus as d
 
# Create simplicial complex
simplices_k0 = [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]]
simplices_k1 = [[0,1],[1,2], [2,3], [0,4], [0,5], [1,4], [1,5], [2,5], [2,6], [3,6], [4,5], [4,7], [4,8], [5,7], [5,8], [5,9], [6,9], [6,10], [7,8], [8,9], [9,10]]
simplices_k2 = [[0,4,5], [0,1,5], [0,4,1], [1,4,5], [1,2,5], [2,3,6], [4,5,7], [5,7,8], [4,5,8], [4,7,8], [5,8,9], [6,9,10]]
 
# Create filtration and reduced boundary matrix
f = d.Filtration(simplices_k0 + simplices_k1 + simplices_k2)
f.sort()
m = d.homology_persistence(f)
 
# Chains to evaluate/compare
chain_red = d.Chain([(1,4), (4,8), (8,9)])
chain_green = d.Chain([(1,5), (5,9)])
chain_blue = d.Chain([(1,2), (2,6), (6,9)])
 
m.homologous(chain_red, chain_green)    # Returns False (but was expecting True)
m.homologous(chain_red, chain_blue)      # Returns True  (but was expecting False)
m.homologous(chain_green, chain_blue)  # Returns False (was expecting False)
As mentioned in the comments above, there is definitely something I am missing. First, am I creating the chains properly? I thought they were basically a list of 1-D simplices tuples, but this might not be the case (still confused after looking at the API documentation). Second - would anyone be able to tell if this is a proper usage for the "homologous" method? If not, how could I adapt the code above to successfully compare the red-green-blue chains from the example?

Thank you very much!

Dmitriy Morozov
 

The chains should be defined in terms of the indices in the filtration. Each entry should be a tuple of coefficient and index. So to make your code work, change the chain definitions to:

chain_red = d.Chain([(1,f.index(d.Simplex(s))) for s in [(1,4), (4,8), (8,9)]])
chain_green = d.Chain([(1,f.index(d.Simplex(s))) for s in [(1,5), (5,9)]])
chain_blue = d.Chain([(1,f.index(d.Simplex(s))) for s in [(1,2), (2,6), (6,9)]])

On Wed, Sep 18, 2019 at 11:06 PM <o.lamarre7@...> wrote:
Hi!
I've been playing around with this library and after going through the (great) documentation for it, I'm still stuck trying to implement what I believe to be rather basic: evaluate path homologies on already-known 8-connected grids.

Here's a sample problem to illustrate the situation: say we have an already-known 8-connected grid/map with known obstacles (shown in dark gray). Such a 2D map can be represented as a simplicial complex (containing k-0, k-1 and k-2 simplices). The space contained between the 2,5,6,9 vertices is a hole:

Now, I would like to compare different chains (with the same start and end vertices) and would like to tell whether they belong to the same homology group or not. In the following example, the red and green 1-chains should be considered homologous but the blue chain should belong to a different homology group:


I have attempted to implement this example in a very simply Dionysus example using Python:

import dionysus as d
 
# Create simplicial complex
simplices_k0 = [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]]
simplices_k1 = [[0,1],[1,2], [2,3], [0,4], [0,5], [1,4], [1,5], [2,5], [2,6], [3,6], [4,5], [4,7], [4,8], [5,7], [5,8], [5,9], [6,9], [6,10], [7,8], [8,9], [9,10]]
simplices_k2 = [[0,4,5], [0,1,5], [0,4,1], [1,4,5], [1,2,5], [2,3,6], [4,5,7], [5,7,8], [4,5,8], [4,7,8], [5,8,9], [6,9,10]]
 
# Create filtration and reduced boundary matrix
f = d.Filtration(simplices_k0 + simplices_k1 + simplices_k2)
f.sort()
m = d.homology_persistence(f)
 
# Chains to evaluate/compare
chain_red = d.Chain([(1,4), (4,8), (8,9)])
chain_green = d.Chain([(1,5), (5,9)])
chain_blue = d.Chain([(1,2), (2,6), (6,9)])
 
m.homologous(chain_red, chain_green)    # Returns False (but was expecting True)
m.homologous(chain_red, chain_blue)      # Returns True  (but was expecting False)
m.homologous(chain_green, chain_blue)  # Returns False (was expecting False)
As mentioned in the comments above, there is definitely something I am missing. First, am I creating the chains properly? I thought they were basically a list of 1-D simplices tuples, but this might not be the case (still confused after looking at the API documentation). Second - would anyone be able to tell if this is a proper usage for the "homologous" method? If not, how could I adapt the code above to successfully compare the red-green-blue chains from the example?

Thank you very much!

o.lamarre7@...
 

Oh I see! Great, thank you very much for the help!