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]:
[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]:
[10]:
is_acyclic(adjacency)
[10]:
False
[11]:
get_cycles(adjacency)
[11]:
[[np.int64(0), np.int64(4), np.int64(3), np.int64(2), np.int64(1)],
[np.int32(1), np.int32(4), np.int32(3), np.int32(2)],
[np.int64(0), np.int64(4), np.int64(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
graph = cyclic_digraph(5, metadata=True)
adjacency = graph.adjacency
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]:
[[np.int64(0), np.int64(1), np.int64(2), np.int64(3), np.int64(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
graph = painters(metadata=True)
adjacency = graph.adjacency
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
graph = painters(metadata=True)
adjacency = graph.adjacency
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