Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Breadth-First-Search
#1
Hello Python-Forum,

I'm new to this Forum and very new to Python and programming itself.
We got a homework in our course where we have to implement the breadth-first-search in Python. We also got a script which we have to fill. We have to use classes.
My fellow students and my have got some really big problems with this homework :(
I hope you can help us to solve this task.


Here is the code we got to fill:

import math, queue

class Graph:
    ''' Class Graph.
    Implements an undirected graph, in the form {v: [w1,w2]} for
    edges (v,w1), (v,w2), i.e., adjacency lists.
    Provides a dict "node", with the nodes as keys, to save additional attributes.'''
    def __init__(self):
        self.graph = {}
        self.node = {}
        
    def __iter__(self):
        '''allows to iterate over nodes by "for v in class instances".'''
        return iter(self.graph)
    
    def __len__(self):
        '''returns the number of nodes as len(class instance)'''
        return(len(self.graph))
        
    def add_nodes(self, L):
        '''adds all nodes in list L to graph and intializes their node dict'''
        #TODO
        pass
    
    def has_edge(self, e):
        '''returns True if the tuple e is an edge, False otherwise'''
        #TODO
        pass
    
    def add_edges(self, L):
        '''adds all edge-tuples in the list L to the graph'''
        #TODO
        pass
    
    def number_of_edges(self):
        '''returns the number of edges in the graph'''
        #TODO
        pass
    
    def neighbours(self,v):
        '''returns a list of all neighbours of v'''
        #TODO
        pass


def BFS_init(G, s):
    '''Initializes node dicts in graph class G for color, distance, and predecessor.'''
    for v in G:
        G.node[v]['color'] = 'white'
        G.node[v]['dist'] = float('inf')
        G.node[v]['pi'] = None
    G.node[s]['color'] = 'gray'
    G.node[s]['dist'] = 0
    
        
def BFS(G, s):
    '''Function BFS. Expects a graph class with node attributes and starting node s.
    Implements BFS and saves distances in corresponding node dicts.'''

    BFS_init(G, s)
    
    #TODO
Best regards
Reply
#2
show what you have tried in place of the passes, and we'll be glad to help get it working.
Don't forget that great resource in the sky called Google, it's amazing what you can find.
Reply
#3
That's what I've got so far.
But the unittest we got, gives me Error for every Test.

import math, queue

class Graph:
    ''' Class Graph.
    Implements an undirected graph, in the form {v: [w1,w2]} for
    edges (v,w1), (v,w2), i.e., adjacency lists.
    Provides a dict "node", with the nodes as keys, to save additional attributes.'''
    def __init__(self):
        self.graph = {}
        self.node = {}
        
    def __iter__(self):
        '''allows to iterate over nodes by "for v in class instances".'''
        return iter(self.graph)
    
    def __len__(self):
        '''returns the number of nodes as len(class instance)'''
        return(len(self.graph))
        
    def add_nodes(self, L):
        '''adds all nodes in list L to graph and intializes their node dict'''
        #TODO
        if L not in self.graph:
            self.graph[L] = []
        pass
    
    def has_edge(self, e):
        '''returns True if the tuple e is an edge, False otherwise'''
        #TODO
        if L[0] in self.graph and L[1] in self.graph:
            return True
        else:
            return False
        pass
    
    def add_edges(self, L):
        '''adds all edge-tuples in the list L to the graph'''
        #TODO
        for key, value in self.graph.items():
            if key == L[0]:
                value.add.nodes(L[1])
            else:
                value.add.nodes(L[0])
        pass
    
    def number_of_edges(self):
        '''returns the number of edges in the graph'''
        #TODO
        return int(len(self.graph))
        pass
    
    def neighbours(self,v):
        '''returns a list of all neighbours of v'''
        #TODO
        if v not in self.node:
            self.node.append(v)
            self.node.sort()
        pass


def BFS_init(G, s):
    '''Initializes node dicts in graph class G for color, distance, and predecessor.'''
    for v in G:
        G.node[v]['color'] = 'white'
        G.node[v]['dist'] = float('inf')
        G.node[v]['pi'] = None
    G.node[s]['color'] = 'gray'
    G.node[s]['dist'] = 0
    
        
def BFS(G, s):
    '''Function BFS. Expects a graph class with node attributes and starting node s.
    Implements BFS and saves distances in corresponding node dicts.'''

    BFS_init(G, s)
    
    #TODO
    for u in G:
        G.node[u].get()

    Q = queue

    while queue:

        for v in G:
            if G.node[v] == "white":
                G.node[v] = "gray"
                G.node[v]["dist"] = G.node[u + 1]["dist"]
                G.node[v]["pi"] = G.node[u]


        G.node[u]["color"] = "black"
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020