Программирование на C#. Графы. Матрица смежности

1.

Богатов Р.Н.
Программирование на C#
Графы. Матрица смежности
Кафедра АСОИУ ОмГТУ, 2022

3.

Граф диалогов персонажей сериала «Игра престолов»
Вершин (персонажей): 1105
Рёбер (диалогов): 3505
Размер вершины – количество сказанных слов
Толщина ребра – количество состоявшихся разговоров

4.

Остовное дерево («скелет» графа диалогов персонажей)
Детали исследования см. в статье
«Теория графов в Игре Престолов»

namespace Граффф
{
public partial class Form1 : Form
{
int N;
public Form1()
{
InitializeComponent();
numericUpDown1.Value = 10;
}
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
N = (int)numericUpDown1.Value;
dataGridView1.RowCount = dataGridView1.ColumnCount = N;
for (int i = 0; i < N; i++)
dataGridView1[i, i].Style.BackColor = Color.Gray;
}
}
}

7.

public partial class Form1 : Form
{
int N;
Random rand = new Random();
...
private void button1_Click(object sender, EventArgs e)
{
for (int i = 0; i < N-1; i++)
for (int j = i+1; j < N; j++)
dataGridView1[j, i].Value =
dataGridView1[i, j].Value = rand.Next(2);
}
}

8.

private void button2_Click(object sender, EventArgs e)
{
int[,] A = new int[N, N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
A[i,j] = Convert.ToInt32( dataGridView1[j, i].Value );
bool oriented = false;
for (int i = 0; i < N - 1 && !oriented; i++)
for (int j = i + 1; j < N && !oriented; j++)
if (A[i, j] != A[j, i]) oriented = true;
}
}
if
...(oriented)
{
textBox1.Text = oriented ?
textBox1.Text
= "Граф ориентированный.
Список дуг:\r\n";
"Граф ориентированный.
Список дуг:\r\n":
for
(int
i = 0; i < N; i++)
"Граф
неориентированный.
Список рёбер:\r\n";
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
if (A[i, j] != 0)
for (int j =textBox1.Text
oriented ? 0 +=
: i;
j +
< (i+1)
N; j++)
"("
+ ", " + (j+1) + ")\r\n";
if
(A[i,
j]
!=
0)
}
textBox1.Text += "(" + (i + 1) + ", " + (j + 1) + ")\r\n";
else
{
textBox1.Text = "Граф неориентированный. Список рёбер:\r\n";
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
if (A[i, j] != 0)
textBox1.Text += "(" + (i+1) + ", " + (j+1) + ")\r\n";
}

9.

10.

11.

// задача: обеспечить контроль ввода взвешенного графа с вещественными весами
private void button2_Click(object sender, EventArgs e)
{
double[,] A = new double[N, N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
try
{
A[i, j] = Convert.ToDouble(dataGridView1[j, i].Value);
}
catch
{
MessageBox.Show("Неверный формат числа в ячейке ("
+(i+1)+", "+(j+1)+")", "Ошибка ввода");
return;
}
...
}

12.

// задача: заведомо выделять ошибки ввода красным цветом
private void button2_Click(object sender, EventArgs e)
{
double[,] A = new double[N, N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
try
{
A[i, j] = Convert.ToDouble(dataGridView1[j, i].Value);
}
catch
{
MessageBox.Show("Исправьте красные значения", "Ошибка ввода");
return;
}
...
}
private void dataGridView1_CellValueChanged(object sender, DataGridViewCellEventArgs e)
{
try
{
Convert.ToDouble( dataGridView1[e.ColumnIndex, e.RowIndex].Value );
dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Black;
}
catch
{
dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Red;
}
}

13.

// задача: обеспечить ввод неориентированного графа без петель
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
N = (int)numericUpDown1.Value;
dataGridView1.RowCount = dataGridView1.ColumnCount = N;
for (int i = 0; i < N; i++)
{
dataGridView1[i, i].Style.BackColor = Color.Gray;
dataGridView1[i, i].ReadOnly = true;
}
}
private void dataGridView1_CellValueChanged(object sender, DataGridViewCellEventArgs e)
{
try
{
Convert.ToDouble( dataGridView1[e.ColumnIndex, e.RowIndex].Value );
dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Black;
dataGridView1[e.RowIndex, e.ColumnIndex].Value =
dataGridView1[e.ColumnIndex, e.RowIndex].Value;
}
catch
{
dataGridView1[e.ColumnIndex, e.RowIndex].Style.ForeColor = Color.Red;
}
}

14.

Сохранение матрицы смежности в файл

15.

using System.IO;
...
private
sender,
EventArgs
private void
void открытьToolStripMenuItem_Click(object
сохранитьToolStripMenuItem_Click(object
sender,
EventArgse)e)
{
{
openFileDialog1.DefaultExt
".graph";
double[,] A = new double[N,=N];
openFileDialog1.Filter
= "Графы
в формате *.graph|*.graph|Все
файлы|*.*";
// импорт матрицы смежности
неориентированного
графа
for (int i = 0; i < N - 1; i++)
if (openFileDialog1.ShowDialog()
!= DialogResult.OK) return;
for (int j = i + 1; j < N; j++)
}
try
numericUpDown1.Value
= 0;
{
FileStream fs
= new
FileStream(openFileDialog1.FileName,
FileMode.Open);
A[i,
j] =
A[j, i] = Convert.ToDouble( dataGridView1[j,
i].Value );
BinaryReader
br
=
new
BinaryReader(fs);
}
numericUpDown1.Value
= br.ReadInt32(); // здесь сработает numericUpDown1_ValueChanged()
catch
for (int{i = 0; i < N; i++)
for (intMessageBox.Show("Исправьте
j = 0; j < N; j++)
красные значения", "Неверный формат"); return;
dataGridView1[j,
i].Value
=
br.ReadDouble();
}
br.Close();
fs.Close();
saveFileDialog1.DefaultExt = ".graph";
saveFileDialog1.Filter = "Графы в формате *.graph|*.graph|Все файлы|*.*";
if (saveFileDialog1.ShowDialog() != DialogResult.OK) return;
FileStream fs = new FileStream(saveFileDialog1.FileName, FileMode.Create);
BinaryWriter bw = new BinaryWriter(fs);
bw.Write(N); // сначала сохраняем количество вершин
foreach (double x in A) // обходит многомерный массив по рядам, потом по слоям и т.д.
bw.Write(x);
bw.Close();
fs.Close();
}

16.

Сохранение матрицы смежности в XML

17.

using System.Xml;
...
private void сохранитьToolStripMenuItem_Click(object sender, EventArgs e)
{
...
if (saveFileDialog1.FilterIndex
== 1) // сохранение
графа
в формате
private
void открытьToolStripMenuItem_Click(object
sender,
EventArgs
e) .xml
{ {
... XmlTextWriter w = new XmlTextWriter(saveFileDialog1.FileName, Encoding.Unicode);
w.Formatting = Formatting.Indented;
if (openFileDialog1.FilterIndex
== 1) // чтение из .xml
w.WriteStartDocument();
{
w.WriteStartElement("Граф");
// <Граф
XmlTextReader r = new XmlTextReader(openFileDialog1.FileName);
w.WriteAttributeString("Вершин",
XmlConvert.ToString(N)); // <Граф Вершин="5"
r.ReadToFollowing("Граф");
w.WriteStartElement("Матрица_смежности");
<Матрица_смежности
numericUpDown1.Value = XmlConvert.ToInt32(//r.GetAttribute("Вершин")
);
}
}
r.ReadToFollowing("Матрица_смежности");
for
for (int
(int ii == 0;
0; ii << N;
N; i++)
i++)
{{
w.WriteStartElement("Строка"
1)); // <Строка1
r.ReadToFollowing("Строка" + +(i(i+ +1));
for
for (int
(int jj == 0;
0; jj << N;
N; j++)
j++)
w.WriteAttributeString("Яч"
dataGridView1[j, i].Value = + (j + 1), XmlConvert.ToString(A[i, j]));
w.WriteEndElement();
// <Строка1
Яч1="0" Яч2="0"
/>
XmlConvert.ToDouble(
r.GetAttribute(
"Яч"...
+ (j+1)
) );
}}
w.WriteEndElement();
// </Матрица_смежности>
r.Close();
} w.WriteEndElement(); // </Граф>
elsew.WriteEndDocument();
// чтение из .graph
w.Close();
{
}
...
else
// сохранение графа в формате .graph
}
{
...
}

18.

Домашнее задание
Найти в графе все клики, состоящие из трёх вершин
(«3-клики», см. https://ru.wikipedia.org/Клика)
В следующих лекциях
• Обход графа в глубину и в ширину
• Раскраска графа
• Графическая визуализация графа
• Графический редактор графа

English Русский Rules