Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Tests/HeuristicLab.IGraph/IGraphWrappersGraphTest.cs @ 15805

Last change on this file since 15805 was 15584, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers on stable
File size: 6.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.IGraph.Wrappers;
26using Microsoft.VisualStudio.TestTools.UnitTesting;
27
28namespace HeuristicLab.Tests {
29  [TestClass]
30  [DeploymentItem("igraph-0.8.0-pre-x86.dll")]
31  [DeploymentItem("igraph-0.8.0-pre-x64.dll")]
32  public class IGraphWrappersGraphTest {
33    [TestMethod]
34    [TestCategory("ExtLibs")]
35    [TestCategory("ExtLibs.igraph")]
36    [TestProperty("Time", "short")]
37    public void IGraphWrappersGraphConstructionAndFinalizationTest() {
38      using (var graph = new Graph(5, new[] {
39        Tuple.Create(0, 1),
40        Tuple.Create(0, 2),
41        Tuple.Create(1, 2),
42        Tuple.Create(2, 3),
43        Tuple.Create(2, 4),
44        Tuple.Create(3, 4),
45      })) {
46        Assert.AreEqual(5, graph.Vertices);
47        Assert.IsFalse(graph.IsDirected);
48      }
49
50      using (var graph = new Graph(3, new[] {
51        Tuple.Create(0, 1),
52        Tuple.Create(0, 2),
53        Tuple.Create(1, 2),
54      }, directed: true)) {
55        Assert.AreEqual(3, graph.Vertices);
56        Assert.IsTrue(graph.IsDirected);
57      }
58    }
59
60    [TestMethod]
61    [TestCategory("ExtLibs")]
62    [TestCategory("ExtLibs.igraph")]
63    [TestProperty("Time", "short")]
64    public void IGraphWrappersGraphDensityTest() {
65      using (var graph = new Graph(5, new[] {
66        Tuple.Create(0, 1),
67        Tuple.Create(0, 2),
68        Tuple.Create(1, 2),
69        Tuple.Create(2, 3),
70        Tuple.Create(2, 4),
71        Tuple.Create(3, 4),
72      })) {
73
74        var density = graph.Density();
75        // in un-directed graphs edges count twice
76        Assert.IsTrue(density.IsAlmost(12 / 20.0));
77      }
78
79      using (var graph = new Graph(5, new[] {
80        Tuple.Create(0, 1),
81        Tuple.Create(0, 2),
82        Tuple.Create(1, 2),
83        Tuple.Create(2, 3),
84        Tuple.Create(2, 4),
85        Tuple.Create(3, 4),
86      }, directed: true)) {
87
88        var density = graph.Density();
89        // in directed graphs edges count twice
90        Assert.IsTrue(density.IsAlmost(6 / 20.0));
91      }
92    }
93
94    [TestMethod]
95    [TestCategory("ExtLibs")]
96    [TestCategory("ExtLibs.igraph")]
97    [TestProperty("Time", "short")]
98    public void IGraphWrappersGraphPageRankTest() {
99      using (var graph = new Graph(4, new[] {
100        Tuple.Create(0, 1),
101        Tuple.Create(0, 2),
102        Tuple.Create(1, 2),
103        Tuple.Create(2, 0),
104        Tuple.Create(3, 2),
105      }, directed: true)) {
106        var ranks = graph.PageRank();
107        Assert.AreEqual(4, ranks.Length);
108        Assert.AreEqual(0.372, ranks[0], 0.01);
109        Assert.AreEqual(0.195, ranks[1], 0.01);
110        Assert.AreEqual(0.394, ranks[2], 0.01);
111        Assert.AreEqual(0.037, ranks[3], 0.01);
112      }
113      using (var graph = new Graph(4, new[] {
114        Tuple.Create(0, 1),
115        Tuple.Create(1, 2),
116        Tuple.Create(2, 3),
117        Tuple.Create(3, 0),
118      }, directed: true)) {
119        var ranks = graph.PageRank();
120        Assert.AreEqual(4, ranks.Length);
121        Assert.AreEqual(0.250, ranks[0], 0.01);
122        Assert.AreEqual(0.250, ranks[1], 0.01);
123        Assert.AreEqual(0.250, ranks[2], 0.01);
124        Assert.AreEqual(0.250, ranks[3], 0.01);
125      }
126      using (var graph = new Graph(4, new[] {
127        Tuple.Create(0, 1),
128        Tuple.Create(0, 2),
129        Tuple.Create(0, 3),
130        Tuple.Create(1, 0),
131        Tuple.Create(2, 0),
132        Tuple.Create(3, 0),
133      }, directed: true)) {
134        var ranks = graph.PageRank();
135        Assert.AreEqual(4, ranks.Length);
136        Assert.AreEqual(0.480, ranks[0], 0.01);
137        Assert.AreEqual(0.173, ranks[1], 0.01);
138        Assert.AreEqual(0.173, ranks[2], 0.01);
139        Assert.AreEqual(0.173, ranks[3], 0.01);
140      }
141    }
142
143    [TestMethod]
144    [TestCategory("ExtLibs")]
145    [TestCategory("ExtLibs.igraph")]
146    [TestProperty("Time", "short")]
147    public void IGraphWrappersGraphBreadthFirstWalkTest() {
148      using (var graph = new Graph(4, new[] {
149        Tuple.Create(0, 1),
150        Tuple.Create(0, 2),
151        Tuple.Create(1, 2),
152        Tuple.Create(2, 0),
153        Tuple.Create(3, 2),
154      }, directed: true)) {
155        var visited = new HashSet<int>();
156        BreadthFirstHandler handler = (graph1, currentVertexId, previousVertexId, nextVertexId, rank, distance, tag) => {
157          visited.Add(currentVertexId);
158          return false;
159        };
160        graph.BreadthFirstWalk(handler, 0, DirectedWalkMode.All, true, null);
161        Assert.AreEqual(4, visited.Count);
162        Assert.IsTrue(visited.Contains(0));
163        Assert.IsTrue(visited.Contains(1));
164        Assert.IsTrue(visited.Contains(2));
165        Assert.IsTrue(visited.Contains(3));
166      }
167    }
168
169    [TestMethod]
170    [TestCategory("ExtLibs")]
171    [TestCategory("ExtLibs.igraph")]
172    [TestProperty("Time", "short")]
173    public void IGraphWrappersGraphDepthFirstWalkTest() {
174      using (var graph = new Graph(4, new[] {
175        Tuple.Create(0, 1),
176        Tuple.Create(0, 2),
177        Tuple.Create(1, 2),
178        Tuple.Create(2, 0),
179        Tuple.Create(3, 2),
180      }, directed: true)) {
181        var visited = new HashSet<int>();
182        DepthFirstHandler handler = (graph1, vertexId, distance, tag) => {
183          visited.Add(vertexId);
184          return false;
185        };
186        graph.DepthFirstWalk(handler, handler, 0, DirectedWalkMode.All, true, null);
187        Assert.AreEqual(4, visited.Count);
188        Assert.IsTrue(visited.Contains(0));
189        Assert.IsTrue(visited.Contains(1));
190        Assert.IsTrue(visited.Contains(2));
191        Assert.IsTrue(visited.Contains(3));
192      }
193    }
194  }
195}
Note: See TracBrowser for help on using the repository browser.