flowgrap.py

#!/usr/bin/env python3

def display_graph(graph):
    """
        Display the graph as an adjacency matrix
    """
    for row in graph:
        print(row)

def create_graph(entrances,exits,path):
    """
        This will returns the graph as an adjacency matrix,
        with one source (row 0) and one sink (row len(path) + 2)
    """
    nrow = len(path)
    graph = [[0 for j in range(nrow+2)] for i in range(nrow+2)]

    # connect the main source to the sources with infinite capacity
    for source in entrances:
        graph[0][source+1] = -1

    # Add the connectivity flow 
    for irow, row  in enumerate(path):
        for ival, val in enumerate(path[irow]):
            graph[irow+1][ival+1] = val

    # connect the exits to the main sink with infinite capacity
    for sink in exits:
        graph[sink+1][nrow+1] = -1

    return graph

def is_connected_(graph,graph_mark,source,dest):
    found = False
    for j, val in enumerate(graph[source]):
        if found:
            break
        if j == source:
            continue
        if graph_mark[source][j]:
            continue
        graph_mark[source][j] = True
        if val != 0:
            if j == dest:
                return True
            else:
                found = is_connected_(graph,graph_mark,j,dest)
    return found

def is_connected(graph,source,dest):
    """
        returns true if there's a path from source to dest
    """
    nrow = len(graph)
    # Creating the residual graph information
    # graph_mark[i][j] = True, means we already used that edge
    graph_mark = [[False for j in range(nrow)] for i in range(nrow)]
    return is_connected_(graph,graph_mark,source,dest)

def compute_flow(graph):
    return -1

entrances = [0,1]
exits = [4,5]
path = [
    [0,0,4,6,0,0],
    [0,0,5,2,0,0],
    [0,0,0,0,4,4],
    [0,0,0,0,6,6],
    [0,0,0,0,0,0],
    [0,0,0,0,0,0]
]

graph = create_graph(entrances,exits,path)

display_graph(graph)

print("max flow is",compute_flow(graph))