0

In general, what is the question, there is a list (graph). If you run this code. That result will be not full but i want that the result will be where the arrow shows. How to fix my problem? If you could rewrite this code. I tryid use 1 more list for keys (first number in pair) and finding this and rewrite to second list. I want to go down the graph. RESULT

link = [[1, 3], [3, 2], [2, 6], [1, 4], [4, 3], [3, 7], [7, 8], [8, 9]]

link_keys = []
cpy_link = []
number = 0
diametr = 0
k = len(link)
m = 0

def circle_for_net(number):
    for j in range(k):
        while number == link[j][0]:
            number = link[j][1]
            cpy_link.append(number)
            circle_for_net(number)
            number = 0
            break

def create_keys(link):
    for j in range(k):
        link_keys.append(link[j][0])

for i in range(k - 1):
    for j in range(k - i - 1):
        if link[j][0] > link[j + 1][0]:
            link[j], link[j + 1] = link[j + 1], link[j]

create_keys(link)
for i in range(k):
    number = link[i][1]
    cpy_link.append(link[i][0])
    cpy_link.append(number)
    circle_for_net(number)
    print(cpy_link)
    if(diametr < len(cpy_link)):
        diametr = len(cpy_link)
    cpy_link.clear()

print(diametr)
Destroyer
  • 1
  • 1

1 Answers1

1

Seems you want to find all possible paths from source nodes to sink nodes in a directed acyclic graph (DAG). This has an answer here, but only for a single pair of nodes:

def paths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong
        memo_dict = dict()

    if source_node == sink_node or source_node not in nodes_children: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = []
            for new_source in nodes_children[source_node]:
                p = paths(new_source, sink_node, memo_dict)
                for path in p:
                    path = (source_node,) + path
                    result.append(path)
            #result = frozenset(result)
            # Memorize answer
            memo_dict[(source_node, sink_node)] = result
            return result

Assuming you have a dictionary nodes_children = {1: [3, 4], 3: [2, 7], 2: [6], 4: [3], 7: [8], 8: [9]} mapping nodes to its children, as well as an array sinks = [6, 9] with the sinks in your DAG, this can easily be extended to find all such paths:

def allpaths(nodes_children, sinks):
    result = []
    for sink in sinks:
        for source in nodes_children:
            result.append(paths(source, sink))
    # flatten the list
    result = [r for res in result for r in res]

    # remove duplicates while keeping order
    seen = set()
    seen_add = seen.add
    result = [x for x in result if not (x in seen or seen_add(x))]
    return result

Finally, if you do not want to compute nodes_children and sinks by hand, you could write

def get_sinks(link):
    sinks = []  # will store 6 and 9
    for edge in link:
        potential_sink = edge[1]
        is_sink = True
        for edge in link:
            if edge[0] == potential_sink:
                is_sink = False
        if is_sink:
            sinks.append(potential_sink)
    return sinks
# [6, 9]
sinks = get_sinks(link)

def dict_children(link):
    nodes_children = {}
    for edge in link:
        l_node = edge[0]
        r_node = edge[1]
        if l_node in nodes_children:
            nodes_children[l_node].append(r_node)
        else:
            nodes_children[l_node] = [r_node]
    return nodes_children
# {1: [3, 4], 3: [2, 7], 2: [6], 4: [3], 7: [8], 8: [9]}
nodes_children = dict_children(link)
hellovertex
  • 23
  • 5