vs_node_inp->input_pointer = current_node->input_pointer;
vs_node_out->output_pointer = current_node->output_pointer;
vs_node_inp->uid = uid_index;
uid_index += 1;
vs_node_out->uid = uid_index;
uid_index += 1;
vs_node_inp->input_pointer->node_pointer = vs_node_inp;
vs_node_out->output_pointer->node_pointer = vs_node_out;
new_arc = (arc *) malloc(sizeof (arc));
new_arc->prev = NULL;
new_arc->next = NULL;
inp_for_arc = (aux_elem_input *) malloc(sizeof (aux_elem_input));
inp_for_arc->input_pointer = NULL;
inp_for_arc->next = NULL;
out_for_arc = (aux_elem_output *) malloc(sizeof (aux_elem_output));
out_for_arc->output_pointer = NULL;
out_for_arc->next = NULL;
strcpy(new_arc->name, "");
strcat(new_arc->name, vs_node_out->name);
strcat(new_arc->name, "->");
strcat(new_arc->name, vs_node_inp->name);
if (current_arc)
while (current_arc->next!= NULL)
current_arc = current_arc->next;
if (current_arc)
current_arc->next = new_arc;
new_arc->prev = current_arc;
current_arc = head_arc;
current_aux_elem_out = vs_node_out->output_pointer->aux_elem_pointer;
if (current_aux_elem_out)
while (current_aux_elem_out->next!= NULL)
current_aux_elem_out = current_aux_elem_out->next;
new_aux_out = (aux_elem_arc *) malloc(sizeof (aux_elem_arc));
new_aux_out->next = NULL;
new_aux_out->arc_pointer = new_arc;
if (current_aux_elem_out)
current_aux_elem_out->next = new_aux_out;
current_aux_elem_inp = vs_node_inp->input_pointer->aux_elem_pointer;
if (current_aux_elem_inp)
while (current_aux_elem_inp->next!= NULL)
current_aux_elem_inp = current_aux_elem_inp->next;
new_aux_inp = (aux_elem_arc *) malloc(sizeof (aux_elem_arc));
new_aux_inp->next = NULL;
new_aux_inp->arc_pointer = new_arc;
if (current_aux_elem_inp)
current_aux_elem_inp->next = new_aux_inp;
new_arc->aux_elem_input_pointer = inp_for_arc;
new_arc->aux_elem_output_pointer = out_for_arc;
new_arc->aux_elem_input_pointer->input_pointer = vs_node_inp->input_pointer;
new_arc->aux_elem_output_pointer->output_pointer = vs_node_out->output_pointer;
new_arc = (arc *) malloc(sizeof (arc));
new_arc->prev = NULL;
new_arc->next = NULL;
inp_for_arc = (aux_elem_input *) malloc(sizeof (aux_elem_input));
inp_for_arc->input_pointer = NULL;
inp_for_arc->next = NULL;
out_for_arc = (aux_elem_output *) malloc(sizeof (aux_elem_output));
out_for_arc->output_pointer = NULL;
out_for_arc->next = NULL;
strcpy(new_arc->name, "");
strcat(new_arc->name, vs_node_inp->name);
strcat(new_arc->name, "->");
strcat(new_arc->name, vs_node_out->name);
if (current_arc)
while (current_arc->next!= NULL)
current_arc = current_arc->next;
if (current_arc)
current_arc->next = new_arc;
new_arc->prev = current_arc;
current_arc = head_arc;
new_aux_inp = (aux_elem_arc *) malloc(sizeof (aux_elem_arc));
new_aux_inp->next = NULL;
new_aux_inp->arc_pointer = new_arc;
vs_node_out->input_pointer->aux_elem_pointer = new_aux_inp;
new_aux_out = (aux_elem_arc *) malloc(sizeof (aux_elem_arc));
new_aux_out->next = NULL;
new_aux_out->arc_pointer = new_arc;
vs_node_inp->output_pointer->aux_elem_pointer = new_aux_out;
new_arc->aux_elem_input_pointer = inp_for_arc;
new_arc->aux_elem_output_pointer = out_for_arc;
new_arc->aux_elem_input_pointer->input_pointer = vs_node_out->input_pointer;
new_arc->aux_elem_output_pointer->output_pointer = vs_node_inp->output_pointer;
if (first_time == 1) {
new_node_list = vs_node_inp;
work_new_node_list = vs_node_out;
first_time += 1;
} else {
work_new_node_list->next = vs_node_inp;
vs_node_inp->prev = work_new_node_list;
while (work_new_node_list->next!= NULL)
work_new_node_list = work_new_node_list->next;
}
current_node = current_node->next;
}
long result = -1;
long global_result = 1000;
long ways_number = 0;
long way_free = 1;
long prv;
long enffl_finded = 0;
// Эта штука тоже вызывает опасения.
// memset(a, 0, sizeof(a));
long used[1000];
memset(used, 0, sizeof(used));
long checked[100][100];
memset(checked, 0, sizeof(checked));
long prev[100];
memset(prev, 0, sizeof(prev));
node *source, *effluent;
output *current_output;
aux_elem_arc *aux_pointer = NULL;
source = new_node_list->next;
if (source->next)
if (source->next->next)
effluent = source->next->next->next;
queue *que;
que = (queue *) malloc(sizeof (queue));
init_que(que);
while (source) {
while (effluent) {
while (way_free == 1) {
init_que(que);
push_front(que, source);
used[source->uid] = 1;
enffl_finded = 0;
while (enffl_finded == 0 && que->tail!= NULL) {
current_node = pop_back(que);
if (current_node)
if (current_node->output_pointer)
if (current_node->output_pointer->aux_elem_pointer)
if (current_node->output_pointer->aux_elem_pointer)
aux_pointer = current_node->output_pointer->aux_elem_pointer;
while (aux_pointer!= NULL) {
if (aux_pointer->arc_pointer->aux_elem_input_pointer)
if (used[aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] == 0)
if (checked[current_node->uid][aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] == 0) {
used[aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] = 1;
prev[aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] = current_node->uid;
if (aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer == effluent)
enffl_finded = 1;
push_front(que, aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer);
}
aux_pointer = aux_pointer->next;
}
}
if (enffl_finded == 1) {
prv = effluent->uid;
if (source->uid)
while (prv!= source->uid) {
checked[prv][prev[prv]] = 1;
checked[prev[prv]][prv] = 1;
prv = prev[prv];
}
current_output = source->output_pointer;
way_free = 0;
while (current_output!= NULL) {
if (current_output->aux_elem_pointer) {
aux_pointer = current_output->aux_elem_pointer;
while (aux_pointer) {
if (aux_pointer->arc_pointer->aux_elem_input_pointer)
if (checked[source->uid]
[aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] == 0)
way_free = 1;
aux_pointer = aux_pointer->next;
}
}
current_output = current_output->next;
}
ways_number += 1;
if (ways_number >= result)
result = ways_number;
} else
way_free = 0;
init_que(que);
memset(used, 0, sizeof (used));
memset(prev, 0, sizeof (prev));
}
if (result <= global_result)
global_result = result;
memset(checked, 0, sizeof (checked));
ways_number = 0;
result = -1;
way_free = 1;
enffl_finded = 0;
if (effluent->next)
effluent = effluent->next->next;
}
if (source->next)
source = source->next->next;
else
source = NULL;
if (source)
if (source->next)
if (source->next->next)
effluent = source->next->next->next;
}
if (g->number_of_nodes == 2)
global_result = 1;
free(graph_copy);
return global_result;
}
#endif /* CHECK_GRAPH_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) {
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 |
