How do I create a mixed graph for BFS in Python?-CodePudding

It is my first question (here) ever, so I'm sorry in advance if anything is wrong. The task is: create a graph that can contain both oriented edges and unoriented edges by using Edge List (it is need for a BFS search). For example: mixed graph. In this graph, Edge List would be this format (edge_number: start_vertex end_vertex):

0: 0 1
1: 0 3
2: 1 2
3: 1 3
4: 2 1
5: 3 0
6: 3 2

Here is the code with output:

print("First number is nodes, second number is edges: ")
N, M = map(int, input().split()) #N is nodes and M is edges
print(f"Now graph has {N} nodes and {M} edges")

print("\nNow input all neighbours: ")
graph = {i: set() for i in range(N)} #store as a dictionary
for i in range(M): #in the cycle add all of the M edges 
    v1, v2 = map(int, input().split()) #inputting start_vertex and end_vertex
    graph[v1].add(v2) #adding adjacency of two nodes 
    print(f"graph v1 is {graph[v1]}")
    graph[v2].add(v1)
    print(f"graph v2 is {graph[v2]}")
        
    print("\nNow you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}")
    for key, value in graph.items():
        print("{0}: {1}".format(key,value))

And the output:

First number is nodes, second number is edges:
4 7
Now graph has 4 nodes and 7 edges

Now input all neighbours:
0 1
graph v1 is {1}
graph v2 is {0}
0 3
graph v1 is {1, 3}
graph v2 is {0}
1 2
graph v1 is {0, 2}
graph v2 is {1}
1 3
graph v1 is {0, 2, 3}
graph v2 is {0, 1}
2 1
graph v1 is {1}
graph v2 is {0, 2, 3}
3 0
graph v1 is {0, 1}
graph v2 is {1, 3}
3 2
graph v1 is {0, 1, 2}
graph v2 is {1, 3}

Now you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}
0: {1, 3}
1: {0, 2, 3}
2: {1, 3}
3: {0, 1, 2}

The key point is, console says that node_3 has arrows (oriented edges) to node_0, node_1 and node_2. Apparently (in console I repeated graph from picture) node_3 should have only one oriented edge (number 5 on pic) to node_2 and one unoriented edge (number 6 on pic) to node_0, but the console says it has one more connection - with node_1 (and that's the problem).

In other words, code I listed above finds all of the neighbours of the current node, but it should show us only possible routes, i.e. the last console string should be "3: {0, 2}". How do I fix it? I have some guesses about sets' methods like set.update(x) or set.difference(x), but honestly have no idea.

Thank you very much for your time and possible solution.

P.S. If you wonder about full code:

from collections import deque
print("First number is nodes, second number is edges: ")
N, M = map(int, input().split()) #N is nodes and M is edges
print(f"Now graph has {N} nodes and {M} edges")
    
print("\nNow input all neighbours: ")
graph = {i: set() for i in range(N)} #store as a dictionary
for i in range(M): #in the cycle add all of the M edges 
    v1, v2 = map(int, input().split()) #inputting start_vertex and end_vertex
    graph[v1].add(v2) #adding adjacency of two nodes 
    print(f"graph v1 is {graph[v1]}")
    graph[v2].add(v1)
    print(f"graph v2 is {graph[v2]}")
            
        print("\nNow you'll see all nodes: {their neighbours}: ------------HERE YOU SHOULD SEE POSSIBLE ROUTES LIKE NODE: {POSSIBLE_ROUTE_TO}")
        for key, value in graph.items():
            print("{0}: {1}".format(key,value))

for start_vertex in range(N):
    print(f"\n------------------------------------------START VERTEX IS {start_vertex} NOW----------------------------------------")

    distances = [None] * N 
    distances[start_vertex] = 0 #distance to ourself = 0
    queue = deque([start_vertex]) # init queue as a deque 
    parents = [None] * N

    while queue: #until queue is empty
        current_vertex = queue.popleft() #take 1st elem
        for neighbours_vertex in graph[current_vertex]: #going through its neighbours
            if distances[neighbours_vertex] is None: #if neigh hasn't been visited (distance = none)
                distances[neighbours_vertex] = distances[current_vertex]   1 #now counting distance
                parents[neighbours_vertex] = current_vertex
                queue.append(neighbours_vertex) #add to queue for we'll check neighbours later
    print("Now you'll see the distances from start_vertex to all of them nodes in 0...N format: ", distances)   
    
    for end_vertex in range(N):
        print(f"END VERTEX IS {end_vertex} NOW")
        parent = parents[end_vertex]
        path = [end_vertex] 

        while not parent is None: 
            path.append(parent)
            parent = parents[parent]
        print(f"Optimal path from start_vertex {start_vertex} to end_vertex {end_vertex}", path[::-1])

CodePudding user response：

The correct term for what you call orientated is directed.

You cannot mix directed and undirected links in one graph.

You can have an undirected graph, where every link goes in both direction.

You can have a directed graph, where each link goes in one direction and if you want to specify that you can go from A to B and B to A then you need two links between the nodes one going in each direction.

In your input code you have

graph[v1].add(v2) 
graph[v2].add(v1)

So every time you input a pair of nodes, you ALWAYS add two directed edges going both ways. You are making no distinction between pairs of nodes where you want a one way connection and were you want a link going in just one direction. Best guess: you should remove the second line of code.