2 (Первое домашнее задание. Изоморфизм графов)

Домашнее задание 1.Изоморфизм графовЭтап II. Написание программыВ рамках данного этапа требуется реализовать программу, решающую задачуизоморфизма графов согласно алгоритму, предложенному в рамках первого этапа.Формат входных данных.Описание графов считывается программой либо со стандартного потока ввода (cin), либоиз файла. При этом программа должна корректно обрабатывать следующие два основныхформата описания графов:1. матрицы смежности (M);2.

списки ребер (L).Каждая строка в указанных описаниях непосредственно относится к описанию форматаили является комментарием в стиле языка С (например, “//строка с комментарием”Весами ребер могут быть целые и вещественные числа, а также символьныепоследовательности.

В случае, если веса являются вещественными числами, то равенствовесов устанавливается с точностью 0.0001.Матрица смежности (формат M)Первая строка содержит символ, указывающий на тип графа:1. «D» - ориентированный граф;2. «U» - неориентированный граф.Вторая строка содержит информацию о том, является ли граф взвешенным:1. «N» - граф не содержит весов;2. «E» - граф содержит веса, приписанные ребрам;3.

«V» - граф содержит веса, приписанные вершинам;4. «A» - граф содержит веса, приписанные и ребрам, и вершинам.Если граф содержит веса на вершинах или на ребрах, то после указания символа во второйстроке через пробел указывается тип весов. Сначала указывается тип для вершин, потомдля ребер. При этом используются следующие обозначения: «int» - целочисленные веса,«float» - вещественные веса, «string» - строковые веса.Третья строка содержит число N – число вершин графа (по умолчанию, считается, что всевершины пронумерованы от 0 до N-1). Последующие N строк содержат описание матрицысмежности графа, причем элементы матрицы в каждой строке разделены пробелами. Еслиграф содержит веса, приписанные вершинам графа, то они указываются на диагоналиматрицы.Примеры корректного входного описания графа в формате M://Vertex and edge weighted 3-vertex directed cycleDA float float32.03 1.3 00 1.2 3.42.1 0 3.2//3-vertex graph with 1 edgeUN30 1 01 0 00 0 0//Vertex weighted 3-vertex undirected cycleUV float31.2 1 11 2.3 11 1 3.1//Symbol labelled 3-vertex directed cycleDE string30 ‘v(1)’ 00 0 ‘v(2)’‘v(3)’ 0 0Список ребер (формат L)Как и в случае формата M, первые три строки характеризуют информацию о типе графа,наличии весов, приписанных вершинам или ребрам, и числе вершин графа N (поумолчанию, считается, что все вершины пронумерованы от 0 до N-1).

Четвертая строкасодержит число K – число ребер графа. Последующие K строк содержат описание реберграфа. При этом в строке через пробел указываются номера вершин и вес, ребра, если онизаданы. В случае, если граф имеет веса, приписанные вершинам, то последние N строксодержат информацию об этих весах.Примеры корректного входного описания графа в формате L://Vertex and edge weighted 3-vertex directed cycleDA float float330 1 1.31 2 3.42 0 2.12.031.23.2//3-vertex graph with 1 edgeUN310 1//Vertex weighted 3-vertex undirected cycleUV float330 11 22 01.22.33.1//Symbol labelled 3-vertex directed cycleDE string330 1 ‘v(1)’1 2 ‘v(2)’2 0 ‘v(3)’Формат выходных данных.В результате своей работы программа в стандартный поток вывода (cout) или в файлвыдает информацию о том изоморфны ли полученные на вход графы или нет.

В случае,если графы изоморфны, то программа выдает информацию о найденном изоморфизме.Если графы изоморфны, то программа выдает «YES», если нет, то «NO». Далее, в первомслучае, программа последовательно выдает N строк, где N – число вершин в графе,которые задают вектор-столбец найденного изоморфизма.Кроме того, при завершении своей работы программа выдает «1», если графы изоморфны,«0», если графы неизоморфны, и «2», если программа завершила свою работу и при этомне могла установить являются ли графы изоморфными или нет.Примеры корректного выхода программы//Isomorphism 0->2 1->1 2->0YES210//No isomorphismNOПараметры командной строки.Программа должна поддерживать следующие параметры командной строки:1.

–-help, -h – при передаче этого параметра программа должна вывести краткуюсправку о работе с программой, которая включает краткое описание программы, атакже все параметры командной строки и их назначение;2. –-input (M|L), -i (M|L) – параметр определяет тип входного формата (вскобках указаны возможные типы входного формата: M – графы задаются в видематриц смежности, L – графы задаются списками своих ребер);3. –-input_file_1 “filename1.txt” –input_file_2“filename2.txt”, -1 “filename1.txt” –2 “filename2.txt” – еслиуказаны эти параметры, то программа считывает вход из файлов с именем“filename1.txt” и “filename2.txt”, если параметр не указан, тосчитывание происходит со стандартного потока ввода (cin);4.

–-output_file “filename.txt”, -O “filename.txt”, -O - еслиуказан этот параметр, то программа записывает результат работы в файл с именем“filename.txt”, если параметр не указан, то запись происходит в стандартныйпоток вывода (cout);Примеры корректного задания параметров командной строкиisomorphism.exe --help /*вывод краткой справки о работепрограммы*/isomorphism.exe –i M /*программа считывает со стандартногопотока ввода графы, заданные в виде матриц смежности, и выдаетрезультат своей работы в стандартный поток вывода.*/isomorphism.exe --input L –1 test1.txt –2 test2.txt –Oresult.txt /*программа считывает графы, заданные списками своихребер, из файла test1.txt и test2.txt и записывает результатсвоей работы в файл result.txt.*/Примеры некорректного задания параметров командной строкиisomorphism.exe –h –i M /*несогласованные параметры команднойстроки*/isomorphism.exe –i /*пропущен обязательный параметр при“-i”*/isomorphism.exe –1 test.txt /*не задан входной форматпредставления графов и задан только один из двух входныхфайлов.*/.