default_ex="Graph({1:[2],5:[6],3:[1,2,5,6,4]})"
def main(ex=default_ex):
G = eval(ex); show(plot(G))
M=sum(G.cliques_maximum(),[])
print "maximum grad knots:",set([y for y in M if M.count(y)==max([M.count(x) for x in M])])
M=sum([[G.shortest_path(a,b) for a in G.vertices()] for b in G.vertices()],[]) #flatten list
N=[len(x) for x in M]
print "one of the longest shortest paths:",M[N.index(max(N))]
print "it is a tree:",G.is_tree(),"\ncomplement:"; show(plot(G.complement()))
main() #decide between just executing and
#@interact #showing the GUI
def gui(ex=default_ex):
main(ex)
|
maximum grad knots: set([3])
one of the longest shortest paths: [4, 3, 1]
it is a tree: False
complement:
BEISPIEL 10 & 11
default_ex="Graph({1:[2,7],5:[6],3:[1,2,5,6,4]})"
default_a=4
default_b=7
def main(ex=default_ex,a=default_a,b=default_b):
G = eval(ex); show(plot(G))
solutions=[]
def path(g,a,b,c=0,li=[]):
if a==b:
solutions.append(li)
return (a==b or true in [path(g,x,b,c+1,li+[x]) for x in g.neighbors(a)] if c<=len(g.edges()) else false)
if path(G,a,b):
M=[len(x) for x in solutions]
print "shortest path from",a,"to",str(b)+":",[a]+solutions[M.index(min(M))]
else:
print "there is no path from",a,"to",b
main() #decide between just executing and
#@interact #showing the GUI
def gui(ex=default_ex,a=default_a,b=default_b):
main(ex,a,b)
|
shortest path from 4 to 7:
[4, 3, 1, 7]