G=Graph({1:[2],5:[6],3:[1,2,5,6,4]}); 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()))
|
maximum grad knots: set([3])
one of the longest shortest paths: [4, 3, 1]
it is a tree: False
complement:
BEISPIEL 10 & 11
solutions=[] #appends all paths from a to b which are shorter than |g.edges()| to solutions
def path(g,a,b,c=0,li=[]): #and returns if there is a solution
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)
a=4; b=7
G=Graph({1:[2,7],5:[6],3:[1,2,5,6,4]})
show(plot(G))
if path(G,a,b):
M=[len(x) for x in solutions];
print "shortest path from",a,"to",b,[a]+solutions[M.index(min(M))]
else:
print "there is no path from",a,"to",b
|
shortest path from 4 to 7 [4, 3, 1, 7]