Graphs#

This module defines models for different graphs.

class stochastic_matching.graphs.Barbell(k=3, l=1, m=None, *args, **kwargs)[source]#
Parameters:

  • k (int) – Size of the first complete graph.

  • m (int, optional) – Size of the second complete graph. Default to the size of the first complete graph.

  • l (int) – Length of the path that joins the two complete graphs.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

Traditional barbel graph with complete graphs of same size and unit bridge.

>>> barbel_5 = Barbell(5)
>>> barbel_5.adjacency 
array([[0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
       [1, 0, 1, 1, 1, 0, 0, 0, 0, 0],
       [1, 1, 0, 1, 1, 0, 0, 0, 0, 0],
       [1, 1, 1, 0, 1, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 1, 1, 0, 1, 1],
       [0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
       [0, 0, 0, 0, 0, 1, 1, 1, 1, 0]])

A bow-tie (two triangles with one node in common).

>>> Barbell(l=0).adjacency 
array([[0, 1, 1, 0, 0],
       [1, 0, 1, 0, 0],
       [1, 1, 0, 1, 1],
       [0, 0, 1, 0, 1],
       [0, 0, 1, 1, 0]])

Something more elaborated.

>>> Barbell(k=3, m=5, l=4).adjacency 
array([[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0]])
class stochastic_matching.graphs.Codomino(*args, **kwargs)[source]#
Parameters:

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

>>> codomino = Codomino()
>>> codomino.adjacency
array([[0, 1, 1, 0, 0, 0],
       [1, 0, 1, 0, 1, 0],
       [1, 1, 0, 1, 0, 0],
       [0, 0, 1, 0, 1, 1],
       [0, 1, 0, 1, 0, 1],
       [0, 0, 0, 1, 1, 0]])
class stochastic_matching.graphs.Complete(n=3, *args, **kwargs)[source]#
Parameters:

  • n (int) – Length of the cycle.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A triangle:

>>> triangle = Complete()
>>> triangle.adjacency 
array([[0, 1, 1],
       [1, 0, 1],
       [1, 1, 0]])

\(K_5\):

>>> k5 = Complete(n=5)
>>> k5.adjacency 
array([[0, 1, 1, 1, 1],
       [1, 0, 1, 1, 1],
       [1, 1, 0, 1, 1],
       [1, 1, 1, 0, 1],
       [1, 1, 1, 1, 0]])

\(K_4\):

>>> k4 = Complete(4)
>>> k4.adjacency 
array([[0, 1, 1, 1],
       [1, 0, 1, 1],
       [1, 1, 0, 1],
       [1, 1, 1, 0]])
class stochastic_matching.graphs.Cycle(n=3, *args, **kwargs)[source]#
Parameters:

  • n (int) – Number of nodes.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A triangle:

>>> triangle = Cycle()
>>> triangle.adjacency 
array([[0, 1, 1],
       [1, 0, 1],
       [1, 1, 0]])

A pentacle:

>>> pentacle = Cycle(n=5)
>>> pentacle.adjacency 
array([[0, 1, 0, 0, 1],
       [1, 0, 1, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 1, 0, 1],
       [1, 0, 0, 1, 0]])

A square:

>>> square = Cycle(4)
>>> square.adjacency 
array([[0, 1, 0, 1],
       [1, 0, 1, 0],
       [0, 1, 0, 1],
       [1, 0, 1, 0]])
class stochastic_matching.graphs.CycleChain(n=3, c=2, o=2, *args, **kwargs)[source]#
Parameters:

  • n (int) – Size of the cycles.

  • c (int) – Number of copies.

  • o (int) – Overlap between cycles.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

The diamond graph (two triangles).

>>> diamond = CycleChain()
>>> diamond.adjacency 
array([[0, 1, 1, 0],
       [1, 0, 1, 1],
       [1, 1, 0, 1],
       [0, 1, 1, 0]])

The triamond graph.

>>> CycleChain(n=3, c=3).adjacency 
array([[0, 1, 1, 0, 0],
       [1, 0, 1, 1, 0],
       [1, 1, 0, 1, 1],
       [0, 1, 1, 0, 1],
       [0, 0, 1, 1, 0]])

The triangular snake graph \(TS_9\) (cf https://mathworld.wolfram.com/TriangularSnakeGraph.html)

>>> CycleChain(n=3, c=4, o=1).adjacency 
array([[0, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 0, 1, 1, 0, 0, 0, 0],
       [0, 0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 1, 1, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 1, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 0]])

The domino graph, or 3-ladder graph (cf https://mathworld.wolfram.com/LadderGraph.html)

>>> CycleChain(n=4, c=2).adjacency 
array([[0, 1, 0, 1, 0, 0],
       [1, 0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0, 1],
       [1, 0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 1, 0, 1, 0]])
class stochastic_matching.graphs.ErdosRenyi(n=10, d=3, seed=None, *args, **kwargs)[source]#
Parameters:

  • n (int) – Number of nodes.

  • d (int or float) – Target degree of Erdos Renyi graph.

  • seed (int, optional) – Random number generator seed.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

>>> erdos_renyi = ErdosRenyi(n=10, d=3, seed=42)
>>> erdos_renyi.m
20
>>> erdos_renyi.adjacency.astype(int) 
array([[0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 1, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
       [0, 1, 0, 0, 0, 0, 1, 1, 0, 0],
       [1, 1, 0, 0, 0, 0, 1, 0, 0, 1],
       [1, 1, 0, 0, 0, 0, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 0, 0, 1, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
       [0, 1, 1, 0, 1, 1, 0, 1, 0, 0]])
class stochastic_matching.graphs.Fan(cycles=3, cycle_size=3, hyperedges=1, *args, **kwargs)[source]#
Parameters:

  • cycles (int) – Number of cycles

  • cycle_size (int) – Size of cycles

  • hyperedges (int) – Number of hyperedges that connect the cycles.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A basic 3-leaves clover:

>>> clover = Fan()
>>> clover.incidence  
array([[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 0, 0, 0, 0, 1],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0]])

Increase the hyperedge connectivity:

>>> connected = Fan(hyperedges=2)
>>> connected.incidence  
array([[1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
       [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
       [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]])

With only two cycles, we have a simple graph.

>>> db = Fan(cycles=2, cycle_size=4)
>>> db.incidence 
array([[1, 1, 0, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0, 0, 0, 0],
       [0, 1, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 1, 0, 0, 1],
       [0, 0, 0, 0, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0, 1, 0, 1, 0]])
>>> from stochastic_matching.model import incidence_to_adjacency
>>> incidence_to_adjacency(db.incidence) 
array([[0, 1, 0, 1, 1, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0],
       [0, 1, 0, 1, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 0, 1, 0]])
class stochastic_matching.graphs.HyperPaddle(k=3, m=3, l=1, *args, **kwargs)[source]#
Parameters:

  • k (int) – Size of the first cycle.

  • m (int) – Size of the second cycle.

  • l (int) – Length of the path of 3-edges that joins the two cycles.

  • *args – Positional parameters for the model.

  • **kwargs (dict, optional) – Keyword parameters for the model.

Examples

The candy, a basic but very useful hypergraph.

>>> candy = HyperPaddle()
>>> candy.incidence
array([[1, 1, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 1, 1, 0, 1],
       [0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 1, 1, 0]])

A more elaborate hypergraph

>>> HyperPaddle(k=5, m=4, l=3).incidence
array([[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]])

Warning: without any hyperedge, we have two disconnected cycles.

>>> HyperPaddle(l=0).incidence
array([[1, 1, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0],
       [0, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 1, 1]])
class stochastic_matching.graphs.KayakPaddle(k=3, l=1, m=None, *args, **kwargs)[source]#
Parameters:

  • k (int) – Size of the first cycle.

  • l (int) – Length of the path that joins the two cycles.

  • m (int, optional) – Size of the second cycle. Default to the size of the first cycle.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A square and a triangle joined by a path of length 3.

>>> kayak = KayakPaddle(k=4, m=3, l=3)
>>> kayak.adjacency 
array([[0, 1, 0, 1, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 1, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 0]])

A bow-tie (two triangles with one node in common).

>>> KayakPaddle(l=0).adjacency 
array([[0, 1, 1, 0, 0],
       [1, 0, 1, 0, 0],
       [1, 1, 0, 1, 1],
       [0, 0, 1, 0, 1],
       [0, 0, 1, 1, 0]])
class stochastic_matching.graphs.Lollipop(m=3, n=1, *args, **kwargs)[source]#
Parameters:

  • m (int) – Length of the complete graph.

  • n (int) – Length of the tail.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A triangle with a one-edge tail (paw graph):

>>> l_3_1 = Lollipop()
>>> l_3_1.adjacency 
array([[0, 1, 1, 0],
       [1, 0, 1, 0],
       [1, 1, 0, 1],
       [0, 0, 1, 0]])

A larger lollipop:

>>> l_5_3 = Lollipop(m=5, n=3)
>>> l_5_3.adjacency 
array([[0, 1, 1, 1, 1, 0, 0, 0],
       [1, 0, 1, 1, 1, 0, 0, 0],
       [1, 1, 0, 1, 1, 0, 0, 0],
       [1, 1, 1, 0, 1, 0, 0, 0],
       [1, 1, 1, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 0]])
class stochastic_matching.graphs.NS19(*args, **kwargs)[source]#
Parameters:

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

>>> ns = NS19()
>>> ns.incidence
array([[1, 0, 0, 0, 1, 0, 0],
       [0, 1, 0, 0, 1, 1, 1],
       [0, 0, 1, 0, 0, 1, 1],
       [0, 0, 0, 1, 0, 0, 1]])
class stochastic_matching.graphs.Path(n=2, *args, **kwargs)[source]#
Parameters:

  • n (int) – Number of nodes.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

Default is a two nodes line:

>>> p2 = Path()
>>> p2.adjacency 
array([[0, 1],
       [1, 0]])

Class name:

>>> p2.name
'Path'

A five nodes line with alphabetical names:

>>> p5 = Path(5, names="alpha")
>>> p5.adjacency 
array([[0, 1, 0, 0, 0],
       [1, 0, 1, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 1, 0, 1],
       [0, 0, 0, 1, 0]])

>>> [p5.names[i] for i in range(p5.n)]
['A', 'B', 'C', 'D', 'E']
class stochastic_matching.graphs.Pyramid(*args, **kwargs)[source]#
Parameters:

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

>>> pyramid = Pyramid()
>>> pyramid.adjacency
array([[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 1, 0, 0, 0, 0],
       [1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 1, 0],
       [0, 1, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
       [0, 0, 0, 0, 1, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 0]])
class stochastic_matching.graphs.Star(n=4, *args, **kwargs)[source]#
Parameters:

  • n (int) – Number of nodes.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

Default is a 4 nodes star (one center and three branches):

>>> s4 = Star()
>>> s4.adjacency 
array([[0, 1, 1, 1],
       [1, 0, 0, 0],
       [1, 0, 0, 0],
       [1, 0, 0, 0]])

A five nodes star:

>>> s5 = Star(5)
>>> s5.adjacency 
array([[0, 1, 1, 1, 1],
       [1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [1, 0, 0, 0, 0]])
class stochastic_matching.graphs.Tadpole(m=3, n=1, *args, **kwargs)[source]#
Parameters:

  • m (int) – Length of the cycle.

  • n (int) – Length of the tail.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Examples

A triangle with a one-edge tail (paw graph):

>>> paw = Tadpole()
>>> paw.adjacency 
array([[0, 1, 1, 0],
       [1, 0, 1, 0],
       [1, 1, 0, 1],
       [0, 0, 1, 0]])

A pentacle:

>>> c5 = Tadpole(m=5, n=0)
>>> c5.adjacency 
array([[0, 1, 0, 0, 1],
       [1, 0, 1, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 1, 0, 1],
       [1, 0, 0, 1, 0]])

A larger tadpole:

>>> long_pan = Tadpole(m=4, n=3)
>>> long_pan.adjacency 
array([[0, 1, 0, 1, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0],
       [0, 1, 0, 1, 0, 0, 0],
       [1, 0, 1, 0, 1, 0, 0],
       [0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 0, 0, 1, 0]])
stochastic_matching.graphs.complete_adjacency(n=3)[source]#
Parameters:

n (int) – Number of nodes.

Returns:

Adjacency matrix of a complete graph \(K_n\) (cf https://mathworld.wolfram.com/CompleteGraph.html).

Return type:

ndarray

stochastic_matching.graphs.concatenate(model_list, overlap=None, *args, **kwargs)[source]#
Parameters:

  • model_list (list of Model) – The graphs that one want to merge. They must all be simple (and in particular have an adjacency matrix).

  • overlap (int or list of int, optional) – Number of nodes that are common to two consecutive graphs. Default to 1.

  • *args – Positional parameters for the model.

  • **kwargs – Keyword parameters for the model.

Returns:

Model of the concatenated graph.

Return type:

Model

Examples

A codomino graph:

>>> codomino = concatenate([Cycle(), Cycle(4), Cycle()], 2)
>>> codomino.adjacency 
array([[0, 1, 1, 0, 0, 0],
       [1, 0, 1, 0, 1, 0],
       [1, 1, 0, 1, 0, 0],
       [0, 0, 1, 0, 1, 1],
       [0, 1, 0, 1, 0, 1],
       [0, 0, 0, 1, 1, 0]])
stochastic_matching.graphs.concatenate_adjacency(adja_list, overlap=None)[source]#
Parameters:

  • adja_list (list of ndarray) – The adjacency matrices that one wants to merge.

  • overlap (int or list of int, optional) – Number of nodes that are common to two consecutive graphs. Default to 1.

Returns:

Concatenated adjacency.

Return type:

ndarray

Examples

A codomino adjacency:

>>> concatenate_adjacency([cycle_adjacency(), cycle_adjacency(4), cycle_adjacency()], 2) 
array([[0, 1, 1, 0, 0, 0],
       [1, 0, 1, 0, 1, 0],
       [1, 1, 0, 1, 0, 0],
       [0, 0, 1, 0, 1, 1],
       [0, 1, 0, 1, 0, 1],
       [0, 0, 0, 1, 1, 0]])
stochastic_matching.graphs.cycle_adjacency(n=3)[source]#
Parameters:

n (int) – Length of the cycle.

Returns:

Adjacency matrix of a cycle graph \(C_n\) (cf https://mathworld.wolfram.com/CycleGraph.html).

Return type:

ndarray

stochastic_matching.graphs.path_adjacency(n=2)[source]#
Parameters:

n (int) – Number of nodes.

Returns:

Adjacency matrix of a path graph \(P_n\) (cf https://mathworld.wolfram.com/PathGraph.html).

Return type:

ndarray

stochastic_matching.graphs.star_adjacency(n=4)[source]#
Parameters:

n (int) – Number of nodes.

Returns:

Adjacency matrix of a star graph \(S_n\) (https://mathworld.wolfram.com/StarGraph.html).

Return type:

ndarray