# 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
position = graph.position

[5]:

image = visualize_graph(adjacency, position, scale=0.5)
SVG(image)

[5]:

[6]:

is_acyclic(adjacency)

[6]:

True

[7]:

get_cycles(adjacency)

[7]:

[]

[8]:

# house graph
position = graph.position

[9]:

image = visualize_graph(adjacency, position, scale=0.5, names=np.arange(5))
SVG(image)

[9]:

[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]:


## Directed graphs

[15]:

# cycle
position = graph.position

[16]:

image = visualize_graph(adjacency, position, scale=0.5)
SVG(image)

[16]:

[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]:

[22]:

# painters
names = graph.names
position = graph.position

[23]:

image = visualize_graph(adjacency, position, names=names)
SVG(image)

[23]:

[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]:

[27]:

is_acyclic(dag)

[27]:

True

[28]:

# painters
names = graph.names
position = graph.position

[29]:

image = visualize_graph(adjacency, position, names=names)
SVG(image)

[29]:

[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]:

[33]:

is_acyclic(dag)

[33]:

True