First Steps#

Categorizing graphs by kernel#

A matching model is primarly defined by its compatibility graph \(G\).

Stochastic Matching can categorize the type of graph by looking at the kernels of its incidence matrix. One can check the four categories from the paper.

Note

A model graph can be built using the adjacency or incidence matrix, for graphs and hypergraphs respectively.

Stochastic Matching also provide a graph library.

Bijective case#

Tip

The method show_graph represents the nodes with their label, which default to their indices (integers).

[1]:

import stochastic_matching as sm
pan = sm.Tadpole()
pan.show_graph()
Refresh

Tip

The display of the graphs is managed by VisJS Network. Sometimes, the result is not convincing (graph not centered, skewed, …). Refreshing the graph usually fixes the issue.

[2]:

pan.kernel

[2]:

Kernels of a graph with 4 nodes and 4 edges.
Node dimension is 0.
Edge dimension is 0
Type: Bijective
Node kernel:
[]
Edge kernel:
[]

Surjective-only case#

[3]:

diamond = sm.CycleChain()
diamond.show_graph()
Refresh 
[4]:

diamond.kernel

[4]:

Kernels of a graph with 4 nodes and 5 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[ 1 -1  0 -1  1]]

Injective-only case#

Tip

If you have custom labels, the indices can be accessed by hovering over nodes.

[5]:

star = sm.Star(names=["R", "L1", "L2", "L3"])
star.show_graph()
Refresh 
[6]:

star.kernel

[6]:

Kernels of a graph with 4 nodes and 3 edges.
Node dimension is 1.
Edge dimension is 0
Type: Injective-only
Node kernel:
[[-1]
 [ 1]
 [ 1]
 [ 1]]
Edge kernel:
[]

Nonjective case (not surjective, not injective)#

[7]:

cycle = sm.Cycle(n=4)
cycle.show_graph()
Refresh 
[8]:

cycle.kernel

[8]:

Kernels of a graph with 4 nodes and 4 edges.
Node dimension is 1.
Edge dimension is 1
Type: Nonjective
Node kernel:
[[ 1]
 [-1]
 [ 1]
 [-1]]
Edge kernel:
[[ 1 -1 -1  1]]

Rate solutions#

Note

Achievable matching rates \(\mu\) depends on the arrival rates \(\lambda\).

While the paper sometimes gives the matching rates \(\mu\) as a generic function of the arrival rates \(\lambda\), Stochastic Matching requires a numeric values of \(\lambda\).

Arrival rates can be defined when the model is instanciated, or afterwards.

Bijective case#

Note

When a flow is specified, show_kernel displays on edges the possible matching rates.

The nodes show their arrival rates.

[9]:

triangle = sm.Cycle(n=3)
triangle.rates = [3, 4, 5]
triangle.show_kernel(disp_flow=True)
Refresh 
[10]:

pan.rates = [4, 5, 5, 2]
pan.show_kernel(disp_flow=True)
Refresh 
[11]:

pentagon = sm.Cycle(n=5, rates=[2, 3, 4, 4, 3])
pentagon.show_kernel(disp_flow=True)
Refresh

Note

A puppet graph is just one frying pan and two stars glued together!

[12]:

puppet = sm.concatenate([sm.Tadpole(), sm.Star(), sm.Star(n=3)],
                        rates=[3, 4, 6, 5, 1, 2, 4, 2, 1])
puppet.show_kernel(disp_flow=True)
Refresh

Surjective-only case#

[13]:

diamond.rates=[7, 9, 7, 5]
diamond.show_kernel(disp_flow=True)
Refresh 
[14]:

kayak = sm.KayakPaddle(rates=[3, 4, 5, 3, 4, 5])
kayak.show_kernel(flow=kayak.optimize_edge(3, -1))
Refresh

Bipartite case#

[15]:

cycle.rates=[2, 2, 1, 1]
cycle.show_kernel(flow=cycle.optimize_edge(1))
Refresh