GraphGen module¶

This algorithm takes a list of degree sequence and determines if it is graphic. If it is graphic, we will generate a graph with that degree sequence.

Starting at the vertex with highest degree, connect it to that many vertices of the next highest degree. Then decrease the remaining degree of those vertices by moving them from one list to the next lowest list. If there are no vertices which can still accept the edge, then we know that the sequence is not graphic.

Algorithm 1.2.1 on page 12

GraphGen.display_graphic_seq(deg_seq)¶

Take the degree sequence, tests if it is graphic and then displays the result.

Parameters

deg_seqList of int

The degree sequence to be tested.

GraphGen.graphic(deg_seq)¶

Tests the seq to see if it is graphic.

Parameters

deg_seqList of int

The sequence of degree for a proposed graph, in any order.

Returns

nx.Graph

A graph with a degree sequence deg_seq or None if the sequence is not graphic.

GraphGen.print_is_graphic(deg_seq)¶

Takes the degree sequence, tests if it is graphic and then prints the result.

Parameters

deg_seqList of int

The degree sequence to be tested, in any order.

Examples

>>> print_is_graphic([4, 4, 4, 4, 4])
The degree sequence is graphic!

This is the degree sequence for the complete graph on 5 vertices.

>>> print_is_graphic([7, 6, 6, 6, 5, 5, 2, 1])
This sequence is not graphic!

This sequence is not graphic becuase there are too many vertices of degree 6.