循环

此笔记本演示了如何在图中搜索循环以及如何打破这些循环。

[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

图

[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

有向图

[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