332 lines
11 KiB
Python
332 lines
11 KiB
Python
# Copyright 2013 Mirantis, Inc.
|
|
#
|
|
# Licensed under the Apache License, Version 2.0 (the "License"); you may
|
|
# not use this file except in compliance with the License. You may obtain
|
|
# a copy of the License at
|
|
#
|
|
# http://www.apache.org/licenses/LICENSE-2.0
|
|
#
|
|
# Unless required by applicable law or agreed to in writing, software
|
|
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
|
|
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
|
|
# License for the specific language governing permissions and limitations
|
|
# under the License.
|
|
|
|
|
|
#!/usr/bin/env python
|
|
import random
|
|
import logging
|
|
import itertools
|
|
|
|
logging.basicConfig()
|
|
logger = logging.getLogger()
|
|
|
|
class Vertex(object):
|
|
def __init__(self, node, interface):
|
|
self.node = node
|
|
self.interface = interface
|
|
def __str__(self):
|
|
return "<Vtx: %s.%s>" % (self.node, self.interface)
|
|
def __repr__(self):
|
|
return self.__str__()
|
|
def __eq__(self, other):
|
|
return self.node == other.node and self.interface == other.interface
|
|
def __ne__(self, other):
|
|
return self.node != other.node or self.interface != other.interface
|
|
def __hash__(self):
|
|
return hash(str(self))
|
|
|
|
|
|
class Arc(object):
|
|
def __init__(self, vertex_a, vertex_b):
|
|
self.arc = (vertex_a, vertex_b)
|
|
def __str__(self):
|
|
return "<Arc: %s>" % (self.arc,)
|
|
def __repr__(self):
|
|
return self.__str__()
|
|
def __getitem__(self, i):
|
|
return self.arc[i]
|
|
def __eq__(self, other):
|
|
l = map(lambda x, y: x == y, self.arc, other.arc)
|
|
return bool(filter(lambda x: x, l))
|
|
def __ne__(self, other):
|
|
l = map(lambda x, y: x != y, self.arc, other.arc)
|
|
return bool(filter(lambda x: x, l))
|
|
def __hash__(self):
|
|
return hash(str(self))
|
|
def invert(self):
|
|
return Arc(self.arc[1], self.arc[0])
|
|
|
|
|
|
class NetChecker(object):
|
|
def __init__(self, nodes, arcs):
|
|
self.nodes = nodes
|
|
self.arcs = arcs
|
|
logger.debug("Init: got %d nodes and %d arcs", len(nodes), len(self.arcs))
|
|
|
|
@staticmethod
|
|
def _invert_arc(arc):
|
|
return arc[1], arc[0]
|
|
|
|
@staticmethod
|
|
def _create_arc(a_vertex, b_vertex):
|
|
return a_vertex, b_vertex
|
|
|
|
@staticmethod
|
|
def _disassm_vertex(vertex):
|
|
index = vertex.find('.')
|
|
node = vertex[:index]
|
|
interface = vertex[index + 1:]
|
|
return node, interface
|
|
|
|
@staticmethod
|
|
def _assm_vertex(node, interface):
|
|
return "%s.%s" % (str(node), str(interface))
|
|
|
|
def get_topos(self):
|
|
""" Main method to collect all possible altermatives of
|
|
interconnection.
|
|
"""
|
|
topos = []
|
|
vertices = set([i[0] for i in self.arcs])
|
|
logger.debug("Get_choices: start with %d vertices", len(vertices))
|
|
while vertices:
|
|
logger.debug("")
|
|
vertex = vertices.pop()
|
|
logger.debug("Get_choices: entry vertex is %s", vertex)
|
|
good_topos, visited_vertices = self._calc_topo(vertex)
|
|
logger.debug("Get_choices: getted %d good_topos",
|
|
len(good_topos))
|
|
logger.debug("Get_choices: getted %d visited_vertices: %s",
|
|
len(visited_vertices), visited_vertices)
|
|
|
|
topos.extend(good_topos)
|
|
vertices.difference_update(visited_vertices)
|
|
logger.debug("Get_choices: %d untracked vertices left: %s",
|
|
len(vertices), vertices)
|
|
return self._uniq_topos(topos)
|
|
|
|
def _calc_topo(self, start_vertex):
|
|
topos = []
|
|
visited_vertices = set()
|
|
|
|
def extend_arcs_to_check(arcs_to_check, arcs):
|
|
for failed_v, ignored_v in arcs:
|
|
existed_arcs = filter(
|
|
lambda x: x[0] == failed_v, arcs_to_check)
|
|
if existed_arcs:
|
|
existed_arc = existed_arcs[0]
|
|
existed_arc[1].append(ignored_v)
|
|
else:
|
|
arcs_to_check.append((failed_v, [ignored_v]))
|
|
|
|
# arcs_to_check consists of arcs (x, y) where
|
|
# x - failed vertex,
|
|
# y - list of vertices which should be ignored.
|
|
arcs_to_check = [(start_vertex, [])]
|
|
for fv, ignored_vertices in arcs_to_check:
|
|
found_vertices = [fv]
|
|
failed_arcs = []
|
|
|
|
for vertex in found_vertices:
|
|
neighbors = self._get_neighbors(vertex)
|
|
logger.debug("_calc_topo: for vtx %s a neigbors found: %s",
|
|
vertex, neighbors)
|
|
new_vertices, absent_vertices = self._diff_lists(
|
|
found_vertices, ignored_vertices, neighbors
|
|
)
|
|
logger.debug("_calc_topo: new vtx found: %s", new_vertices)
|
|
logger.debug("_calc_topo: absent_vertices is %s",
|
|
absent_vertices)
|
|
if absent_vertices:
|
|
for v in absent_vertices:
|
|
failed_arc = (v, vertex)
|
|
if failed_arc not in failed_arcs:
|
|
failed_arcs.append(failed_arc)
|
|
found_vertices.extend(new_vertices)
|
|
|
|
failed_vertices = [x[0] for x in failed_arcs]
|
|
topo = self._validate_topo(found_vertices, failed_vertices)
|
|
visited_vertices.update(found_vertices)
|
|
visited_vertices.update(failed_vertices)
|
|
if topo:
|
|
topos.append(topo)
|
|
extend_arcs_to_check(arcs_to_check, failed_arcs)
|
|
return topos, visited_vertices
|
|
|
|
def _get_neighbors(self, vertex):
|
|
arcs = filter(
|
|
lambda x: x[0] == vertex,
|
|
self.arcs)
|
|
return [x[1] for x in arcs]
|
|
|
|
@staticmethod
|
|
def _diff_lists(found_vertices, ignored_vertices, neighbours):
|
|
new_vertices = []
|
|
absent_vertices = []
|
|
for n in found_vertices:
|
|
if n in neighbours:
|
|
neighbours.remove(n)
|
|
else:
|
|
absent_vertices.append(n)
|
|
new_vertices = [n for n in neighbours if n not in ignored_vertices]
|
|
return new_vertices, absent_vertices
|
|
|
|
def _validate_topo(self, found_v, failed_v):
|
|
logger.debug("_validate_topo: found_vertices is: %s", found_v)
|
|
logger.debug("_validate_topo: failed_vertices is: %s", failed_v)
|
|
topo = {}
|
|
for v in found_v:
|
|
if v in failed_v:
|
|
continue
|
|
node, interface = self._disassm_vertex(v)
|
|
interfaces = topo.get(node)
|
|
if interfaces:
|
|
interfaces.append(interface)
|
|
else:
|
|
topo[node] = [interface]
|
|
if set(self.nodes) != set(topo.keys()):
|
|
return None
|
|
for l in topo.values():
|
|
l.sort()
|
|
return topo
|
|
|
|
def _uniq_topos(self, topos):
|
|
def isincluded(topo, topos):
|
|
for at in topos:
|
|
included = True
|
|
for n in self.nodes:
|
|
if not set(topo[n]).issubset(set(at[n])):
|
|
included = False
|
|
if included:
|
|
return True
|
|
return False
|
|
|
|
copy = []
|
|
logger.debug("_uniq_topos: topos is %s" % topos)
|
|
for t in topos:
|
|
logger.debug("_uniq_topos: now testing: %s" % t)
|
|
if not isincluded(t, [i for i in topos if id(i) != id(t)]):
|
|
copy.append(t)
|
|
return copy
|
|
|
|
|
|
class ClassbasedNetChecker(NetChecker):
|
|
@staticmethod
|
|
def _invert_arc(arc):
|
|
return arc.invert()
|
|
|
|
@staticmethod
|
|
def _create_arc(a_vertex, b_vertex):
|
|
return Arc(a_vertex, b_vertex)
|
|
|
|
@staticmethod
|
|
def _disassm_vertex(vertex):
|
|
return vertex.node, vertex.interface
|
|
|
|
@staticmethod
|
|
def _assm_vertex(node, interface):
|
|
return Vertex(node, interface)
|
|
|
|
|
|
|
|
|
|
|
|
def generateFullMesh(nodes, interfaces, Klass, stability=1.0):
|
|
A = []
|
|
vertices = itertools.product(nodes, interfaces, nodes, interfaces)
|
|
for n1, i1, n2, i2 in vertices:
|
|
# Drop some arcs if stability < 1.0
|
|
if stability == 1.0 or random.random() < stability:
|
|
a_vertex = Klass._assm_vertex(n1, i1)
|
|
b_vertex = Klass._assm_vertex(n2, i2)
|
|
arc = Klass._create_arc(a_vertex, b_vertex)
|
|
A.append(arc)
|
|
logger.debug("generateArcs: %d arcs generated", len(A))
|
|
return A
|
|
|
|
def generateMesh(nodes1, ifaces1, nodes2, ifaces2, Klass, stability=1.0):
|
|
A = []
|
|
vertices = itertools.product(nodes1, ifaces1, nodes2, ifaces2)
|
|
for n1, i1, n2, i2 in vertices:
|
|
# Drop some arcs if stability < 1.0
|
|
if stability == 1.0 or random.random() < stability:
|
|
a_vertex = Klass._assm_vertex(n1, i1)
|
|
b_vertex = Klass._assm_vertex(n2, i2)
|
|
arc = Klass._create_arc(a_vertex, b_vertex)
|
|
A.append(arc)
|
|
logger.debug("generateArcs: %d arcs generated", len(A))
|
|
return A
|
|
|
|
|
|
def printChoice(choice, step=4):
|
|
def printlist(l, indent=0, step=2):
|
|
print '%s[' % (' ' * indent)
|
|
for i in l:
|
|
if type(i) is dict:
|
|
print '%s-' % (' ' * indent)
|
|
printdict(i, indent + step, step)
|
|
elif type(i) in (list, tuple):
|
|
printlist(i, indent + step, step)
|
|
else:
|
|
print '%s- %s' % (' ' * indent, str(i))
|
|
print '%s]' % (' ' * indent)
|
|
def printdict(d, indent=0, step=2):
|
|
for k, v in d.iteritems():
|
|
if type(v) is dict:
|
|
print '%s%s:' % (' ' * indent, str(k))
|
|
printdict(v, indent + step, step)
|
|
elif type(v) in (list, tuple):
|
|
print '%s%s:' % (' ' * indent, str(k))
|
|
printlist(v, indent + step, step)
|
|
else:
|
|
print '%s%s: %s' % (' ' * indent, str(k), str(v))
|
|
if type(choice) is dict:
|
|
printdict(choice, step=step)
|
|
elif type(choice) is list:
|
|
printlist(choice, step=step)
|
|
else:
|
|
print choice
|
|
|
|
|
|
|
|
|
|
|
|
print ""
|
|
|
|
nodes = ['s1', 's2', 's3', 's4']
|
|
interfaces = ['i0', 'i1', 'i2', 'i3']
|
|
logger.setLevel(logging.DEBUG)
|
|
|
|
Klass = ClassbasedNetChecker
|
|
Klass = NetChecker
|
|
arcs = []
|
|
# arcs.extend(generateFullMesh(nodes[:2], interfaces[:2], Klass, 0.9))
|
|
# #arcs.extend(generateFullMesh(nodes[:2], interfaces[2:], Klass))
|
|
# arcs.extend(generateMesh(nodes[2:3], interfaces[0:1],
|
|
# nodes[:3], interfaces[0:2], Klass))
|
|
# arcs.extend(generateMesh(nodes[:2], interfaces[0:2],
|
|
# nodes[2:3], interfaces[0:1], Klass))
|
|
# netcheck = Klass(nodes[:3], arcs)
|
|
|
|
nodes = [str(i) for i in xrange(200)]
|
|
interfaces = [str(i) for i in xrange(4)]
|
|
arcs = generateFullMesh(nodes, interfaces, Klass)
|
|
netcheck = Klass(nodes, arcs)
|
|
logger.setLevel(logging.INFO)
|
|
choices = netcheck.get_topos()
|
|
|
|
#printChoice(arcs)
|
|
# print ""
|
|
# for i in xrange(len(choices)):
|
|
# print "\n---- Choice number %d: ----\n" % (i + 1)
|
|
# printChoice(choices[i])
|
|
if not choices:
|
|
print "No choices found"
|
|
else:
|
|
print "%d choices found" % len(choices)
|
|
print ""
|
|
|
|
#import time
|
|
#time.sleep(5)
|