node *current_node;
push_front(que, start_node);
used[start_node->uid] = 1;
cursor = que->tail;
while (que->tail) {
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 (aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer)
if (aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer)
if (used[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;
push_front(que, aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer);
}
aux_pointer = aux_pointer->next;
}
}
for (int i = 0; i < used_counter; i++)
if (used[i] == 0) {
result = 0;
break;
}
destroy_que(que);
return result;
}
/*
* Определяет количество компонент связности.
*/
int find_num_conponents(graph *g) {
// Если граф изначально связный, то число компонент равно 1.
int result = 1;
int number_of_components = 0;
int used_counter = g->number_of_nodes;
int used[MAX_ELEM];
memset(used, 0, sizeof (used));
node *cursor;
aux_elem_arc *aux_pointer = NULL;
queue *que;
que = (queue *) malloc(sizeof (queue));
init_que(que);
node *current_node;
for (int i = 0; i < used_counter; i++) {
if (used[i] == 0) {
destroy_que(que);
init_que(que);
current_node = g->node_pointer;
while (current_node->uid!= i)
current_node = current_node->next;
push_front(que, current_node);
used[i] = 1;
cursor = que->tail;
while (que->tail) {
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)
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) //Вершина не посещалась
{
used[aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer->uid] = 1; //Отмечаем её как посещённую
push_front(que, aux_pointer->arc_pointer->aux_elem_input_pointer->input_pointer->node_pointer); //И помещаем в очередь
}
aux_pointer = aux_pointer->next;
}
}
for (int i = 1; i <= used_counter; i++)
//for (int i = 1; i < used_counter; i++)
if (used[i] == 0) {
//result = 0;
number_of_components += 1;
break;
}
}
}
if (number_of_components > 1)
return number_of_components;
else
return result;
}
/*
* Определяет рёберную связность графа.
*/
int find_rib_relations(graph *g) {
int result = -1;
int global_result = ABSOLUTE_MAX;
int ways_number = 0;
int way_free = 1;
int prv;
int enffl_finded = 0;
int used[RIB_SIZE] = {0};
int checked[RIB_SIZE][RIB_SIZE] = {0};
int prev[RIB_SIZE] = {0};
node *source, *effluent;
output *current_output;
source = g->node_pointer;
effluent = source->next;
aux_elem_arc *aux_pointer = NULL;
queue *que;
que = (queue *) malloc(sizeof (queue));
init_que(que);
node *current_node;
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;
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;
effluent = effluent->next;
}
source = source->next;
if (source)
effluent = source->next;
}
return global_result;
}
/*
* Определяет вершинную связность графа.
*/
int find_node_relations(graph* g) {
graph *graph_copy, *work;
node *head, *current_node, *vs_node_inp, *vs_node_out, *new_node_list, *work_new_node_list;
arc *new_arc, *head_arc, *current_arc;
aux_elem_arc *current_aux_elem_out, *new_aux_out;
aux_elem_arc *current_aux_elem_inp, *new_aux_inp;
aux_elem_input *inp_for_arc;
aux_elem_output *out_for_arc;
input *new_input;
output *new_output;
// work - это исходный граф.
work = g;
// graph_copy - копия исходного графа. Которую преобразуем.
graph_copy = copy_graph(work);
int first_time = 1;
int uid_index = 0;
head = graph_copy->node_pointer;
head_arc = graph_copy->arc_pointer;
current_node = head;
current_arc = head_arc;
while (current_node!= NULL) {
vs_node_inp = (node *) malloc(sizeof (node));
vs_node_out = (node *) malloc(sizeof (node));
vs_node_inp->prev = NULL;
vs_node_inp->next = vs_node_out;
vs_node_out->prev = vs_node_inp;
vs_node_out->next = NULL;
strcpy(vs_node_inp->name, "");
strcat(vs_node_inp->name, current_node->name);
strcat(vs_node_inp->name, current_node->input_pointer->name);
strcat(vs_node_inp->name, "1");
strcpy(vs_node_out->name, "");
strcat(vs_node_out->name, current_node->name);
strcat(vs_node_out->name, current_node->output_pointer->name);
strcat(vs_node_out->name, "2");
vs_node_inp->number_of_inputs = current_node->number_of_inputs;
vs_node_inp->number_of_outputs = 1;
vs_node_out->number_of_outputs = current_node->number_of_outputs;
vs_node_out->number_of_inputs = 1;
new_input = (input *) malloc(sizeof (input));
new_input->node_pointer = vs_node_out;
strcpy(new_input->name, "");
strcat(new_input->name, "inp");
strcat(new_input->name, vs_node_out->name);
vs_node_out->input_pointer = new_input;
new_output = (output *) malloc(sizeof (output));
new_output->node_pointer = vs_node_inp;
strcpy(new_output->name, "");
strcat(new_output->name, "out");
strcat(new_output->name, vs_node_inp->name);
vs_node_inp->output_pointer = new_output;
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 |
