singlePointOfFailure

singlePointOfFailure.py

import networkx as nx
import matplotlib.pyplot as plt

def draw_graph(adjList, log = False):

    V = len(adjList)
    
    # extract nodes from graph
    nodes = set([i for i in range(V)])
    if log: print("nodes: " + str(nodes))
    
    # create networkx graph
    G=nx.Graph()

    # add nodes
    for node in nodes:
        G.add_node(node)
        if log: print("n:" + str(node))

    # add edges
    for v in range(len(adjList)):
        if log: print("len of adj list for v:" + str(len(adjList[v])))
        if log: print("leng of adj List for v: " + str(v) + " is " + str(len(adjList[v])))
        for e in adjList[v]:
            G.add_edge(v, e)
            if log: print("add edge from: " + str(v) + " to:" + str(adjList[v][e]))

    # draw graph
    pos = nx.kamada_kawai_layout(G)
    nx.draw_networkx_nodes(G, pos, node_size = 30)
    nx.draw_networkx_edges(G, pos, width=1)

    # show graph
    plt.show()

def convertToAdjList(connections):
    result = [[] for i in range(len(connections))]

    for i in range(len(connections)):
        for j in range(len(connections[i])):
            if connections[i][j] == 1:
                if j not in result[i]:
                    result[i].append(j)
                if i not in result[j]:
                    result[j].append(i)

    return result

def singlePointOfFailure(connections, log = False, draw = False, start_v = 0):
    
    adjList = convertToAdjList(connections)
    if draw: draw_graph(adjList)

    V = len(adjList)
    
    visited = [False for i in range(V)]
    levels = [-1 for i in range(V)]
    currentLevel = 0
    maxLevel = 0

    
    def dfs(v, level, path, path_levels):
        nonlocal maxLevel, levels, visited

        visited[v] = True
        levels[v] = level
        if log: print("=============\nv:" + str(v) + " l:" + str(levels[v]))
        if log: print("path levels: " + str(path_levels))
        if log: print("levels: " + str(levels))
        
        for next_v in adjList[v]:
            if log: print("path:" + str(path))
            # parent node skip step - dfs algo
            if len(path) > 0 and next_v == path[len(path) - 1]:
                continue

            # if path have a cycle
            if next_v not in path or (levels[next_v] == -1 or levels[next_v] not in path_levels):
                if log: print("hi")
                maxLevel = maxLevel + 1
                if log: print("maxLevel " + str(maxLevel))
                deep_level = dfs(next_v, maxLevel, path + [v], path_levels + [levels[v]])
                levels[v] = min(levels[v], deep_level)
            else:
                change_from = max(levels[next_v], levels[v])
                change_to = min(levels[next_v], levels[v])
                levels[v] = change_to
                levels[next_v] = change_to
                for i in range(V):
                    if levels[i] == change_from:
                        if log: print("level reduce")
                        levels[i] = change_to
                        
                                
        return levels[v]

    # start with initial testing point
    dfs(start_v, maxLevel, [], [])
    for v in range(V):
        if visited[v] == False:
            if log: print("dfs for v: " + str(v))
            dfs(v, maxLevel, [], [])
            
    ##if log: print("sort, distinct, final result calc")
    if log: print("final levels: " + str(levels))
            
    return len(set(levels)) - 1

"""
conn5 = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 0, 1, 1, 0]
]
singlePointOfFailure(conn5, log = False, start_v = 3 )
"""

def test_connections(connections, e_qnt, log = False):
    print("Test for adj_list: "+ str(convertToAdjList(connections)))
    for v in range(len(connections)):
        if log: print("Starting from v: " + str(v))
        assert(singlePointOfFailure(connections, start_v = v) == e_qnt)
        if log: print("[OK]")
    print("[OK]")

conn1 = [
    [0, 1],
    [1, 0]
]

test_connections(conn1, 1)

conn2 = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]
test_connections(conn2, 0)
    
conn3 = [
    [0, 1, 1, 1, 0, 0],
    [1, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0]
]
test_connections(conn3, 3)

conn4 = [
    [0, 1, 1, 1, 1],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0]
]
test_connections(conn4, 4)

conn5 = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 1, 0, 1],
    [0, 0, 1, 1, 0]
]
test_connections(conn5, 0, log = True)