Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5be0a3d

Browse files
authored
Merge pull requestTheAlgorithms#208 from aparibocci/feature/graph_topological_sort
Implementing topological sorting for DAGs
2 parentsaf56ad0 +5f0a19c commit5be0a3d

File tree

2 files changed

+89
-0
lines changed

2 files changed

+89
-0
lines changed
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
require'set'
2+
3+
##
4+
# This class aims to provide topological sorting capabilities for directed acyclic graphs.
5+
#
6+
# Topological sorting runs in O(|V|), where |V| is the number of graph nodes.
7+
8+
classTopologicalSorter
9+
attr_reader:graph
10+
11+
definitialize(graph)
12+
raiseArgumentError,"Topological sort is only applicable to directed graphs!"unlessgraph.directed
13+
@graph=graph
14+
end
15+
16+
deftopological_sort
17+
@sorted_nodes=[]
18+
@seen=Set[]
19+
@visited=Set[]
20+
fornodeingraph.nodes
21+
dfs_visit(node)
22+
end
23+
@sorted_nodes
24+
end
25+
26+
private
27+
defdfs_visit(node)
28+
returnif@visited.include?(node)
29+
raiseArgumentError,"Cycle in graph detected on node#{node}!"if@seen.include?(node)
30+
@seen.add(node)
31+
forneighboringraph.neighbors(node)
32+
dfs_visit(neighbor)
33+
end
34+
@visited.add(node)
35+
@sorted_nodes.unshift(node)
36+
end
37+
end
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
require'minitest/autorun'
2+
require_relative'topological_sort'
3+
require_relative'unweighted_graph'
4+
5+
classTestTopologicalSort <Minitest::Test
6+
deftest_topological_sort_returns_valid_order_for_acyclic_graph
7+
wardrobe_items=[:underwear,:trousers,:belt,:shirt,:tie,:jacket,:socks,:shoes,:watch]
8+
wardrobe_graph=UnweightedGraph.new(nodes:wardrobe_items,directed:true)
9+
wardrobe_graph.add_edge(:underwear,:trousers)
10+
wardrobe_graph.add_edge(:underwear,:shoes)
11+
wardrobe_graph.add_edge(:socks,:shoes)
12+
wardrobe_graph.add_edge(:trousers,:shoes)
13+
wardrobe_graph.add_edge(:trousers,:belt)
14+
wardrobe_graph.add_edge(:shirt,:belt)
15+
wardrobe_graph.add_edge(:belt,:jacket)
16+
wardrobe_graph.add_edge(:shirt,:tie)
17+
wardrobe_graph.add_edge(:tie,:jacket)
18+
19+
sorted_items=TopologicalSorter.new(wardrobe_graph).topological_sort
20+
21+
assertsorted_items.index(:underwear) <sorted_items.index(:trousers)
22+
assertsorted_items.index(:underwear) <sorted_items.index(:shoes)
23+
assertsorted_items.index(:socks) <sorted_items.index(:shoes)
24+
assertsorted_items.index(:trousers) <sorted_items.index(:shoes)
25+
assertsorted_items.index(:trousers) <sorted_items.index(:belt)
26+
assertsorted_items.index(:shirt) <sorted_items.index(:belt)
27+
assertsorted_items.index(:belt) <sorted_items.index(:jacket)
28+
assertsorted_items.index(:shirt) <sorted_items.index(:tie)
29+
assertsorted_items.index(:tie) <sorted_items.index(:jacket)
30+
end
31+
32+
deftest_topological_sort_raises_exception_for_undirected_graph
33+
nodes=[:u,:v]
34+
graph=UnweightedGraph.new(nodes:nodes,directed:false)
35+
graph.add_edge(:u,:v)
36+
37+
assert_raisesArgumentErrordo
38+
TopologicalSorter.new(graph).topological_sort
39+
end
40+
end
41+
42+
deftest_topological_sort_raises_exception_for_cyclic_graph
43+
nodes=[:u,:v]
44+
graph=UnweightedGraph.new(nodes:nodes,directed:true)
45+
graph.add_edge(:u,:v)
46+
graph.add_edge(:v,:u)
47+
48+
assert_raisesArgumentErrordo
49+
TopologicalSorter.new(graph).topological_sort
50+
end
51+
end
52+
end

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp