Threshold Graphs
================

>>> import networkx as NX
>>> from networkx.threshold import *
>>> from networkx.isomorph import graph_could_be_isomorphic
>>> import string
>>> from networkx.operators import convert_node_labels_to_integers as cnlti


>>> try:
...     import numpy as N
...	eigenval=N.linalg.eigvals
... except ImportError:
...     raise ImportError,"numpy can not be imported."

Threshold Sequence and Graph Test
---------------------------------

>>> G=NX.star_graph(10)
>>> is_threshold_graph(G)
True
>>> is_threshold_sequence(G.degree())
True

>>> G=NX.complete_graph(10)
>>> is_threshold_graph(G)
True
>>> is_threshold_sequence(G.degree())
True

>>> deg=[3,2,2,1,1,1]
>>> is_threshold_sequence(deg)
False

>>> deg=[3,2,2,1]
>>> is_threshold_sequence(deg)
True

>>> G=NX.generators.havel_hakimi_graph(deg)
>>> is_threshold_graph(G)
True

Creation Sequences
------------------

>>> cs0=creation_sequence(deg)
>>> H0=threshold_graph(cs0)
>>> string.join(cs0,'')
'ddid'


>>> cs1=creation_sequence(deg, with_labels=True)
>>> H1=threshold_graph(cs1)
>>> cs1
[(1, 'd'), (2, 'd'), (3, 'i'), (0, 'd')]

>>> cs2=creation_sequence(deg, compact=True)
>>> H2=threshold_graph(cs2)
>>> cs2
[2, 1, 1]


>>> string.join(uncompact(cs2),'')
'ddid'

>>> graph_could_be_isomorphic(H0,G)
True
>>> graph_could_be_isomorphic(H0,H1)
True
>>> graph_could_be_isomorphic(H0,H2)
True
    
Shortest Path
-------------

>>> shortest_path(cs1,3,0)==NX.shortest_path(G, 3, 0)
True
>>> shortest_path(cs1,0,3)==NX.shortest_path(G, 0, 3)
True
>>> shortest_path(cs1,0,2)==NX.shortest_path(G, 0, 2)
True
>>> shortest_path(cs1,0,1)==NX.shortest_path(G, 0, 1)
True
>>> shortest_path(cs1,1,3)==NX.shortest_path(G, 1, 3)
True
>>> shortest_path(cs1,3,1)==NX.shortest_path(G, 3, 1)
True
>>> shortest_path(cs1,1,2)==NX.shortest_path(G, 1, 2)
True
>>> shortest_path(cs1,2,3)==NX.shortest_path(G, 2, 3)
True

>>> spl=shortest_path_length(cs1,3)
>>> spl2=shortest_path_length([ t for v,t in cs1],2)
>>> spl==spl2
True

>>> spld={}
>>> for j,pl in enumerate(spl):
...     n=cs1[j][0]
...     spld[n]=pl
>>> spld==NX.single_source_shortest_path_length(G, 3)
True

Weights and thresholds
----------------------
>>> wseq=[3,4,3,3,5,6,5,4,5,6]
>>> cs=weights_to_creation_sequence(wseq,threshold=10)
>>> wseq=creation_sequence_to_weights(cs)
>>> cs2=weights_to_creation_sequence(wseq)
>>> cs==cs2
True

>>> wseq=creation_sequence_to_weights(uncompact([3,1,2,3,3,2,3]))
>>> wseq==[s*0.125 for s in [4,4,4,3,5,5,2,2,2,6,6,6,1,1,7,7,7]]
True

>>> wseq=creation_sequence_to_weights([3,1,2,3,3,2,3])
>>> wseq==[s*0.125 for s in [4,4,4,3,5,5,2,2,2,6,6,6,1,1,7,7,7]]
True

>>> wseq=creation_sequence_to_weights(list(enumerate('ddidiiidididi')))
>>> wseq==[s*0.1 for s in [5,5,4,6,3,3,3,7,2,8,1,9,0]]
True

>>> wseq=creation_sequence_to_weights('ddidiiidididi')
>>> wseq==[s*0.1 for s in [5,5,4,6,3,3,3,7,2,8,1,9,0]]
True

>>> wseq=creation_sequence_to_weights('ddidiiidididid')
>>> ws=[s/float(12) for s in [6,6,5,7,4,4,4,8,3,9,2,10,1,11]]
>>> sum([abs(c-d) for c,d in zip(wseq,ws)])<1e-14
True

Test finding routines
---------------------

>>> G=NX.Graph()
>>> G.add_cycle([1,2,3,4,5,6])
>>> G.add_edge(2,4)
>>> G.add_edge(2,5)
>>> G.add_edge(2,7)
>>> G.add_edge(3,6)
>>> G.add_edge(4,6)

Alternating 4 cycle

>>> find_alternating_4_cycle(G)
[1, 2, 3, 6]

Threshold graph

>>> TG=find_threshold_graph(G)
>>> is_threshold_graph(TG)
True
>>> sorted(TG.nodes())
[1, 2, 3, 4, 5, 7]

>>> cs=creation_sequence(TG.degree(with_labels=True),with_labels=True)
>>> find_creation_sequence(G)==cs
True


Fast versions of properties for threshold graphs
------------------------------------------------

>>> cs='ddiiddid'
>>> G=threshold_graph(cs)

>>> density('ddiiddid')==NX.density(G)
True

>>> sorted(degree_sequence(cs))==sorted(G.degree())
True

>>> ts=triangle_sequence(cs)
>>> ts==NX.cluster.triangles(G)
True

>>> sum(ts)/3==triangles(cs)
True

>>> c1=cluster_sequence(cs)
>>> c2=NX.clustering(G)
>>> sum([abs(c-d) for c,d in zip(c1,c2)])<1e-14
True

>>> b1=NX.betweenness_centrality(G).values()
>>> b2=betweenness_sequence(cs)
>>> sum([abs(c-d) for c,d in zip(b1,b2)])<1e-14
True

>>> eigenvalues(cs)
[0, 1, 3, 3, 5, 7, 7, 8]

      Degree Correlation

>>> abs(degree_correlation(cs)+0.593038821954)<1e-12
True

>>> print degree_correlation('diiiddi')
-0.8

>>> degree_correlation('did')==-1.0
True

>>> degree_correlation('ddd')==1.0
True

>>> eigenvalues('dddiii')
[0, 0, 0, 0, 3, 3]

>>> eigenvalues('dddiiid')
[0, 1, 1, 1, 4, 4, 7]

TG creation routines
--------------------

>>> s=left_d_threshold_sequence(5,7)
>>> s=right_d_threshold_sequence(5,7)
>>> s1=swap_d(s,1.0,1.0)

Eigenvectors
------------
Problems testing this if numpy not installed

>>> (tgeval,tgevec)=eigenvectors(cs)
>>> dot=N.dot
>>> [ abs(dot(lv,lv)-1.0)<1e-9 for lv in tgevec ]==[True]*8
True
>>> lapl=NX.laplacian(G)
>>> tgev=[ dot(lv,dot(lapl,lv)) for lv in tgevec ]
>>> sum([abs(c-d) for c,d in zip(tgev,tgeval)])<1e-9
True
>>> tgev.sort()
>>> lev=list(eigenval(lapl))
>>> lev.sort()
>>> sum([abs(c-d) for c,d in zip(tgev,lev)])<1e-9
True