Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2645_ContextAlgorithms/HeuristicLab.Tests/HeuristicLab.IGraph/IGraphWrappersGraphTest.cs @ 18242

Last change on this file since 18242 was 15624, checked in by abeham, 7 years ago

#2645: created branch
File size: 6.3 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  public class IGraphWrappersGraphTest {
31    [TestMethod]
32    [TestCategory("ExtLibs")]
33    [TestCategory("ExtLibs.igraph")]
34    [TestProperty("Time", "short")]
35    public void IGraphWrappersGraphConstructionAndFinalizationTest() {
36      using (var graph = new Graph(5, new[] {
37        Tuple.Create(0, 1),
38        Tuple.Create(0, 2),
39        Tuple.Create(1, 2),
40        Tuple.Create(2, 3),
41        Tuple.Create(2, 4),
42        Tuple.Create(3, 4),
43      })) {
44        Assert.AreEqual(5, graph.Vertices);
45        Assert.IsFalse(graph.IsDirected);
46      }
47
48      using (var graph = new Graph(3, new[] {
49        Tuple.Create(0, 1),
50        Tuple.Create(0, 2),
51        Tuple.Create(1, 2),
52      }, directed: true)) {
53        Assert.AreEqual(3, graph.Vertices);
54        Assert.IsTrue(graph.IsDirected);
55      }
56    }
57
58    [TestMethod]
59    [TestCategory("ExtLibs")]
60    [TestCategory("ExtLibs.igraph")]
61    [TestProperty("Time", "short")]
62    public void IGraphWrappersGraphDensityTest() {
63      using (var graph = new Graph(5, new[] {
64        Tuple.Create(0, 1),
65        Tuple.Create(0, 2),
66        Tuple.Create(1, 2),
67        Tuple.Create(2, 3),
68        Tuple.Create(2, 4),
69        Tuple.Create(3, 4),
70      })) {
71
72        var density = graph.Density();
73        // in un-directed graphs edges count twice
74        Assert.IsTrue(density.IsAlmost(12 / 20.0));
75      }
76
77      using (var graph = new Graph(5, new[] {
78        Tuple.Create(0, 1),
79        Tuple.Create(0, 2),
80        Tuple.Create(1, 2),
81        Tuple.Create(2, 3),
82        Tuple.Create(2, 4),
83        Tuple.Create(3, 4),
84      }, directed: true)) {
85
86        var density = graph.Density();
87        // in directed graphs edges count twice
88        Assert.IsTrue(density.IsAlmost(6 / 20.0));
89      }
90    }
91
92    [TestMethod]
93    [TestCategory("ExtLibs")]
94    [TestCategory("ExtLibs.igraph")]
95    [TestProperty("Time", "short")]
96    public void IGraphWrappersGraphPageRankTest() {
97      using (var graph = new Graph(4, new[] {
98        Tuple.Create(0, 1),
99        Tuple.Create(0, 2),
100        Tuple.Create(1, 2),
101        Tuple.Create(2, 0),
102        Tuple.Create(3, 2),
103      }, directed: true)) {
104        var ranks = graph.PageRank();
105        Assert.AreEqual(4, ranks.Length);
106        Assert.AreEqual(0.372, ranks[0], 0.01);
107        Assert.AreEqual(0.195, ranks[1], 0.01);
108        Assert.AreEqual(0.394, ranks[2], 0.01);
109        Assert.AreEqual(0.037, ranks[3], 0.01);
110      }
111      using (var graph = new Graph(4, new[] {
112        Tuple.Create(0, 1),
113        Tuple.Create(1, 2),
114        Tuple.Create(2, 3),
115        Tuple.Create(3, 0),
116      }, directed: true)) {
117        var ranks = graph.PageRank();
118        Assert.AreEqual(4, ranks.Length);
119        Assert.AreEqual(0.250, ranks[0], 0.01);
120        Assert.AreEqual(0.250, ranks[1], 0.01);
121        Assert.AreEqual(0.250, ranks[2], 0.01);
122        Assert.AreEqual(0.250, ranks[3], 0.01);
123      }
124      using (var graph = new Graph(4, new[] {
125        Tuple.Create(0, 1),
126        Tuple.Create(0, 2),
127        Tuple.Create(0, 3),
128        Tuple.Create(1, 0),
129        Tuple.Create(2, 0),
130        Tuple.Create(3, 0),
131      }, directed: true)) {
132        var ranks = graph.PageRank();
133        Assert.AreEqual(4, ranks.Length);
134        Assert.AreEqual(0.480, ranks[0], 0.01);
135        Assert.AreEqual(0.173, ranks[1], 0.01);
136        Assert.AreEqual(0.173, ranks[2], 0.01);
137        Assert.AreEqual(0.173, ranks[3], 0.01);
138      }
139    }
140
141    [TestMethod]
142    [TestCategory("ExtLibs")]
143    [TestCategory("ExtLibs.igraph")]
144    [TestProperty("Time", "short")]
145    public void IGraphWrappersGraphBreadthFirstWalkTest() {
146      using (var graph = new Graph(4, new[] {
147        Tuple.Create(0, 1),
148        Tuple.Create(0, 2),
149        Tuple.Create(1, 2),
150        Tuple.Create(2, 0),
151        Tuple.Create(3, 2),
152      }, directed: true)) {
153        var visited = new HashSet<int>();
154        BreadthFirstHandler handler = (graph1, currentVertexId, previousVertexId, nextVertexId, rank, distance, tag) => {
155          visited.Add(currentVertexId);
156          return false;
157        };
158        graph.BreadthFirstWalk(handler, 0, DirectedWalkMode.All, true, null);
159        Assert.AreEqual(4, visited.Count);
160        Assert.IsTrue(visited.Contains(0));
161        Assert.IsTrue(visited.Contains(1));
162        Assert.IsTrue(visited.Contains(2));
163        Assert.IsTrue(visited.Contains(3));
164      }
165    }
166
167    [TestMethod]
168    [TestCategory("ExtLibs")]
169    [TestCategory("ExtLibs.igraph")]
170    [TestProperty("Time", "short")]
171    public void IGraphWrappersGraphDepthFirstWalkTest() {
172      using (var graph = new Graph(4, new[] {
173        Tuple.Create(0, 1),
174        Tuple.Create(0, 2),
175        Tuple.Create(1, 2),
176        Tuple.Create(2, 0),
177        Tuple.Create(3, 2),
178      }, directed: true)) {
179        var visited = new HashSet<int>();
180        DepthFirstHandler handler = (graph1, vertexId, distance, tag) => {
181          visited.Add(vertexId);
182          return false;
183        };
184        graph.DepthFirstWalk(handler, handler, 0, DirectedWalkMode.All, true, null);
185        Assert.AreEqual(4, visited.Count);
186        Assert.IsTrue(visited.Contains(0));
187        Assert.IsTrue(visited.Contains(1));
188        Assert.IsTrue(visited.Contains(2));
189        Assert.IsTrue(visited.Contains(3));
190      }
191    }
192  }
193}
Note: See TracBrowser for help on using the repository browser.