мне нужно использовать этот класс для реализации алгоритма бипарита, используя BFS, моя проблема - сравнение вершины с противоположной вершиной, я хочу вернуть None, если у вершины того же цвета противоположная вершина на том же уровне, нужно использоватьсложность O (n + m), n цифр вершины, число ребер m.
это код
class Graph:
"""Representation of a simple graph using an adjacency map."""
#------------------------- nested Vertex class -------------------------
class Vertex:
"""Lightweight vertex structure for a graph."""
__slots__ = '_element'
def __init__(self, x):
"""Do not call constructor directly. Use Graph's insert_vertex(x)."""
self._element = x
def element(self):
"""Return element associated with this vertex."""
return self._element
def __hash__(self): # will allow vertex to be a map/set key
return hash(id(self))
def __str__(self):
return str(self._element)
#------------------------- nested Edge class -------------------------
class Edge:
"""Lightweight edge structure for a graph."""
__slots__ = '_origin', '_destination', '_element'
def __init__(self, u, v, x):
"""Do not call constructor directly. Use Graph's insert_edge(u,v,x)."""
self._origin = u
self._destination = v
self._element = x
def endpoints(self):
"""Return (u,v) tuple for vertices u and v."""
return (self._origin, self._destination)
def opposite(self, v):
"""Return the vertex that is opposite v on this edge."""
if not isinstance(v, Graph.Vertex):
raise TypeError('v must be a Vertex')
if v is self._origin:
return self._destination
elif v is self._destination:
return self._origin
raise ValueError('v not incident to edge')
def element(self):
"""Return element associated with this edge."""
return self._element
def __hash__(self): # will allow edge to be a map/set key
return hash( (self._origin, self._destination) )
def __str__(self):
return '({0},{1},{2})'.format(self._origin,self._destination,self._element)
#------------------------- Graph methods -------------------------
def __init__(self, directed=False):
"""Create an empty graph (undirected, by default).
Graph is directed if optional paramter is set to True.
"""
self._outgoing = {}
# only create second map for directed graph; use alias for undirected
self._incoming = {} if directed else self._outgoing
def _validate_vertex(self, v):
"""Verify that v is a Vertex of this graph."""
if not isinstance(v, self.Vertex):
raise TypeError('Vertex expected')
if v not in self._outgoing:
raise ValueError('Vertex does not belong to this graph.')
def is_directed(self):
"""Return True if this is a directed graph; False if undirected.
Property is based on the original declaration of the graph, not its contents.
"""
return self._incoming is not self._outgoing # directed if maps are distinct
def vertex_count(self):
"""Return the number of vertices in the graph."""
return len(self._outgoing)
def vertices(self):
"""Return an iteration of all vertices of the graph."""
return self._outgoing.keys()
def edge_count(self):
"""Return the number of edges in the graph."""
total = sum(len(self._outgoing[v]) for v in self._outgoing)
# for undirected graphs, make sure not to double-count edges
return total if self.is_directed() else total // 2
def edges(self):
"""Return a set of all edges of the graph."""
result = set() # avoid double-reporting edges of undirected graph
for secondary_map in self._outgoing.values():
result.update(secondary_map.values()) # add edges to resulting set
return result
def get_edge(self, u, v):
"""Return the edge from u to v, or None if not adjacent."""
self._validate_vertex(u)
self._validate_vertex(v)
return self._outgoing[u].get(v) # returns None if v not adjacent
def degree(self, v, outgoing=True):
"""Return number of (outgoing) edges incident to vertex v in the graph.
If graph is directed, optional parameter used to count incoming edges.
"""
self._validate_vertex(v)
adj = self._outgoing if outgoing else self._incoming
return len(adj[v])
def incident_edges(self, v, outgoing=True):
"""Return all (outgoing) edges incident to vertex v in the graph.
If graph is directed, optional parameter used to request incoming edges.
"""
self._validate_vertex(v)
adj = self._outgoing if outgoing else self._incoming
for edge in adj[v].values():
yield edge
def insert_vertex(self, x=None):
"""Insert and return a new Vertex with element x."""
v = self.Vertex(x)
self._outgoing[v] = {}
if self.is_directed():
self._incoming[v] = {} # need distinct map for incoming edges
return v
def insert_edge(self, u, v, x=None):
"""Insert and return a new Edge from u to v with auxiliary element x.
Raise a ValueError if u and v are not vertices of the graph.
Raise a ValueError if u and v are already adjacent.
"""
if self.get_edge(u, v) is not None: # includes error checking
raise ValueError('u and v are already adjacent')
e = self.Edge(u, v, x)
self._outgoing[u][v] = e
self._incoming[v][u] = e
#grafo si puo implemtare sia con lista/mappe di adiacenza prende tempo O(n +m )
#mancano gli import delle librerie
def bipartite(self,src):
discovered = {}
count_level = 0
level =[src]
color= {src:1}
if g.vertex_count() == 1:
return none
while len(level) > 0:
next_level = []
for u in level:
for e in g.incident_edges(u):
v = e.opposite(u)
if v not in discovered:
discovered[v] = e
if count_level % 2 == 0:
color[v] = 1
next_level.append(v)
count_level++
else:
color[v] = 0
next_level.append(v)
count_level++
if color[u] == color [v]:
return None
level = next_level
return True
я изменяю этот код:
def BFS(g, s, discovered):
"""Perform BFS of the undiscovered portion of Graph g starting at Vertex s.
discovered is a dictionary mapping each vertex to the edge that was used to
discover it during the BFS (s should be mapped to None prior to the call).
Newly discovered vertices will be added to the dictionary as a result.
"""
level = [s] # first level includes only s
while len(level) > 0:
next_level = [] # prepare to gather newly found vertices
for u in level:
for e in g.incident_edges(u): # for every outgoing edge from u
v = e.opposite(u)
if v not in discovered: # v is an unvisited vertex
discovered[v] = e # e is the tree edge that discovered v
next_level.append(v) # v will be further considered in next pass
level = next_level # relabel 'next' level to become current
def BFS_complete(g):
"""Perform BFS for entire graph and return forest as a dictionary.
Result maps each vertex v to the edge that was used to discover it.
(vertices that are roots of a BFS tree are mapped to None).
"""
forest = {}
for u in g.vertices():
if u not in forest:
forest[u] = None # u will be a root of a tree
BFS(g, u, forest)
return forest