今次的 Adjacency Matrix Network 加進了新的功能
- 可以找出最短路徑
- 讀取文字檔來輸入路徑訊息
- GUI
GUI 使用了 WPF 技術
原始碼:
AM_Network
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace NetworkLibrary
{
public class AM_Network : Network
{
//Define the large number for shortest path function node init value
private const int _LargeNumber = 5000000;
private int [ , ] _LinkMatrix; // the adjacency matrix
public int LargeNumber
{
get { return _LargeNumber; }
}
public int[,] LinkMatrix
{
get { return _LinkMatrix; }
}
// constructor to create an AM Network with given number of nodes and adjacency matrix
// raise TypeLoadException if something wrong with the input data
// Note : We could define our own exceptions, but have chosen not to do so
public AM_Network(int numNodes, int[ , ] theMatrix)
{
if (numNodes <= 0)
throw new TypeLoadException("Must have positive number of nodes");
else
_Size = numNodes;
if ((theMatrix.GetLength(0) != numNodes) || (theMatrix.GetLength(1) != numNodes))
throw new TypeLoadException("Array size not the same as number of nodes");
else
_LinkMatrix = theMatrix;
}
public AM_Network(string fileName)
{
//handel file not found
if (!File.Exists(fileName))
throw new FileNotFoundException("File do not exists");
int lineNumber = 0;
try
{
/**
* Starting read the text file
* trim each line
* convert the first line string to integer
* init the martrix
*/
FileStream input = new FileStream(fileName, FileMode.Open, FileAccess.Read);
StreamReader fileReader = new StreamReader(input);
string line = fileReader.ReadLine().Trim();
lineNumber++;
_Size = Convert.ToInt32(line);
_LinkMatrix = new int[Size, Size];
for (int i = 0; i < Size; i++)
{
/**
* Read line
* Checking line have a data
* Checking number of integer is same to matrix size
* if not same to matrix size will throw exception
*/
lineNumber++;
line = fileReader.ReadLine();
if (line == null)
throw new MatrixNotCorrectException();
string[] tempArray = line.Split(',');
if (tempArray.Length > Size || tempArray.Length < Size)
throw new MatrixNotCorrectException();
for (int ii = 0; ii < tempArray.Length; ii++)
_LinkMatrix[i, ii] = Convert.ToInt32(tempArray[ii]);
}
//Close the reader and streaming
fileReader.Close();
input.Close();
}
catch (FormatException)
{
throw new FormatException("Number format error in line " + lineNumber);
}
catch (Exception ex)
{
throw new Exception(ex.Message + " in line " + lineNumber);
}
}
// return the number of links in the network
public override int NumberOfLinks()
{
int result = 0;
// just count the number of non-zero elements in the adjacency matrix
foreach (int element in _LinkMatrix)
if (element != 0)
result++;
return result;
}
// return the out-degree of node aNode in the network
public override int OutDegree(int aNode)
{
if (aNode > Size)
throw new NonExistentNodeException();
int result = 0;
// count the number of non-zero entries in row aNode of the adjacency matrix
for (int j = 0; j < Size; j++)
if (_LinkMatrix[aNode,j] != 0)
result++;
return result;
}
// return the in-degree of node aNode in the network
public override int InDegree(int aNode)
{
if (aNode > Size)
throw new NonExistentNodeException();
int result = 0;
// count the number of non-zero entries in column aNode of the adjacency matrix
for (int j = 0; j < Size; j++)
if (_LinkMatrix[j, aNode] != 0)
result++;
return result;
}
// return the list of nodes reachable from aNode in this network
// less detailed comments than in class LL_Network
public override List<int> ReachableFrom(int aNode)
{
if (aNode > Size)
throw new NonExistentNodeException();
List<int> result = new List<int>();
// set up 3 Boolean arrays to hold information about newly connected nodes
Boolean[] selectedNodes = new Boolean[Size];
Boolean[] selectedOnThisPass = new Boolean[Size];
Boolean[] selectedOnLastPass = new Boolean[Size];
// set up a Boolean variable to record if any new nodes were selected on the last pass
Boolean wasNew;
// start off by selecting node aNode itself on the first pass
selectedNodes[aNode] = true;
selectedOnThisPass[aNode] = true;
wasNew = true;
// now check over all the nodes added on the last pass to see if
// any new nodes are connectable to them, and hence to aNode
// only do this if there were nodes added on the last pass
// stop when no new node was added on last pass
while (wasNew)
{
// first copy the "selected on this pass" from last pass to "selected on last path" for this pass
// and reset "selected on this path" to all false
for (int i = 0; i < selectedOnLastPass.Length; i++)
selectedOnLastPass[i] = selectedOnThisPass[i];
for (int i = 0; i < selectedOnThisPass.Length; i++)
selectedOnThisPass[i] = false;
// reset wasNew to false at the start of the pass
wasNew = false;
for (int i = 0; i < Size; i++)
{
// if l.From was added to the connected nodes on the last pass
// and l.To is not yet connected, then signal that l.To is now
// connected, and that it has been connected on this pass;
// also indicate that a new node has been connected
if (selectedOnLastPass[i])
for (int j = 0; j < Size; j++)
if ((_LinkMatrix[i,j] != 0) && !selectedNodes[j])
{
selectedNodes[j] = true;
selectedOnThisPass[j] = true;
wasNew = true;
}
}
}
// now build the list that is to be returned by scanning the array selectedNodes
for (int i = 0; i < selectedNodes.Length; i++)
if (selectedNodes[i])
result.Add(i);
return result;
}
// return string representation of the network
public override string ToString()
{
string result = "<";
string theMatrix = "";
for (int i = 0; i < Size; i++)
{
theMatrix += "|";
for (int j = 0; j < Size; j++)
{
theMatrix += " " +_LinkMatrix[i,j];
if (j == (Size-1))
theMatrix += "|\n";
}
}
result += Size.ToString() + ",\n" + theMatrix + ">";
return result;
}
// return the network in LL form
public LL_Network To_LL()
{
List<Link> Links = new List<Link>();
// for each row in the adjacency matrix, build link objects and add to Links
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
if (_LinkMatrix[i,j] != 0)
{
Link l = new Link(i,j,_LinkMatrix[i,j]);
Links.Add(l);
}
LL_Network result = new LL_Network(Size, Links);
return result;
}
public List<NetworkLibrary.Path> shortestPaths(int startNode)
{
if (startNode > Size)
throw new NonExistentNodeException();
List<Path> pathList = new List<Path>();
/*for (int i = 0; i < Size; i++)
{
pathList.Add(shortestPaths(startNode, i)[0]);
}*/
/**
* Define the node value
* Define node shortest neighbour
* Init the value and shortedt neighbor
*/
bool[] nodeVisited = new bool[Size];
int[] nodesValue = new int[Size];
int[] nodesShortesNeighbour = new int[Size];
for (int i = 0; i < Size; i++)
{
nodeVisited[i] = false;
nodesValue[i] = LargeNumber;
nodesShortesNeighbour[i] = -1;
}
//self node value is 0
nodesValue[startNode] = 0;
List<int> checkNodeList = new List<int>();
checkNodeList.Add(startNode);
//If checkNodeList have data will continue the looping
while (checkNodeList.Count > 0)
{
/**
* Checking this node was check or not
* if has been check will remove that
*/
if (nodeVisited[checkNodeList[0]] == false)
{
//check current node all out going link
for (int i = 0; i < Size; i++)
{
//Checking which link is link to other node
if (_LinkMatrix[checkNodeList[0], i] > 0)
{
//Checking this link weight is it less than the last value
if ((_LinkMatrix[checkNodeList[0], i] + nodesValue[checkNodeList[0]]) < nodesValue[i])
{
//Assign the new value into destination node value
//Destination node shortest neighbor is current node
//Put the destination node into check list
//Updated node should be check again
nodesValue[i] = _LinkMatrix[checkNodeList[0], i] + nodesValue[checkNodeList[0]];
nodesShortesNeighbour[i] = checkNodeList[0];
checkNodeList.Add(i);
nodeVisited[i] = false;
}
}
}
nodeVisited[checkNodeList[0]] = true;
}
else
{
checkNodeList.RemoveAt(0);
}
}
//Checking end node is reachable
for (int i = 0; i < Size; i++)
{
if (nodesValue[i] < LargeNumber)
{
List<int> nodeList = new List<int>();
Path path = new Path();
int currentNode = i;
//From end node to start node to fine the shortest path
while (currentNode != startNode)
{
nodeList.Add(currentNode);
currentNode = nodesShortesNeighbour[currentNode];
}
nodeList.Add(startNode);
//Reverse the list
//Start node in list index 0
nodeList.Reverse();
path.NodeList = nodeList;
path.Length = nodesValue[i];
pathList.Add(path);
}
else
{
//End Node unreachable should return the LargeNumber path length
Path path = new Path();
path.NodeList = null;
path.Length = LargeNumber;
pathList.Add(path);
}
}
return pathList;
}
public List<NetworkLibrary.Path> shortestPaths(int startNode, int endNode)
{
if (startNode > Size || endNode > Size)
throw new NonExistentNodeException();
List<Path> pathList = new List<Path>();
pathList.Add(shortestPaths(startNode)[endNode]);
return pathList;
}
}
}
Path:
using System;
using System.Collections.Generic;
using System.Text;
namespace NetworkLibrary
{
public class Path
{
private List<int> _NodeList;
private int _Length;
public int Length
{
get { return _Length; }
set { _Length = value; }
}
public List<int> NodeList
{
get { return _NodeList; }
set { _NodeList = value; }
}
}
}
Windows.xaml:
<Window x:Class="NetworkView.Window1"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
Title="Window1" Width="680" Height="768" WindowStyle="ToolWindow" ResizeMode="NoResize">
<Grid>
<Grid Height="41.675" Margin="13.336,12,280.056,0" Name="grid1" VerticalAlignment="Top">
<TextBox Margin="37,9.994,170.034,8.335" Name="fileName" IsReadOnly="True" />
<Button Margin="0,9.994,88.351,9.476" Name="btnBrowse" Click="browseTextFile" HorizontalAlignment="Right" Width="76">Browse</Button>
<Label HorizontalAlignment="Left" Margin="-1.336,9.003,0,6" Name="label1" Width="37">File:</Label>
<Button HorizontalAlignment="Right" Margin="0,9.994,6,9.476" Name="btnConfirm" Width="76" Click="confirm">Confirm</Button>
</Grid>
<Canvas Width="630" Height="630" Margin="12,86.684,12,12" Name="cvsNodeView"></Canvas>
<Grid Height="68" Margin="0,12,12,0" Name="grid2" VerticalAlignment="Top" HorizontalAlignment="Right" Width="261.719">
<ComboBox Margin="70.014,5.001,6,0" Name="cmbFromNode" Height="22.991" VerticalAlignment="Top" />
<Label HorizontalAlignment="Left" Margin="0,5.001,0,0" Name="label2" Width="63" Height="24.658" VerticalAlignment="Top">From:</Label>
<Label Margin="0,34,0,12" Name="label3" HorizontalAlignment="Left" Width="64" Height="24.658" FlowDirection="LeftToRight">To:</Label>
<ComboBox Margin="70.014,0,6,11.669" Name="cmbToNode" Height="22" VerticalAlignment="Bottom" />
</Grid>
</Grid>
</Window>
Window.xaml.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.IO;
using NetworkLibrary;
namespace NetworkView
{
/// <summary>
/// Interaction logic for Window1.xaml
/// </summary>
public partial class Window1 : Window
{
private AM_Network AN;
private List<Ellipse> ellipses;
private TextBlock txtPathLength;
private Line[,] lines;
public Window1()
{
InitializeComponent();
ellipses = new List<Ellipse>();
txtPathLength = new TextBlock();
}
private void browseTextFile(object sender, RoutedEventArgs e)
{
Microsoft.Win32.OpenFileDialog dlg = new Microsoft.Win32.OpenFileDialog();
// Set filter for file extension and default file extension
dlg.DefaultExt = ".txt";
dlg.Filter = "Text File (.txt) | *.txt";
// Display OpenFileDialog by calling ShowDialog method
Nullable<bool> result = dlg.ShowDialog();
// Get the selected file name and display in a TextBox
if (result == true)
{
// Open document
string filename = dlg.FileName;
fileName.Text = filename;
}
}
private void confirm(object sender, RoutedEventArgs e)
{
try
{
//Create a AM Network
AN = new AM_Network(fileName.Text);
//Clear all remain data
cmbFromNode.SelectionChanged -= updateShortestPath;
cmbToNode.SelectionChanged -= updateShortestPath;
cmbFromNode.Items.Clear();
cmbToNode.Items.Clear();
cvsNodeView.Children.Clear();
//Add node into component
for (int i = 0; i < AN.Size; i++)
{
ComboBoxItem cmbFromNodeItem = new ComboBoxItem();
ComboBoxItem cmbToNodeItem = new ComboBoxItem();
cmbFromNodeItem.Content = "Node " + i;
cmbToNodeItem.Content = "Node " + i;
cmbFromNode.Items.Add(cmbFromNodeItem);
cmbToNode.Items.Add(cmbToNodeItem);
}
//Draw a node view and link
drawNodeView();
cmbFromNode.SelectedIndex = 0;
cmbToNode.SelectedIndex = 0;
//Set the combox changed action
cmbFromNode.SelectionChanged += updateShortestPath;
cmbToNode.SelectionChanged += updateShortestPath;
}
catch (Exception ex)
{
MessageBox.Show(ex.Message, "Error");
}
}
private void drawNodeView()
{
double w = cvsNodeView.Width >= cvsNodeView.Height ? cvsNodeView.Height : cvsNodeView.Width;
double nodeSize = cvsNodeView.Width / AN.Size * 0.7;
//Draw a link first
lines = new Line[AN.LinkMatrix.GetLength(0), AN.LinkMatrix.GetLength(0)];
for (int i = 0; i < AN.LinkMatrix.GetLength(0); i++)
{
//Define the x, y from current node
double x1 = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Cos(2 * Math.PI * i / AN.Size) + nodeSize / 2;
double y1 = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Sin(2 * Math.PI * i / AN.Size) + nodeSize / 2;
for (int ii = i; ii < AN.LinkMatrix.GetLength(0); ii++)
{
if (AN.LinkMatrix[i, ii] > 0)
{
Line myLine = new Line();
myLine.X1 = x1;
myLine.Y1 = y1;
//Set the x2, y2 to destination node
myLine.X2 = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Cos(2 * Math.PI * ii / AN.Size) + nodeSize / 2;
myLine.Y2 = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Sin(2 * Math.PI * ii / AN.Size) + nodeSize / 2;
//line style
myLine.StrokeThickness = 2;
myLine.Stroke = Brushes.Black;
//Add to canvas
cvsNodeView.Children.Add(myLine);
//Store the line reference for fine shortest path to change color
lines[i, ii] = myLine;
lines[ii, i] = myLine;
//Add the text block to the line center
TextBlock txtLinkWeight = new TextBlock();
txtLinkWeight.Text = AN.LinkMatrix[i, ii].ToString();
txtLinkWeight.FontSize = nodeSize / 4;
txtLinkWeight.Foreground = Brushes.Black;
txtLinkWeight.Background = Brushes.White;
Canvas.SetLeft(txtLinkWeight, (myLine.X1 >= myLine.X2) ? myLine.X1 - ((myLine.X1 - myLine.X2) / 2) : myLine.X2 - ((myLine.X2 - myLine.X1) / 2));
Canvas.SetTop(txtLinkWeight, (myLine.Y1 >= myLine.Y2) ? myLine.Y1 - ((myLine.Y1 - myLine.Y2) / 2) : myLine.Y2 - ((myLine.Y2 - myLine.Y1) / 2));
cvsNodeView.Children.Add(txtLinkWeight);
}
}
}
//Draw a Node
for (int i = 0; i < AN.Size; i++)
{
//Define the ellipse x and y
double ellipseX = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Cos(2 * Math.PI * i / AN.Size);
double ellipseY = (w / 2 - nodeSize / 2) - (w / 2 - nodeSize / 2) * Math.Sin(2 * Math.PI * i / AN.Size);
//Set ellipse color
Ellipse myEllipse = new Ellipse();
myEllipse.Fill = Brushes.Black;
// Set the width and height of the Ellipse.
myEllipse.Width = nodeSize;
myEllipse.Height = nodeSize;
//Set the ellipse x and y in canvas
Canvas.SetLeft(myEllipse, ellipseX);
Canvas.SetTop(myEllipse, ellipseY);
//Add ellipse to canvas and ellipse list
cvsNodeView.Children.Add(myEllipse);
ellipses.Add(myEllipse);
//Create a text block to display the node number
TextBlock txtNodeNumber = new TextBlock();
txtNodeNumber.Text = i.ToString();
txtNodeNumber.FontSize = nodeSize / 3;
txtNodeNumber.Foreground = Brushes.White;
Canvas.SetLeft(txtNodeNumber, (ellipseX + nodeSize / 2) - txtNodeNumber.FontSize / 2);
Canvas.SetTop(txtNodeNumber, (ellipseY + nodeSize / 2) - txtNodeNumber.FontSize / 2);
cvsNodeView.Children.Add(txtNodeNumber);
}
}
private void updateShortestPath(object sender, SelectionChangedEventArgs e)
{
try
{
//Call the shortest path function
List<NetworkLibrary.Path> path = AN.shortestPaths(cmbFromNode.SelectedIndex, cmbToNode.SelectedIndex);
if (path[0].Length < AN.LargeNumber)
{
List<int> nodeList = path[0].NodeList;
int previousNode = -1;
resumeToNormal();
//Change the start node color
ellipses[cmbFromNode.SelectedIndex].Fill = Brushes.DarkRed;
previousNode = nodeList[0];
for (int i = 1; i < nodeList.Count; i++)
{
//Change the next node and line color
ellipses[nodeList[i]].Fill = Brushes.DarkRed;
lines[previousNode, nodeList[i]].Stroke = Brushes.Red;
previousNode = nodeList[i];
}
//Display the path length
txtPathLength.Text = "Path Length: " + path[0].Length;
txtPathLength.FontSize = 20;
txtPathLength.Foreground = Brushes.Black;
cvsNodeView.Children.Add(txtPathLength);
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
}
private void resumeToNormal()
{
//All line should resume resume to black color
for (int i = 0; i < lines.GetLength(0); i++)
{
for (int ii = 0; ii < lines.GetLength(0); ii++)
{
Line myLine = lines[i, ii];
if (myLine != null)
myLine.Stroke = Brushes.Black;
}
}
//All node should resume to black color
for (int i = 0; i < ellipses.Count; i++)
{
ellipses[i].Fill = Brushes.Black;
}
//Remove the path length text block
cvsNodeView.Children.Remove(txtPathLength);
}
}
}
文字檔:
7
0,3429,0,0,0,3050,4250
3429,0,982,0,0,0,0
0,982,0,288,1040,0,0
0,0,288,0,657,0,0
0,0,1040,657,0,732,0
3050,0,0,0,732,0,2716
4250,0,0,0,0,2716,0
第一行是描述有多少個點
以下的都是描述路徑
相閞書籍:
