Simple and Hyper Graphs#

Stochastic Matchings allows to build arbitrary models from their graph adjacency or incidence matrix, but also to directly instantiate some families. This tutorial gives a tour of these families and details the graph behavior of a Model instance.

First, we load the package.

[1]:

import stochastic_matching as sm

Simple graph: manual definition and basic usage#

A simple graph can be defined by providing its adjacency or incidence matrix. We give a tour of the possibilities using the diamond graph as running example.

[2]:

diamond_adjacency = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
diamond = sm.Model(adjacency=diamond_adjacency)
diamond.show_graph(vis_options={"height": 200})

If you input an incidence matrix, the graph is treated as a hypergraph.

[3]:

diamond_incidence = [[1, 1, 0, 0, 0], [1, 0, 1, 1, 0], [0, 1, 1, 0, 1], [0, 0, 0, 1, 1]]

diamond = sm.Model(incidence=diamond_incidence)
diamond.show_graph(vis_options={"height": 200})

A Model possesses many attributes.

Number of edges and nodes:

[4]:

diamond.n, diamond.m

[4]:

(4, 5)

Adjacency matrix does not exist for hypergraphs:

[5]:

diamond.adjacency

[6]:

diamond = sm.Model(adjacency=diamond_adjacency)
diamond.adjacency

[6]:

array([[0, 1, 1, 0],
       [1, 0, 1, 1],
       [1, 1, 0, 1],
       [0, 1, 1, 0]])

Incidence (nodes X edges):

[7]:

diamond.incidence

[7]:

array([[1, 1, 0, 0, 0],
       [1, 0, 1, 1, 0],
       [0, 1, 1, 0, 1],
       [0, 0, 0, 1, 1]])

As already seen, you can visualize the graph with the show_graph method.

[8]:

diamond.show_graph()

You can customize display with vis_options (the options will be pass to the vis engine). For example, to display a red graph with no navigation button:

[9]:

diamond.show_graph(
    vis_options={
        "nodes": {"color": "red"},
        "height": 200,
        "interaction": {"navigationButtons": True}
    }
)

Names can be specified.

[10]:

diamond.names = ["Ga", "Bu", "Zo", "Meu"]
diamond.show_graph(vis_options={"height": 200})

Automatic letter labeling can be obtained using alpha as input for names

[11]:

diamond.names = "alpha"
diamond.show_graph(vis_options={"height": 200})

Pre-defined models#

For convenience, many graph families are provided. You can have the list with the get_class method.

[12]:

sm.common.get_classes(sm.Model)

[12]:

{'Path': stochastic_matching.graphs.Path,
 'Star': stochastic_matching.graphs.Star,
 'Cycle': stochastic_matching.graphs.Cycle,
 'Complete': stochastic_matching.graphs.Complete,
 'Codomino': stochastic_matching.graphs.Codomino,
 'Erdös-Rényi': stochastic_matching.graphs.ErdosRenyi,
 'Nazari-Stolyar': stochastic_matching.graphs.NS19,
 'Pyramid': stochastic_matching.graphs.Pyramid,
 'Tadpole': stochastic_matching.graphs.Tadpole,
 'Lollipop': stochastic_matching.graphs.Lollipop,
 'Kayak Paddle': stochastic_matching.graphs.KayakPaddle,
 'Barbell': stochastic_matching.graphs.Barbell,
 'Cycle Chain': stochastic_matching.graphs.CycleChain,
 'Hyper Kayak Paddle': stochastic_matching.graphs.HyperPaddle,
 'Fan': stochastic_matching.graphs.Fan}

Path graphs#

Paths are defined by a parameter \(n\) (the size, e.g. number of nodes) that defaults to 2.

[13]:

sm.Path().show_graph(vis_options={"height": 200})

[14]:

sm.Path(names="alpha", n=5).show_graph(vis_options={"height": 200})

Cycle graphs#

Cycles are defined by a parameter \(n\) that defaults to 3.

[15]:

sm.Cycle().show_graph(vis_options={"height": 200})

[16]:

sm.Cycle(names="alpha", n=5).show_graph(vis_options={"height": 200})

Star graphs#

Stars are defined by a parameter \(n\) (the number of nodes) that defaults to 4.

[17]:

sm.Star().show_graph(vis_options={"height": 200})

[18]:

sm.Star(names="alpha", n=5).show_graph(vis_options={"height": 200})

Complete graphs#

Complete graphs are defined by a parameter \(n\) that defaults to 3.

[19]:

sm.Complete().show_graph(vis_options={"height": 200})

[20]:

sm.Complete(names="alpha", n=5).show_graph(vis_options={"height": 200})

Tadpole graphs#

A tadpole combines a cycle of length \(m\) and a path of length \(n\). Default is the paw graph (\(m=3, n=1\))

[21]:

# Paw graph
sm.Tadpole().show_graph(vis_options={"height": 200})

[22]:

sm.Tadpole(n=4).show_graph(vis_options={"height": 200})

[23]:

# Banner graph
sm.Tadpole(m=4).show_graph(vis_options={"height": 200})

[24]:

# Ursa major
sm.Tadpole(
    n=3, m=4, names=["Dubhe", "Merak", "Phecda", "Megrez", "Alioth", "Mizar", "Alkaid"]
).show_graph(vis_options={"height": 400})

Lollipop graphs#

A lollipop combines a complete graph of size \(m\) and a path of length \(n\). Default is the paw graph (\(m=3, n=1\))

[25]:

# Paw graph
sm.Lollipop().show_graph(vis_options={"height": 200})

[26]:

sm.Lollipop(m=4).show_graph(vis_options={"height": 200})

[27]:

sm.Lollipop(n=3, m=5).show_graph(vis_options={"height": 400})

Kayak paddle graphs#

Combines a cycle of length \(k\), a path of length \(l\), and a cycle of length \(m\). Defaults to \(k=3, l=1, m=k\).

[28]:

sm.KayakPaddle().show_graph(vis_options={"height": 200})

[29]:

sm.KayakPaddle(5, 2).show_graph(vis_options={"height": 300})

[30]:

## Fish graph
sm.KayakPaddle(l=0, m=4).show_graph(vis_options={"height": 300})

Barbell graph#

Combines a complete graph of size \(k\), a path of length \(l\), and a complete graph of size \(m\). Defaults to \(k=3, l=1, m=k\).

[31]:

sm.Barbell().show_graph(vis_options={"height": 200})

[32]:

sm.Barbell(5, 2).show_graph(vis_options={"height": 300})

[33]:

sm.Barbell(l=0, m=4).show_graph(vis_options={"height": 300})

Chained cycle graphs#

Concatenates cycles of size \(n\), \(c\) of them. Each cycle has \(o\) nodes that overlap with the next one. Defaults to \(n=3, c=2, o=2\).

[34]:

# Diamond
sm.CycleChain().show_graph(vis_options={"height": 200})

[35]:

# Triamond
sm.CycleChain(c=3).show_graph(vis_options={"height": 300})

[36]:

# Domino
sm.CycleChain(n=4).show_graph(vis_options={"height": 300})

[37]:

# The triangular snake graph TS_9 (cf https://mathworld.wolfram.com/TriangularSnakeGraph.html)
sm.CycleChain(c=4, o=1).show_graph(vis_options={"height": 400})

[38]:

# 3 separated squares
sm.CycleChain(n=4, c=3, o=0).show_graph(vis_options={"height": 300})

[39]:

# A big chain of triangle
sm.CycleChain(c=30, names="alpha").show_graph()

Erdös-Rényi graph#

Standard random graph with default parameters \(n=10\), \(d=3\), \(seed=None\).

[40]:

sm.ErdosRenyi(seed=42).show_graph(vis_options={"height": 300})

[41]:

sm.ErdosRenyi(n=20, d=2, seed=42).show_graph(vis_options={"height": 400})

Concatenation#

Building more elaborate graphs on top of the provided generators is relatively easy.).

One way to build these graphs is to use concatenation.

Concatenation generalizes the chained cycles above. It uses a list of graphs and the overlapping between graph. Overlapping can be uniform or heterogeneous (you need then to provide a list of overlaps).

[42]:

# House
sm.concatenate([sm.Cycle(), sm.Cycle(4)], 2).show_graph(vis_options={"height": 200})

[43]:

# Barred house
sm.concatenate([sm.Cycle(), sm.Complete(4)], 2).show_graph(vis_options={"height": 200})

[44]:

# House with a triangle on top
sm.concatenate([sm.Cycle(), sm.Cycle(), sm.Cycle(4)], [1, 2]).show_graph(
    vis_options={"height": 200}
)

For some examples proposed in https://hal.archives-ouvertes.fr/hal-03502084, direct shortcut is provided:

the co-domino graph;
the Egyptian pyramid graph (please see the above paper for the origin of the name.

[45]:

# Codomino
sm.Codomino().show_graph(vis_options={"height": 200})

[46]:

# Pyramid
sm.Pyramid().show_graph(vis_options={"height": 200})

Package logo#

The logo of stochastic matching was made with stochastic matching. Here is the code that produced the big version.

[47]:

import numpy as np
from matplotlib import pyplot as plt
from stochastic_matching.graphs import concatenate_adjacency, path_adjacency


def random_color(n=100, i=None, name="rainbow"):
    if i is None:
        i = np.random.randint(n)
    r, g, b, a = plt.get_cmap(name, n)(i)
    return f"rgba({int(256 * r)}, {int(256 * g)}, {int(256 * b)}, 1)"


adja = concatenate_adjacency([path_adjacency(10), path_adjacency(8)], 0)
for i, j in [(1, 11), (16, 7), (5, 15), (12, 3)]:
    adja[i, j] = 1
    adja[j, i] = 1

g = sm.Model(adjacency=adja, names=[c for c in "StochasticMatching"])
nodes_dict1 = [
    {"color": {"background": random_color(10, i)}, "font": {"color": "black"}}
    for i in range(10)
]
nodes_dict2 = [
    {"color": {"background": random_color(8, 8 - i - 1)}, "font": {"color": "white"}}
    for i in range(8)
]
options = {"width": "1000px", "nodes": {"font": {"size": 80}}}
g.show_graph(nodes_info=nodes_dict1 + nodes_dict2, vis_options=options)

An here is the code for the short version. Note the option png=True which creates a mirror png image that can be saved!

[48]:

adja = concatenate_adjacency([path_adjacency(5), path_adjacency(5)], 0)
for i, j in [(1, 6), (2, 6), (3, 7), (3, 8)]:
    adja[i, j] = 1
    adja[j, i] = 1
g = sm.Model(adjacency=adja, names=[c for c in "StochMatch"])
nodes_dict1 = [
    {"color": {"background": random_color(5, i)}, "font": {"color": "black"}}
    for i in range(5)
]
nodes_dict2 = [
    {"color": {"background": random_color(5, 4 - i)}, "font": {"color": "white"}}
    for i in range(5)
]
options = {"width": "1000px", "nodes": {"font": {"size": 80}}}
g.show_graph(nodes_info=nodes_dict1 + nodes_dict2, vis_options=options, png=True)

Hypergraphs#

Hypergraph egdes can link an arbitrary number of nodes (nor necessarily 2). Hypergraphs mainly differ from simple graphs by the absence of adjacency matrix (only the incidence matrix is used) and a different way of been displayed.

Simple graphs as hypergraphs#

All simple graphs are hypergraphs if you remove the adjacency.

[49]:

paw = sm.Tadpole()
paw.adjacency = None
paw.show_graph(vis_options={"height": 200})

Note

Hypergraph convention: edges are represented by small black nodes, and the edges displayed alway link one single node to one edge. Also note that it is possible to make the bipartite structure between nodes and edges more apparent by passing the bipartite flag.

[50]:

paw.show_graph(bipartite=True, vis_options={"height": 200})

Nazari-Stolyar example#

Hypergraph from https://arxiv.org/pdf/1608.01646 (no parameter).

[51]:

sm.NS19().show_graph(vis_options={"height": 300})

Hyper paddle#

A variation of the regular paddle where the two cycles are linked by 3-egdes. Default to \(k=3\), \(m=3\), \(l=1\).

The default version, named Candy graph, is one of the simplest graph for which one can find stabilizable rates that no greedy policy can stabilize.

[52]:

candy = sm.HyperPaddle()
candy.show_graph()

A larger version.

[53]:

poodle = sm.HyperPaddle(k=4, l=3)
poodle.show_graph()

Fans#

Fans are cycles linked by hyperedges. Default to \(cycles=3\), \(cycle_size=3\), \(hyperedges=1\).

Fans are useful to study the equivalent of bipartite graphs (non-trivial left kernel) in the hypergraphs world.

The default fan is called a clover.

[54]:

sm.Fan().show_graph()

Next one is a highly degenerated example (as shown in another notebook)!

[55]:

sm.Fan(cycle_size=4, hyperedges=2).show_graph()