while (current_arc!= NULL) {
printf(" ==> Дуга %s выходит из узла %s и входит в узел %s.\n", current_arc->name,
current_arc->aux_elem_output_pointer->output_pointer->node_pointer->name,
current_arc->aux_elem_input_pointer->input_pointer->node_pointer->name);
current_arc = current_arc->next;
}
current_graph = current_graph->next;
}
}
#endif /* WALK_THROUGH_H */
//graph_copy
#include <stdlib. h>
#include <string. h>
#include <stdio. h>
#include <iostream>
#include <math. h>
#include <ctime>
#include "structs_description. h"
using namespace std;
#ifndef GRAPH_COPY_H
#define GRAPH_COPY_H
graph *copy_graph(graph *);
node *copy_node(int, node *, graph *);
input *copy_input(int, node *);
output *copy_output(int, node *);
graph *copy_graph(graph *g){
graph *copy;
copy = (graph *) malloc(sizeof (graph));
copy->mark = 4;
copy->prev = NULL;
copy->next = NULL;
// Должны быть NULL потому что будут создаваться новые элементы.
copy->node_pointer = NULL;
copy->arc_pointer = NULL;
copy->number_of_nodes = g->number_of_nodes;
copy->arn = 2;
copy->node_pointer = copy_node(g->number_of_nodes, g->node_pointer, copy);
copy->arc_pointer = create_arc(copy);
return copy;
}
node *copy_node(int n, node *copied_nodes, graph *copy){
// Результирующая вершина.
node *head_node = NULL;
node *current1, *current2;
//char buffer[BUFFERSIZE];
node *copied_node;
// Копируемые вершины.
copied_node = copied_nodes;
current1 = (node *) malloc(sizeof (node));
current1->prev = NULL;
current1->prevv = NULL;
current1->next = NULL;
current1->nextt = NULL;
current1->uid = copied_node->uid;
current1->graph_pointer = copy;
// Копировние имени
strcpy(current1->name, copied_node->name);
// Скопировать входы
current1->number_of_inputs = copied_node->number_of_inputs;
current1->input_pointer = copy_input(current1->number_of_inputs, current1);
// Скопировать выходы
current1->number_of_outputs = copied_node->number_of_outputs;
current1->output_pointer = copy_output(current1->number_of_outputs, current1);
// Координаты
current1->x_cur = copied_node->x_cur;
current1->y_cur = copied_node->y_cur;
current1->radius = copied_node->radius;
current1->speed = copied_node->speed;
head_node = current1;
copied_node = copied_node->next;
for (int i = 1; i < n; i++) {
if (copied_node){
current2 = (node *) malloc(sizeof (node));
current1->next = current2;
current2->prev = current1;
current2->next = NULL;
//current2->corrected = 0;
current2->nextt = NULL;
current2->prevv = NULL;
current2->uid = copied_node->uid;
current2->graph_pointer = copy;
strcpy(current2->name, copied_node->name);
current2->number_of_inputs = copied_node->number_of_inputs;
current2->input_pointer = copy_input(current2->number_of_inputs, current2);
current2->number_of_outputs = copied_node->number_of_outputs;
current2->output_pointer = copy_output(current2->number_of_outputs, current2);
// Координаты
current2->x_cur = copied_node->x_cur;
current2->y_cur = copied_node->y_cur;
current2->radius = copied_node->radius;
current2->speed = copied_node->speed;
current1 = current2;
copied_node = copied_node->next;
}
}
return head_node;
}
input *copy_input(int n, node *current_node) {
input *head_input = NULL;
input *current1, *current2;
if (n > 0) {
current1 = (input *) malloc(sizeof (input));
current1->prev = NULL;
current1->next = NULL;
current1->aux_elem_pointer = NULL;
current1->mark = 6;
//0fscanf(fp, "%s", current1->name);
// Формирование имени входа.
strcpy(current1->name, current_node->name);
strcat(current1->name, "_");
strcat(current1->name, "inp1");
/*
cout << " * Enter the input name: " << endl;
cin >> current1->name;
*/
current1->link_with_process = 0;
current1->node_pointer = current_node;
head_input = current1;
for (int i = 1; i < n; i++) {
current2 = (input *) malloc(sizeof (input));
current1->next = current2;
current2->prev = current1;
current2->next = NULL;
current2->aux_elem_pointer = NULL;
current2->mark = 6;
//fscanf(fp, "%s", current2->name);
//strcpy(current2->name, current_node->name);
//strcat(current2->name, "_");
//strcat(current2->name, "inp");
//strcat(current2->name, i+1);
cout << " * Enter the " << i + 1 << "input name: " << endl;
cin >> current2->name;
// Формирование имени входа.
//strcpy(current2->name, current_node->name);
//strcat(current2->name, "_");
//strcat(current2->name, "inp");
current2->link_with_process = 0;
current2->node_pointer = current_node;
current1 = current2;
}
fflush(stdout);
}
return head_input;
};
output *copy_output(int n, node *current_node) {
output *head_output = NULL;
output *current1, *current2;
if (n > 0) {
current1 = (output *) malloc(sizeof (output));
current1->prev = NULL;
current1->next = NULL;
current1->mark = 7;
current1->aux_elem_pointer = NULL;
//fscanf(fp, "%s", current1->name);
//cout << " * Enter the output name: " << endl;
//cin >> current1->name;
// Формирование имени выхода.
strcpy(current1->name, current_node->name);
strcat(current1->name, "_");
strcat(current1->name, "out1");
current1->link_with_process = 0;
current1->node_pointer = current_node;
head_output = current1;
for (int i = 1; i < n; i++) {
fflush(stdout);
current2 = (output *) malloc(sizeof (output));
current1->next = current2;
current2->prev = current1;
current2->next = NULL;
current2->mark = 7;
current2->aux_elem_pointer = NULL;
//fscanf(fp, "%s", current2->name);
cout << " * Enter the " << i + 1 << "output name: " << endl;
cin >> current2->name;
current2->link_with_process = 0;
current2->node_pointer = current_node;
current1 = current2;
}
fflush(stdout);
}
return head_output;
};
#endif /* GRAPH_COPY_H */
/*
* Функции вычисляющие характеристики графа. Связность, количество компонент связности,
* вершинную и ребёрную связность. Для вычисления вершинной связности необходимо
* создавать копию исходного графа, так как его структура подвергнется изменениям.
*/
#ifndef CHECK_GRAPH_H
#define CHECK_GRAPH_H
#define ABSOLUTE_MAX 100000
#define MAX_ELEM 1000
#define MAX_RIB 1000
#define RIB_SIZE 100
#include "structs_description. h"
//#include "load_module. h"
#include "functions. h"
#include "graph_copy. h"
#include "walk_through. h"
typedef struct _queue queue;
struct _queue {
node *head;
node *tail;
};
int find_num_conponents(graph *g);
int find_rib_relations(graph *g);
int find_node_relations(graph *g);
int check_relations(graph *g);
void init_que(queue* que) {
que->head = NULL;
que->tail = NULL;
}
void destroy_que(queue* que) {
node* cursor;
while (que->tail) {
cursor = que->tail;
que->tail = que->tail->prevv;
free(cursor);
}
que->head = que->tail;
};
void push_front(queue *que, node *val) {
node *que_elem;
que_elem = (node *) malloc(sizeof (node));
que_elem = val;
que_elem->prevv = NULL;
que_elem->nextt = que->head;
if (que->head)
que->head->prevv = que_elem;
else
que->tail = que_elem;
que->head = que_elem;
}
node *pop_back(queue* que) {
node *val = 0;
if (que->tail) {
val = que->tail;
if (que->tail == que->head)
que->head = NULL;
que->tail = que->tail->prevv;
if (que->tail) {
//free(que->tail->nextt);
que->tail->nextt = NULL;
}
}
return val;
}
/*
* Определяет является ли граф связным или нет.
*/
int check_relations(graph *g) {
int result = 1;
int used_counter = g->number_of_nodes;
int used[MAX_ELEM];
memset(used, 0, sizeof (used));
node *start_node = g->node_pointer;
node *cursor;
aux_elem_arc *aux_pointer = NULL;
queue *que;
que = (queue *) malloc(sizeof (queue));
init_que(que);
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 |
