Click here to Skip to main content
15,867,906 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi! I am currently developing a custom algorithm that implements the Havel-Hakimi algorithm choosing a node randomly. Unfortunately I have run into a logical error that is hard for me to trace (since I am a beginner in programming).I would appreciate it if someone could help me spot the issue. What happens is I get the correct sequence returned sometimes, but other times not

Python
import networkx as nx
import matplotlib.pyplot as plt
import random

def nodes_connected(G,u,v):
    return u in G.neighbors(v)

def hh_graph(seq):
    if not(nx.is_graphical(seq)):
        print("Sequence is not graphical")
    else:
        #Randomly mix the degree sequence
        random.shuffle(seq)
        #Create graph
        G = nx.Graph()
        G.add_nodes_from(range(1,len(seq)+1))
        #Repeat for every node in the sequence
        for i in range(0,len(seq)):
            #j stores number of edges to be added
            j=seq[i]
            #selected node is zeroed
            seq[i]=0
            #Repeat till all edges have been connected
            while j>0:
                k=0
                done=False
                #Repeat till finding a suitable node to connect to
                while k<len(seq) and done==False :
                    #Check to connect to a maximum value node,and avoiding a duplicate connection
                    if seq[k]==max(seq) and nodes_connected(G,i+1,k+1)==False:
                        G.add_edges_from([[i+1,k+1]])
                        seq[k]-=1
                        done=True
                    k+=1
                j-=1
        #Check graph degree sequence to validate results
        degree_sequence = [d for n, d in G.degree()]
        print(f"Graph degree sequence {degree_sequence}")
        #nx.draw_networkx(G)
        #plt.show()

A=[5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3]
B=[6, 3, 3, 3, 3, 2, 2, 2, 2, 2,1,1]
C=[4,3,2,1]
hh_graph(A)
hh_graph(B)
hh_graph(C)


What I have tried:

I have tried to focus on the loops where I think there might be an issue.I have tested different if cases and implementations,but still cant understand how it works half of the time and other times not
Posted
Updated 26-Mar-22 21:49pm

1 solution

Read and understand the theoritical basics and use some simple examples as test input for your code to see where the problem is.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900