Implementation graph operations algorithms-CodePudding

This code is some operations of a graph implementation, I would like some help to implement the input request which is in the style:

example operations:
IV A        insert vertex with id==A into the graph;
IA A B P    inserts an edge from the vertex of id==A to the vertex of id==B with weight P, if the vertices exist;
RV A        removes the vertex of id==A, if it exists, and all edges related to it; 
RA A B      remove the edge from the vertex of id==A to the vertex of id==B, if it exists;

Where N is any number that determines the number of operations to be performed, in the case of the example there are 4, and the rest are commands:

INPUT EXAMPLE:
4
IV A
IA B A 1
IV B
IA A B 2

OUTPUT: Present the vertex number, number of edges and total sum of weights information
EXAMPLE:
2 vertex, 1 edge and total weight 2.00.

I would like help just to know how to read the entries and call the functions, thanks!!

def add_node(v):
    if v in graph:
        print(v, "is already part of the graph")
        
    else:
        graph[v] = []

def add_edge(v1,v2,cost):
    if v1 and v2 not in graph:
        print("not part of the graph")
        
    else:
        list1 = [v2,cost]
        list2 = [v1,cost]
        graph[v1].append(list1)
        graph[v2].append(list2)

def delete_node(v):
    if v not in graph:
        print(v,"not part of the graph")
        
    else:
        graph.pop(v)
        for i in graph:
            list1 = graph[i]
            for j in list1:
                if v == j[0]:
                    list1.remove(j)
                
def delete_edge(v1,v2,cost):
    if v1 and v2 not in graph:
        print("not part of the graph")
        
    else:
        temp = [v1, cost]
        temp1 = [v2, cost]
        if temp1 in graph[v1]:
            graph[v1].remove(temp1)
            graph[v2].remove(temp)

CodePudding user response：

I would like help just to know how to read the entries and call the functions

For that purpose you can add the following code below your functions:

# main program
method = {
    "IV": add_node,
    "IA": add_edge,
    "RV": delete_node,
    "RA": delete_edge
}
numinputlines = int(input())
for _ in range(numinputlines):
    instruction, *rest = input().split()
    if len(rest) == 3:  # There is a cost:
        rest[-1] = int(rest[-1])
    method[instruction](*rest)

The method dictionary helps to translate a 2-letter code to a method that needs to be called. As the arguments to those methods are all in the same order, you can just capture those in a list rest, and "unpack" that list when passing the arguments. There is just one special thing to take care of. Two methods get a cost argument, and it must be of number type. Since input is read as string, you need to convert that cost string to a number. The if statement takes care of this case.

This should answer your question, but it does not finish the exercise. You will still have to debug your code. For instance, currently your code will raise an exception on the example input you have given -- vertex "B" is referenced in IA B A 1 before it is added with IV B.

Also, you'll need to add the code to produce the output.

But since your question was about capturing the input and calling the functions, I have left the rest for you to tackle.

CodePudding user response：

I made little modifications on the graph functions since there were little mistakes. Although it's not the best implementation of graphs, I didn't want to make major change to stick to your own implementation.

def add_node(v):
    if v in graph.keys() :
        print(v, "is already part of the graph")
        
    else:
        graph[v] = []

def add_edge(v1,v2,cost):
    keys = graph.keys()
    if v1 not in keys or v2 not in keys:
        print("not part of the graph")
        
    else:
        list1 = [v2,cost]
        list2 = [v1,cost]
        graph[v1].append(list1)
        graph[v2].append(list2)

def delete_node(v):
    if v not in graph.keys():
        print(v,"not part of the graph")
        
    else:
        graph.pop(v)
        for i in graph.keys():
            list1 = graph[i]
            for j in list1:
                if v == j[0]:
                    list1.remove(j)
                
def delete_edge(v1,v2):
    keys = graph.keys()
    if v1 not in keys or v2 not in keys:
        print("not part of the graph")
        
    else:
        graph[v1] = [x for x in graph[v1] if x[0] != v2]
        graph[v2] = [x for x in graph[v2] if x[0] != v1]
            
graph = {}
no_operations = int(input("Enter number of operations: "))

for opt in range(no_operations):
    command = input("Enter command: ").split()
    if(command[0] == 'IV'):
        A = command[1]
        add_node(A)
    elif(command[0] == 'IA'):
        B = command[1]
        A = command[2]
        P = int(command[3])
        add_edge(A, B, P)
    elif(command[0] == 'RV'):
        B = command[1]
        delete_node(B)
    elif(command[0] == 'RA'):
        A = command[1]
        B = command[2]
        delete_edge(A, B)
    else:
        print("Invalid command")
print(graph)