Форум программистов, компьютерный форум CyberForum.ru

Эйлеров путь - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
10.12.2013, 23:08     Эйлеров путь #1
Я примерно написал програму, но мой вариант работает долго - 28(иногда меньше, иногда больше) минут.Подскажите пожалуйста есть ли какой-то более быстрый вариант. У меня есть только 5 минут каждый раз.
Мой заключается в следующем - берем одну из 10000 вершин ну и начинаем искать, подходит-добавили-опять ищем-нашли-добавали ну и если ничего не осталось то вывели.
Но работает долго.
К сожалению графы и алгоритмы на них еще не изучал - подскажите пожалуйста какой-либо алгоритм который будет быстрее. Можно не пример, а типа блок-схемы

Добавлено через 22 минуты
C другой стороны при использовании 3 i7 и 1 i3 расписав точки начала проверок как 0, 2500, 5000, 7500 можно конечно упеть за 3-4 минуты в среднем, но я верю что есть более цивилизованные пути решения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 23:08     Эйлеров путь
Посмотрите здесь:

C++ Путь
Путь до файла C++
C++ Путь к файлу
C++ Путь к процессам
C++ Эйлеров цикл
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
10.12.2013, 23:11     Эйлеров путь #2
В качестве начальной и конечной вершины можно рассматривать только вершины нечетных степеней. Их должно быть ровно 2, иначе эйлерова пути (не замкнутого) нет.
Если все вершины имеют четную степень, то имеется (обязательно!) эйлеров цикл (замкнутый путь). И тогда без разницы с какой из вершин начинать..
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
10.12.2013, 23:20  [ТС]     Эйлеров путь #3
Тут, к сожалению, не так я задал вопрос.
Те изначально известно что нечетных вершин 2 - не ноль - то есть не цикл, а именно путь - но на входе у меня 10000 строк и как определить нечетную я не пойму, хотя пока пишу это уже пару идей пришло.
Спасибо
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 09:47     Эйлеров путь #4
Цитата Сообщение от Aliru Посмотреть сообщение
28(иногда меньше, иногда больше) минут
жесть!
сие творение ищет эйлеров путь за N*logN (можно избавиться от логарифма если set заменить на что-нибудь на хешах, например unordered_map):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <set>
#include <stack>
using namespace std;
 
const int N = 10001;
 
set< int > adj[ N ]; // граф на списках смежности
stack< int > st;
 
void insert_edge( int v, int w )
{
    adj[ v ].insert( w );
    adj[ w ].insert( v );
}
 
void remove_edge( int v, int w )
{
    adj[ v ].erase( w );
    adj[ w ].erase( v );
}
 
int traverse( int v )
{
    for ( set< int >::iterator it; ( it = adj[ v ].begin() ) != adj[ v ].end(); v = *it )
    {
        st.push( v );
        remove_edge( v, *it );
    }
    return v;
}
 
void print_euler( int v )
{
    st.push( v = traverse( v ) );
    while ( !st.empty() )
    {
        printf( "%d ", v = st.top() ); st.pop();
        traverse( v );
    }
}
 
int find_odd_degree()
{
    for ( int v = 0; v < N; ++v )
        if ( adj[ v ].size() & 0x01 )
            return v;
    return -1;
}
 
int main()
{
    for ( int v, w; 1 < scanf( "%d%d", &v, &w ); insert_edge( v, w ) );
    print_euler( find_odd_degree() );
 
    return 0;
}
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:05  [ТС]     Эйлеров путь #5
Сейчас я дописал поиск нечетной вершины.
На входе у меня 260-280Кб строк
такого типа(на самом деле они по-моему по 25 или 30 символов но это не важно)
ATGCG
GCATG
CATGC
AGGCA
GGCAT
Ответ типа такой(отсортирован по алфавиту)
AGGCA -> GGCAT
CATGC -> ATGCG
GCATG -> CATGC
GGCAT -> GCATG
Все одинаковой длины.
Нечетное ребро - это когда первые (размер() -1) символов не повторяются нигде. Четное - когда у одной строки это начало,а у другой конец.
Вот код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// OGP2.0.cpp : Defines the entry point for the console application.
//
 
// Overlap Graph Problem.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include "conio.h"
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <algorithm>
#include <iterator>
#include "vector"
 
using namespace std;
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    list<string> Lines;
    list<string>::iterator it;
    vector <string> lines;
    string s1, s2, example;
    ifstream Fin;
    Fin.open("d:\\dataset_52_7.txt");
    if (!Fin.is_open())
    {
        cout << "Can't open file-d:\\dataset_52_7.txt" << endl;
        exit(EXIT_FAILURE);
    }
    while (Fin.good())
    {
      getline(Fin, s1);
      Lines.push_back(s1);
      s1.clear();
    }
    if (Fin.eof())
        cout << "EOF" << endl;
    else 
        if (Fin.fail())
        cout << "Fuck a duck, HAX!!!" << endl;
    else
        cout << "!!!---!!!" << endl;
    Fin.close();
    //End of input
 
    
    //Lines.sort();
    for ( it = Lines.begin(); it != Lines.end(); it++)
        lines.push_back(*it);
    //sort & send dna to the vector
 
    int count = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        s1 = lines.at(i);
        s1.erase(s1.begin() + s1.size() - 1);
        for (count = 0; count < lines.size(); count++)
        {
            example = lines.at(count);
            example.erase(example.begin());
            if (i != count)
            {
                if (s1 == example)
                    break;
            }
        }
        if (count == lines.size())
        {
            s1 = lines.at(i);
            break;
        }
    }
    //cout << s1;
    ofstream f_out("d:\\Result.txt", ios::app);
        if (!f_out) 
            {
                cout<<"Файл Result.txt невозможно открыть";
                exit(EXIT_FAILURE);
            }
        f_out << s1;
    while (lines.size() != 0)
    {
        example = s1;
        example.erase(example.begin());
        for (unsigned int i = 1; i < lines.size(); i++)
        {
            for (unsigned int j = 0; j < (s1.size() - 1); j++)
            {
                if (example.at(j) == lines.at(i).at(j))
                {
                    count++;
                }
            }
            if (count == example.size())
            {
                //f_out << s1 << " -> " << lines.at(i) << endl;
                //cout << s1 << " -> " << lines.at(i) << endl;
                s1.clear();
                s1 = lines.at(i);
                lines.erase(lines.begin() + i);
                break;
            }
            count = 0;
        }
        cout << lines.size();
        example.clear();
    }
    f_out.close();
    _getch();
    return 0;
}
Доходит до 4500 и потом не находит продолжения.
В чем может быть проблема?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:10     Эйлеров путь #6
Цитата Сообщение от Aliru Посмотреть сообщение
ATGCG
GCATG
CATGC
AGGCA
GGCAT
можете поведать смысл этих строк
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:10  [ТС]     Эйлеров путь #7
Ну это ДНК, вернее ее куски нарезанные по н штук
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:18     Эйлеров путь #8
а как из этих строк строится граф? что является узлом? буквы или что? и как определяются ребра? соседние буквы образуют ребро или что? можете поподробнее объяснить
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:34  [ТС]     Эйлеров путь #9
Пусть длина строки н
(н-1) последних символов одной сторки это (н-1) первых символов другой строки.
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина. Есть еще одна но у нее последнии н-1 символов не повторяются.
2 нееных вершины - значит это эйлеров путь
И так мы выстраиваем этот путь - ну типа
AACACTT->ACACTTG
CACTTGT->ACTTGTA
CTTGTAA->TTGTAAG
Ну вот так

Добавлено через 6 минут
Извиняюсь точнее так
AACACTT->ACACTTG
ACACTTG->CACTTGT
CACTTGT->ACTTGTA
ACTTGTA->CTTGTAA
CTTGTAA->TTGTAAG
Исправил
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:35     Эйлеров путь #10
я вас правильно понял: вам надо по кускам восстановить полную цепочку? и
Цитата Сообщение от Aliru Посмотреть сообщение
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина.
нечетная - значит начальная, а это
Цитата Сообщение от Aliru Посмотреть сообщение
Есть еще одна но у нее последнии н-1 символов не повторяются.
значит конечная вершина?
если так, то при чём здесь эйлеров путь, никак не уловлю?
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:38  [ТС]     Эйлеров путь #11
да, но я думал это граф. я их еще не учил, но...
а о чем тогда задача, натолкнте на алгоритм пожалуйста
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:29     Эйлеров путь #12
продолжаем разговор
Цитата Сообщение от ya_noob Посмотреть сообщение
я вас правильно понял: вам надо по кускам восстановить полную цепочку?
я не услышал ответа. да или нет?
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 12:32  [ТС]     Эйлеров путь #13
Да.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:48     Эйлеров путь #14
хорошо. мне сложно запомнить ATGC, так что давайте далее будем говорить про ABCD.
итак, может ли во входных данных встретиться такое

AABC
ABCD
BCDD
CDDB
ABCD
BCDB
CDBA
DBAB
BABC
? попробуйте нарисовать эту цепочку
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 17:58  [ТС]     Эйлеров путь #15
ТУТ есть AABC->ABCD->BCDD->CDDB и ABCD->BCDB->CDBA->DBAB->BABC
а у меня будет типа
Вход:
BCDD
DDBB
BBAB
DBBA
CDDB
AABC
ADCD
Выход
AABC->ABCD->BCDD->CDDB->DDBB->DBBA->BBAB
то есть AABC это начало так как комбинация AAB больше нигде не встеекается как последние 3 символа(н-1),
а вот ВСD - это начало BCDD И конец ABCD
я вот опять день думал периодически впринципе то мой код должен работать - но он доходит до 6311 отрезков и больше не находит
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 19:52     Эйлеров путь #16
Цитата Сообщение от Aliru Посмотреть сообщение
ТУТ есть AABC->ABCD->BCDD->CDDB и ABCD->BCDB->CDBA->DBAB->BABC
а я изначально имел ввиду такую последовательность (всего одну):
AABC->ABCD->BCDB->CDBA->DBAB->BABC->ABCD->BCDD->CDDB
сможет ли ваша программа найти эту последовательность?

и еще вдогонку вопрос. может ли быть на входе такая последовательность (начало первого куска совпадает с концом последнего):
AABC->ABCD->BCDB->CDBA->DBAB->BABC->ABCD->BCDA->CDAA->DAAB ?

Добавлено через 4 минуты
или такая (конец уникальный, а начало AAB встречается в куске DAAB):
AABC->ABCD->BCDA->CDAA->DAAB->AABD->ABDC ?
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
12.12.2013, 03:31  [ТС]     Эйлеров путь #17
да протупил, делал на глаз
сейчас проверю
варианты 2 и 3 не должны быть

Добавлено через 6 часов 26 минут
Вообщем что-то понял, что-то надо читать-понимать
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.12.2013, 08:03     Эйлеров путь #18
Цитата Сообщение от Aliru Посмотреть сообщение
Overlap Graph Problem.cpp
я понял что вам надо. а надо вам по исходным строкам найти все их пары такие, что префикс одной строки равен суффиксу другой, т.е. построить списки смежности для строк. только и всего.
у меня были сомнения насчет того, что надо восстановить всю цепочку (хотя вы и ответили "да"), т.к. способов восстановления может быть очень много.
вот вам ссыль на решение вашей задачи: http://bioalgo.blogspot.ru/2013/01/o...sic-graph.html
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2013, 11:27     Эйлеров путь
Еще ссылки по теме:

путь фишки C++
Путь символа C++
G++.exe путь к *.h C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
12.12.2013, 11:27  [ТС]     Эйлеров путь #19
Самое интересное что я вчера ночью я наконец то понял что надо сделать и решил ее. Зато много нового узнал. Вам огромное спасибо за труды.
Подскажите пожалуйста такой еще вопрос. Есть входные данные:
0 -> 2
1 -> 3
2 -> 1
3 -> 0,4
6 -> 3,7
7 -> 8
8 -> 9
9 -> 6
Из них необходимо построить Эйлеров цикл:
6->8->7->9->6->5->4->2->1->0->3->2->6
Но я не могу понять как считывать входящие данные.
Строками?А потом отделять их и записывать по массивам?
Yandex
Объявления
12.12.2013, 11:27     Эйлеров путь
Ответ Создать тему
Опции темы

Текущее время: 00:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru