-
Notifications
You must be signed in to change notification settings - Fork 1
/
Graph.cs
73 lines (64 loc) · 2.55 KB
/
Graph.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* Copyright (c) 2018-2024 Nuno Fachada and contributors
* Distributed under the MIT License (See accompanying file LICENSE or copy
* at http://opensource.org/licenses/MIT) */
using System;
using System.Collections.Generic;
namespace LibGameAI.PathFinding
{
public class Graph : IGraph
{
// The graph is internally represented using an adjacency list
private IList<IEnumerable<IConnection>> connections;
/// <summary>
/// Create new graph using an adjacency list.
/// </summary>
/// <param name="connections">Adjacency list with which to create
/// graph.</param>
public Graph(IList<IEnumerable<IConnection>> connections)
{
this.connections = connections;
}
/// <summary>
/// Create new graph using an adjacency matrix.
/// </summary>
/// <param name="adjMatrix">Adjacency matrix with which to create
/// graph.</param>
public Graph(float[,] adjMatrix)
{
// Adjacency matrix must be square
if (adjMatrix.GetLength(0) != adjMatrix.GetLength(1))
{
throw new ArgumentException("Adjacency matrix must be square!");
}
// Initialize the internal adjacency list which defines this graph
connections = new IEnumerable<IConnection>[adjMatrix.GetLength(0)];
// Cycle through the adjacency matrix and build the internal
// adjacency list
for (int i = 0; i < adjMatrix.GetLength(0); i++)
{
// Create list for current node
List<IConnection> currList = new List<IConnection>();
// Populate list for current node
for (int j = 0; j < adjMatrix.GetLength(1); j++)
{
// Only add connections if weight/cost is larger than 0
if (adjMatrix[i, j] > 0.0f)
{
currList.Add(new Connection(adjMatrix[i, j], i, j));
}
}
// Keep current node's list in the adjacency list
connections[i] = currList;
}
}
/// <summary>
/// Get all outgoing connections for the given node.
/// </summary>
/// <param name="fromNode">A node in the graph.</param>
/// <returns>All outgoing connections for the given node.</returns>
public IEnumerable<IConnection> GetConnections(int fromNode)
{
return connections[fromNode];
}
}
}