Не нарушает ли создание пользовательской структуры данных графа какие-либо принципы? - PullRequest
Новая
       17

Не нарушает ли создание пользовательской структуры данных графа какие-либо принципы?

0 голосов
/ 03 мая 2011

Я работаю над небольшим научным проектом, связанным с тестированием цепей с использованием непрерывных методов.Программа будет анализировать файлы определений схем и затем создавать легко модифицируемую структуру графа, представляющую схему. После этого в этот граф вносятся определенные изменения, и он сортируется топологически.После сортировки граф преобразуется в статическую структуру, которая состоит из списка массивов, где каждый массив соответствует определенной степени топологической сортировки.После этого можно легко смоделировать схему, поскольку вы можете положиться на порядок сортировки и последовательно обработать модель.

Теперь это все хорошо и логично, но два упомянутых мною графика представляют собой пользовательские структуры данных, которые:

1) Не построены полностью в соответствии со спецификациями STL (в любом случае, это было бы для меня длинным и сложным - графики намного сложнее, чем векторы и списки)

2) Для второго графика япредположим, что это нельзя изменить, и используйте вектор векторов или список векторов для скорости.

3) Набор операций, доступных для моих графиков, ограничен и отражает потребности моего проекта.

4) Код прост.

Теперь я учусь на третьем курсе по ИТ, и после прохождения курса по разработке программного обеспечения и после прочтения некоторого реального кода, мне интересно:

1) Может (или даже может) код быть таким простым?

2) Не нарушаю ли я ни один из тысяч принципов разработки программного обеспечения, делая предположения оданныеструктуры?

3) Должен ли я действительно всегда соответствовать спецификациям STL для всех структур данных, которые я создаю в этом и будущих проектах?

Этот проект использует C ++.

Спасибо за внимание!Буду признателен за фундаментальный и теоретический ответ на эти вопросы, а также за пример практического подхода к этой проблеме.

Ответы [ 2 ]

5 голосов
/ 03 мая 2011

1) Может ли (или даже может) код быть таким простым?

Мало того, что это может быть, это должно быть. Нет необходимости, чтобы код был сложным.

2) Разве я не нарушаю ни один из тысяч принципов разработки программного обеспечения, делая предположения о структурах данных?

Хм, как вы можете поступить иначе? Этот вопрос не имеет смысла для меня.

3) Должен ли я действительно всегда соответствовать спецификациям STL для всех структур данных, которые я создаю в этом и будущих проектах?

Неа. Например, если вам не нужно повторять структуру, не предоставляйте итераторы. Реализуйте только то, что вам действительно нужно.

1 голос
/ 03 мая 2011

Я не вижу ничего плохого в таком простом дизайне, как этот: 

typedef int node_type; // or a more complex type here
typedef std::list<node_type> node_list;
typedef std::pair<node_list::const_iterator, node_list::const_iterator> edge_type;
typedef std::list<edge_type> edge_list;

struct graph
{
    node_list nodes;
    edge_list edges;

    // Some member functions for doing specific things here
    // for instance:
    void remove_node(node_list::iterator i)
    {
        nodes.erase(i);
        edges.remove_if(connects(i));
    }
};

, где 

struct connects
{
    connects(node_list::const_iterator i) : i(i) {}

    bool operator()(const edge_type& e) const
    {
        return e.first == i || e.second == i;
    }

private:
    node_list::const_iterator i;
};

Он остается простым, модульным и позволяет использовать на нем стандартную библиотеку. Это позволяет вам перебирать узлы и ребра. Если вам нужен список смежности вершин, вам придется перебрать весь список ребер, но это сделано специально (вам нужна лучшая структура, если вы хотите сделать это быстро).

Например, определить (это, к сожалению, не является стандартным) 

template <typename I, typename F, typename G>
F for_each_if(I first, I last, F f, G pred)
{
    for ( ; first!=last; ++first ) if (pred(*first)) f(*first);
    return f;
}

и теперь вы можете сделать 

for_each_if(g.edges.begin(), g.edges.end(), something, connects(some_node));

для перебора списка смежности some_node.

В C ++ 0x есть более элегантные способы кодирования таких алгоритмов (с использованием лямбд).

...