在大學習作中需要制作一個 Adjacency Matrix Network 和 List of Link Network 的 Class
大致功能:
- 查詢有多少 Path 連進選取的 Node
- 查詢有多少 Path 由選取的 Node 出發
- 查詢一個 Node 能否到達另一個 Node
- Path 的總和
- 2 種 Network 互相轉換
做此習作感受到了 Microsoft .NET 內的 LINQ 的強大
只需短短一行的程式碼便可以做出了複雜的查詢
實在是非常方便
原始碼如下:
Network Class
using System;Adjacency Matrix Network Class
using System.Collections.Generic;
using System.Text;
namespace NetworkLibrary
{
public abstract class Network
{
protected int _Size;
//Size is read only
public int Size
{
get { return _Size; }
}
public abstract int NumberOfLinks();
public abstract int OutDegree(int nodeNumber);
public abstract int InDegree(int nodeNumber);
public abstract List<int> ReachableFrom(int nodeNumber);
}
}
using System;List of Link Network Class
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NetworkLibrary
{
public class AM_Network : Network
{
private int[][] _NodeMatrix;
public int[][] NodeMatrix
{
get { return _NodeMatrix; }
}
public AM_Network(int numberOfNode, int[,] nodeMap)
{
/**
* Error checking
* No node exception
* Null argument exception
* Martrix not correct exception
*/
if (numberOfNode < 1)
throw new NumberOfNodeLessThenOneException("Number Of Node Less Then One");
else if (nodeMap == null)
throw new ArgumentNullException("Node Map is null");
else if (numberOfNode * numberOfNode != nodeMap.Length)
throw new NumberOfNodeNotEqualMatrixHeightException("Number of Node or Matrix Height Not Correct");
else if (!nodeMap.IsFixedSize)
throw new MatrixNotCorrectException("Matrix Width Not Correct");
//Store to local variable
base._Size = numberOfNode;
//Convert 2D array to jagged array
_NodeMatrix = new int[numberOfNode][];
for (int i = 0; i < numberOfNode; i++)
{
_NodeMatrix[i] = new int[numberOfNode];
for (int ii = 0; ii < numberOfNode; ii++)
_NodeMatrix[i][ii] = nodeMap[i, ii];
}
}
public LL_Network To_LL()
{
/**
* Create a list store a Link information
* Search matrix information
* if matrix value greater then zero
* should be create a array to store node data
*/
List<int[]> linkList = new List<int[]>();
for (int i = 0; i < _NodeMatrix.Length; i++)
{
for (int ii = 0; ii < _NodeMatrix[i].Length; ii++)
{
if (_NodeMatrix[i][ii] > 0)
linkList.Add(new int[] { i, ii, _NodeMatrix[i][ii] });
}
}
return new LL_Network(base._Size, linkList.ToArray());
}
public override string ToString()
{
/**
* retrun network type
* network size and total link
*/
string info = "Network Type: Adjacency Matrix\n";
info += "Network Size: " + base._Size + "\n";
info += "Number Of Link: " + NumberOfLinks() + "\n";
return info;
}
public override int NumberOfLinks()
{
//Return network total link
return _NodeMatrix.Sum(row => row.Count(column => column > 0));
}
public override int OutDegree(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
* return number of link in this node point to other node
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (nodeNumber > base._Size - 1)
throw new NonExistentNodeException("Node not found");
return _NodeMatrix[nodeNumber].Count(column => column > 0);
}
public override int InDegree(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
* return number of link in this node is other node point to this node
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (nodeNumber > base._Size - 1)
throw new NonExistentNodeException("Node not found");
return _NodeMatrix.Count(row => row[nodeNumber] > 0);
}
public override List<int> ReachableFrom(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (nodeNumber > base._Size - 1)
throw new NonExistentNodeException("Node not found");
/**
* Create 2 list to store node
* reachableList is a final result list
* Store node into nonCheckNodeList when this node was checked.
* Prevent repeat to check
*/
List<int> reachableList = new List<int>();
List<int> nonCheckNodeList = new List<int>();
bool update;
//Source node must be add to reachableList
reachableList.Add(nodeNumber);
do
{
/**
* Initial the update to false
* because we will check the node is it repeat.
*
* Create a checkNodeList
* checkNodeList only store a will check node
* It filter the nonCheckNodeList node
*
* Loop the checkNodeList
*/
update = false;
List<int> checkNodeList = reachableList.Except(nonCheckNodeList).ToList();
for (int i = 0; i < checkNodeList.Count; i++)
{
/**
* Add current node to nonCheckNodeList
* because current node was checked.
*
* Define the List and check this node can reach to which node
*/
nonCheckNodeList.Add(reachableList[i]);
IEnumerable<int> result = _NodeMatrix[checkNodeList[i]]
.Select((column, index) => new { column, index })
.Where(obj => obj.column > 0)
.Select(obj => obj.index);
foreach (int temp in result)
{
/**
* Check node is it repeat
* if not repeat is should be store in reachableList
* and update set to true
* because this node was store into the reachableList
*/
if (!reachableList.Exists(node => node == temp))
{
update = true;
reachableList.Add(temp);
}
}
}
} while (update);
/**
* Sorting the list
* and return the result
*/
reachableList.Sort();
return reachableList;
}
}
}
using System.Collections.Generic;Link Class
using System.Linq;
using System.Text;
namespace NetworkLibrary
{
public class LL_Network : Network
{
private NetworkLibrary.Link[] _NodeLinks;
public NetworkLibrary.Link[] NodeLinks
{
get { return _NodeLinks; }
}
public LL_Network(int numberOfNode, int[][] nodeMap)
{
/**
* Error checking
* No node exception
* Null argument exception
* Too many exception
*/
if (numberOfNode < 1)
throw new NumberOfNodeLessThenOneException("Number Of Node Less Then One");
else if (nodeMap == null)
throw new ArgumentNullException("Node Map is null");
else if (numberOfNode * numberOfNode < nodeMap.Length)
throw new TooManyLinkException("Too Many Link");
//Store to local variable
base._Size = numberOfNode;
_NodeLinks = new Link[nodeMap.Length];
//Create Link from array
for (int i = 0; i < nodeMap.Length; i++)
{
if (nodeMap[i].Length != 3)
throw new LinkNumberOfArgumentException("Link Must have 3 Argument");
_NodeLinks[i] = new Link(nodeMap[i][0], nodeMap[i][1], nodeMap[i][2]);
}
}
public AM_Network To_AM()
{
/**
* Create a 2D array
* Assign a link value into array
*/
int[,] amStructure = new int[base._Size, base._Size];
for (int i = 0; i < base._Size; i++)
{
for (int ii = 0; ii < base._Size; ii++)
{
IEnumerable<Link> result = _NodeLinks.Where(n => n.Node == i && n.DestinationNode == ii);
amStructure[i,ii] = (result.Count() > 0) ? result.First().Weight : 0;
}
}
return new AM_Network(base._Size, amStructure);
}
public override string ToString()
{
/**
* retrun network type
* network size and total link
*/
string info = "Network Type: List-of-Links\n";
info += "Network Size: " + base._Size + "\n";
info += "Number Of Link: " + NumberOfLinks() + "\n";
return info;
}
public override int NumberOfLinks()
{
//Return network total link
return _NodeLinks.Length;
}
public override int OutDegree(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
* return number of link in this node point to other node
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (!_NodeLinks.ToList().Exists(link => link.Node == nodeNumber))
throw new NonExistentNodeException("Node not found");
return _NodeLinks.Count(link => link.Node == nodeNumber);
}
public override int InDegree(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
* return number of link in this node is other node point to this node
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (!_NodeLinks.ToList().Exists(link => link.Node == nodeNumber))
throw new NonExistentNodeException("Node not found");
return _NodeLinks.Count(link => link.DestinationNode == nodeNumber);
}
public override List<int> ReachableFrom(int nodeNumber)
{
/**
* Error checking
* Negative node number exception
* Node not found exception
*/
if (nodeNumber < 0)
throw new NegativeNodeNumberException("Node Number Cannot be a Negative Number");
else if (!_NodeLinks.ToList().Exists(link => link.Node == nodeNumber))
throw new NonExistentNodeException("Node not found");
/**
* Create 2 list to store node
* reachableList is a final result list
* Store node into nonCheckNodeList when this node was checked.
* Prevent repeat to check
*/
List<int> reachableList = new List<int>();
List<int> nonCheckNodeList = new List<int>();
bool update;
//Source node must be add to reachableList
reachableList.Add(nodeNumber);
do
{
/**
* Initial the update to false
* because we will check the node is it repeat.
*
* Create a checkNodeList
* checkNodeList only store a will check node
* It filter the nonCheckNodeList node
*
* Loop the checkNodeList
*/
update = false;
List<int> checkNodeList = reachableList.Except(nonCheckNodeList).ToList();
for (int i = 0; i < checkNodeList.Count; i++)
{
/**
* Add current node to nonCheckNodeList
* because current node was checked.
*
* Define the List and check this node can reach to which node
*/
nonCheckNodeList.Add(reachableList[i]);
IEnumerable<Link> result = _NodeLinks.Where(link => link.Node == checkNodeList[i]);
foreach (Link temp in result)
{
/**
* Check node is it repeat
* if not repeat is should be store in reachableList
* and update set to true
* because this node was store into the reachableList
*/
if (!reachableList.Exists(node => node == temp.DestinationNode))
{
update = true;
reachableList.Add(temp.DestinationNode);
}
}
}
} while (update);
/**
* Sorting the list
* and return the result
*/
reachableList.Sort();
return reachableList;
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace NetworkLibrary
{
public struct Link
{
/**
* _Node store a current Node
* _DestinationNode store a next Node
* _Weight store a link weight
*/
private int _Node;
private int _DestinationNode;
private int _Weight;
public int Node
{
get { return _Node; }
set { _Node = value; }
}
public int DestinationNode
{
get { return _DestinationNode; }
set { _DestinationNode = value; }
}
public int Weight
{
get { return _Weight; }
set { _Weight = value; }
}
//Constructor
public Link(int node, int destinationNode, int weight)
{
_Node = node;
_DestinationNode = destinationNode;
_Weight = weight;
}
}
}
相關書籍:
