directed_graph_spec.rb in nanoc-4.7.11

- old
+ new
@@ -63,6 +63,297 @@
       end
 
       it { is_expected.to eq([2, 3, 4, 5]) }
     end
   end
+
+  describe '#all_paths' do
+    subject { graph.all_paths.to_a }
+
+    context 'no cycles' do
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [2],
+          [3],
+        )
+      end
+    end
+
+    context 'one cycle without head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 1],
+          [2],
+          [2, 1],
+          [2, 1, 2],
+          [3],
+        )
+      end
+    end
+
+    context 'one cycle with head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 2)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 2],
+          [2],
+          [2, 3],
+          [2, 3, 2],
+          [3],
+          [3, 2],
+          [3, 2, 3],
+        )
+      end
+    end
+
+    context 'one cycle with tail' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 20)
+        graph.add_edge(20, 21)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 20],
+          [1, 2, 20, 21],
+          [1, 2, 3],
+          [1, 2, 3, 1],
+          [2],
+          [2, 20],
+          [2, 20, 21],
+          [2, 3],
+          [2, 3, 1],
+          [2, 3, 1, 2],
+          [3],
+          [3, 1],
+          [3, 1, 2],
+          [3, 1, 2, 20],
+          [3, 1, 2, 20, 21],
+          [3, 1, 2, 3],
+          [20],
+          [20, 21],
+          [21],
+        )
+      end
+    end
+
+    context 'large cycle' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 4)
+        graph.add_edge(4, 5)
+        graph.add_edge(5, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 4],
+          [1, 2, 3, 4, 5],
+          [1, 2, 3, 4, 5, 1],
+          [2],
+          [2, 3],
+          [2, 3, 4],
+          [2, 3, 4, 5],
+          [2, 3, 4, 5, 1],
+          [2, 3, 4, 5, 1, 2],
+          [3],
+          [3, 4],
+          [3, 4, 5],
+          [3, 4, 5, 1],
+          [3, 4, 5, 1, 2],
+          [3, 4, 5, 1, 2, 3],
+          [4],
+          [4, 5],
+          [4, 5, 1],
+          [4, 5, 1, 2],
+          [4, 5, 1, 2, 3],
+          [4, 5, 1, 2, 3, 4],
+          [5],
+          [5, 1],
+          [5, 1, 2],
+          [5, 1, 2, 3],
+          [5, 1, 2, 3, 4],
+          [5, 1, 2, 3, 4, 5],
+        )
+      end
+    end
+
+    context 'large cycle with head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 4)
+        graph.add_edge(4, 5)
+        graph.add_edge(5, 2)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 4],
+          [1, 2, 3, 4, 5],
+          [1, 2, 3, 4, 5, 2],
+          [2],
+          [2, 3],
+          [2, 3, 4],
+          [2, 3, 4, 5],
+          [2, 3, 4, 5, 2],
+          [3],
+          [3, 4],
+          [3, 4, 5],
+          [3, 4, 5, 2],
+          [3, 4, 5, 2, 3],
+          [4],
+          [4, 5],
+          [4, 5, 2],
+          [4, 5, 2, 3],
+          [4, 5, 2, 3, 4],
+          [5],
+          [5, 2],
+          [5, 2, 3],
+          [5, 2, 3, 4],
+          [5, 2, 3, 4, 5],
+        )
+      end
+    end
+  end
+
+  describe '#dfs_from' do
+    subject do
+      [].tap do |ps|
+        graph.dfs_from(1) do |p|
+          ps << p
+        end
+      end
+    end
+
+    context 'no cycles' do
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+        )
+      end
+    end
+
+    context 'one cycle without head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 1],
+        )
+      end
+    end
+
+    context 'one cycle with head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 2)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 2],
+        )
+      end
+    end
+
+    context 'one cycle with tail' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 20)
+        graph.add_edge(20, 21)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 20],
+          [1, 2, 20, 21],
+          [1, 2, 3],
+          [1, 2, 3, 1],
+        )
+      end
+    end
+
+    context 'large cycle' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 4)
+        graph.add_edge(4, 5)
+        graph.add_edge(5, 1)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 4],
+          [1, 2, 3, 4, 5],
+          [1, 2, 3, 4, 5, 1],
+        )
+      end
+    end
+
+    context 'large cycle with head' do
+      before do
+        graph.add_edge(1, 2)
+        graph.add_edge(2, 3)
+        graph.add_edge(3, 4)
+        graph.add_edge(4, 5)
+        graph.add_edge(5, 2)
+      end
+
+      example do
+        expect(subject).to contain_exactly(
+          [1],
+          [1, 2],
+          [1, 2, 3],
+          [1, 2, 3, 4],
+          [1, 2, 3, 4, 5],
+          [1, 2, 3, 4, 5, 2],
+        )
+      end
+    end
+  end
 end