Cycles

This notebook illustrates the search for cycles in graphs and how to break these cycles.

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import house, star, cyclic_digraph, painters
from sknetwork.topology import is_acyclic
from sknetwork.topology import get_cycles, break_cycles
from sknetwork.visualization import visualize_graph

Graphs

[4]:
# star
graph = star(5, metadata=True)
adjacency = graph.adjacency
position = graph.position
[5]:
image = visualize_graph(adjacency, position, scale=0.5)
SVG(image)
[5]:
../../_images/tutorials_topology_cycles_7_0.svg
[6]:
is_acyclic(adjacency)
[6]:
True
[7]:
get_cycles(adjacency)
[7]:
[]
[8]:
# house graph
graph = house(metadata=True)
adjacency = graph.adjacency
position = graph.position
[9]:
image = visualize_graph(adjacency, position, scale=0.5, names=np.arange(5))
SVG(image)
[9]:
../../_images/tutorials_topology_cycles_11_0.svg
[10]:
is_acyclic(adjacency)
[10]:
False
[11]:
get_cycles(adjacency)
[11]:
[[0, 4, 3, 2, 1], [1, 4, 3, 2], [0, 4, 1]]
[12]:
adjacency_no_cycle = break_cycles(adjacency, root=0)
[13]:
is_acyclic(adjacency_no_cycle)
[13]:
True
[14]:
image = visualize_graph(adjacency_no_cycle, position, scale=0.5, names=np.arange(5))
SVG(image)
[14]:
../../_images/tutorials_topology_cycles_16_0.svg

Directed graphs

[15]:
# cycle
graph = cyclic_digraph(5, metadata=True)
adjacency = graph.adjacency
position = graph.position
[16]:
image = visualize_graph(adjacency, position, scale=0.5)
SVG(image)
[16]:
../../_images/tutorials_topology_cycles_19_0.svg
[17]:
is_acyclic(adjacency)
[17]:
False
[18]:
get_cycles(adjacency)
[18]:
[[0, 1, 2, 3, 4]]
[19]:
adjacency_no_cycle = break_cycles(adjacency, root=0)
[20]:
is_acyclic(adjacency_no_cycle)
[20]:
True
[21]:
image = visualize_graph(adjacency_no_cycle, position, scale=0.5, names=np.arange(5))
SVG(image)
[21]:
../../_images/tutorials_topology_cycles_24_0.svg
[22]:
# painters
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[23]:
image = visualize_graph(adjacency, position, names=names)
SVG(image)
[23]:
../../_images/tutorials_topology_cycles_26_0.svg
[24]:
is_acyclic(adjacency)
[24]:
False
[25]:
dag = break_cycles(adjacency, root=np.flatnonzero(names=='Henri Matisse'))
[26]:
image = visualize_graph(dag, position, names=names)
SVG(image)
[26]:
../../_images/tutorials_topology_cycles_29_0.svg
[27]:
is_acyclic(dag)

[27]:
True
[28]:
# painters
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[29]:
image = visualize_graph(adjacency, position, names=names)
SVG(image)
[29]:
../../_images/tutorials_topology_cycles_32_0.svg
[30]:
is_acyclic(adjacency)
[30]:
False
[31]:
dag = break_cycles(adjacency, root=np.flatnonzero(names=='Henri Matisse'))
[32]:
image = visualize_graph(dag, position, names=names)
SVG(image)
[32]:
../../_images/tutorials_topology_cycles_35_0.svg
[33]:
is_acyclic(dag)
[33]:
True