Алгоритм выбора всех ребер и вершин, связанных с одной вершиной

Question

Я использую Boost Graph, чтобы попытаться понять некоторые графики зависимостей, сгенерированные мной в формате Graphviz Dot.

К сожалению, я не очень разбираюсь в теории графов, поэтому мне сложно сформулировать то, что я хочу знать в терминах теории графов.

Из ориентированного графа зависимостей с ~ 150 вершинами я бы хотел "увеличить" одну конкретную вершину V и построить подграф, содержащий V, все его входящие ребра и их входящие ребра, все его исходящие ребра и их исходящие ребра, вроде как самый длинный путь через V.

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

Например, дано;

     g
     |
     v
a -> b -> c -> d
|    |         |
v    v         |
e    f <-------+

если бы мне пришлось запустить алгоритм на c, я думаю, что хочу;

     g
     |
     v
a -> b -> c -> d -> f

Не уверен, следует ли включать b -> f также ... Я думаю, что все вершины "до" c должны иметь свои ребра включенными, а все вершины "после" c должны иметь свои ребра включен, но мне кажется, что это потеряло бы некоторую информацию.

Такое чувство, что должен существовать алгоритм, который делает это (или что-то более разумное, не уверен, что я пытаюсь сделать что-то глупое, см. B-> f выше), но я не уверен, с чего начать ,

Спасибо!

Answer 1

Хорошо, я переведу и адаптирую свой учебник к вашему конкретному вопросу.Документация всегда предполагает тонны «использования пространства имен»;Я не буду использовать, чтобы вы знали, что к чему.Давайте начнем:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

Сначала определите вершину и ребро:

struct Vertex{
    string name; // or whatever, maybe nothing
};
struct Edge{
    // nothing, probably. Or a weight, a distance, a direction, ...
};

Создайте тип или свой график:

typedef boost::adjacency_list<  // adjacency_list is a template depending on :
    boost::listS,               //  The container used for egdes : here, std::list.
    boost::vecS,                //  The container used for vertices: here, std::vector.
    boost::directedS,           //  directed or undirected edges ?.
    Vertex,                     //  The type that describes a Vertex.
    Edge                        //  The type that describes an Edge
> MyGraph;

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

typedef MyGraph::vertex_descriptor VertexID;
typedef MyGraph::edge_descriptor   EdgeID;

Создание экземпляра вашего графика:

MyGraph graph;

Считывание данных Graphviz и подача графика:

for (each Vertex V){
    VertexID vID = boost::add_vertex(graph); // vID is the index of a new Vertex
    graph[vID].name = whatever;
}

Обратите внимание, что graph[ a VertexID ] дает вершину, а graph[ an EdgeID ] дает преимущество.Вот как добавить один:

EdgeID edge;
bool ok;
boost::tie(edge, ok) = boost::add_edge(u,v, graphe); // boost::add_edge gives a std::pair<EdgeID,bool>. It's complicated to write, so boost::tie does it for us. 
if (ok)  // make sure there wasn't any error (duplicates, maybe)
    graph[edge].member = whatever you know about this edge

Итак, теперь у вас есть график.Вы хотите получить VertexID для Vertex "c".Для простоты давайте воспользуемся линейным поиском:

MyGraph::vertex_iterator vertexIt, vertexEnd;
boost::tie(vertexIt, vertexEnd) = vertices(graph);
for (; vertexIt != vertexEnd; ++vertexIt){
    VertexID vertexID = *vertexIt; // dereference vertexIt, get the ID
    Vertex & vertex = graph[vertexID];
    if (vertex.name == std::string("c")){} // Gotcha
}

И, наконец, чтобы получить соседей вершины:

MyGraph::adjacency_iterator neighbourIt, neighbourEnd;
boost::tie(neighbourIt, neighbourEnd) = adjacent_vertices( vertexIdOfc, graph );
for(){you got it I guess}

Вы также можете получить ребра с помощью

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u, const adjacency_list& g)
std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const adjacency_list& g)
 // don't forget boost::tie !

Итак, для вашего реального вопроса:

• Найти идентификатор вершины "c"
• Рекурсивно найти in_edges
• Рекурсивно найти out_edges

Пример для in_edges (никогда не компилируется и не пробовал, из головы в голову):

void findParents(VertexID vID){
    MyGraph::inv_adjacency_iterator parentIt, ParentEnd;
    boost::tie(parentIt, ParentEnd) = inv_adjacent_vertices(vID, graph);
    for(;parentIt != parentEnd); ++parentIt){
        VertexID parentID = *parentIt;
        Vertex & parent = graph[parentID];
        add_edge_to_graphviz(vID, parentID); // or whatever
        findParents(parentID);
    }
}

Для обратного, просто переименуйте Parent в Children и используйте adjacency_iterator /acent_vertices.

Надеюсь, это поможет.

Answer 2

Вот как это закончилось.Я понял, что мне нужно работать полностью с точки зрения ребер и ребер:

// Graph-related types
typedef property < vertex_name_t, std::string > vertex_p;
typedef adjacency_list < vecS, vecS, bidirectionalS, vertex_p> graph_t;
typedef graph_t::vertex_descriptor vertex_t;
typedef std::set< graph_t::edge_descriptor > edge_set;

// Focussing algorithm
edge_set focus_on_vertex(graph_t& graph, const std::string& focus_vertex_name)
{
    const vertex_t focus_vertex = find_vertex_named(graph, focus_vertex_name);

    edge_set edges;
    collect_in_edges(graph, focus_vertex, edges);
    collect_out_edges(graph, focus_vertex, edges);

    return edges;
}

// Helpers
void collect_in_edges(const graph_t& graph, vertex_t vertex, edge_set& accumulator)
{
    typedef graph_t::in_edge_iterator edge_iterator;

    edge_iterator begin, end;
    boost::tie(begin, end) = in_edges(vertex, graph);
    for (edge_iterator i = begin; i != end; ++i)
    {
        if (accumulator.find(*i) == accumulator.end())
        {
            accumulator.insert(*i);
            collect_in_edges(graph, source(*i, graph), accumulator);
        }
    }
}

void collect_out_edges(const graph_t& graph, vertex_t vertex, edge_set& accumulator)
{
    typedef graph_t::out_edge_iterator edge_iterator;

    edge_iterator begin, end;
    boost::tie(begin, end) = out_edges(vertex, graph);
    for (edge_iterator i = begin; i != end; ++i)
    {
        if (accumulator.find(*i) == accumulator.end())
        {
            accumulator.insert(*i);
            collect_out_edges(graph, target(*i, graph), accumulator);
        }
    }
}

vertex_t find_vertex_named(const graph_t& graph, const std::string& name)
{
    graph_t::vertex_iterator begin, end;
    boost::tie(begin, end) = vertices(graph);
    for (graph_t::vertex_iterator i = begin; i != end; ++i)
    {
        if (get(vertex_name, graph, *i) == name)
            return *i;
    }

    return -1;
}

Это также обрабатывает циклы до или после рассматриваемой вершины.В моем исходном графе зависимостей были циклы (дрожь).

Я предпринял несколько попыток обобщить ребра сбора _ * _ в шаблонный сбор_еджей, но у меня не было достаточно энергии отладки метапрограммирования, чтобы потратить на это.