1

In my application I have some kind of graph where every node/vertex can be connected to each other but actual connection is determined at runtime.

Of course this is trivial to implement by iterating over all existing vertices and connecting them to the last one I've added to the graph and using a filtered graph at runtime to decide of the connection still persists.

Purpose is to use BFS or DFS or other algorithms provided by BGL.

Is there any other approach to get that task done more efficiently? By example: Adding all(!) vertices at initialization and having some kind of callback which checks for an edge at runtime?

That's what how I tried to solve it but that one doesn't work:

#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>
struct VD { };
struct ED { };

struct Graph : boost::adjacency_matrix<boost::directedS, VD, ED>
{
    Graph() : boost::adjacency_matrix<boost::directedS, VD, ED>(4) { }
    //=================================================================
    // Functions required by the AdjacencyMatrix concept
    template <typename D, typename VP, typename EP, typename GP, typename A>
    std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
    edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
        typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
        const adjacency_matrix<D,VP,EP,GP,A>& g)
    {
        // Connect vertex 1 and 2
        bool exists = (u == 1 && v == 2);

        typename boost::adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
            e(exists, u, v, boost::detail::get_edge_property(g.get_edge(u,v)));

        return std::make_pair(e, exists);
    }
};

int main() {
    Graph g;
    print_graph(g);

    std::vector<int> component(num_vertices(g));
    int num = boost::connected_components(g, &component[0]);
}

Any pointers would be appreciated!

fhw72
  • 1,066
  • 1
  • 11
  • 19
  • Why do you want to create all edges with some kind of additional metadata to make them appear or disappear, instead of simply creating only the edges that actually exist? – Quentin Jul 10 '19 at 12:27
  • It's simple the edges can "appear" or "disappear" depending on the data contained in the vertices at runtime. – fhw72 Jul 11 '19 at 06:26
  • @fhw72 Oh, that's simpler. Look at some of my [answers containing filtered_graph](https://stackoverflow.com/search?tab=relevance&q=user%3a85371%20filtered_graph). That should give you some ideas – sehe Jul 11 '19 at 09:45
  • Yes... but that's what I mean by: Constructing the graph that way that every time I add a new vertex I also add edges to all previous vertices and that new one and then use the filtered graph approach. I wanted to see if there's a better (more efficient) approach to that. – fhw72 Jul 11 '19 at 11:40

1 Answers1

0

From BGL concepts:

The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the parlance of generic programming), that define how a graph can be examined and manipulated in a data-structure neutral fashion. In fact, the BGL interface need not even be implemented using a data-structure, as for some problems it is easier or more efficient to define a graph implicitly based on some functions.

There's no standard model implementation, but the docs contain an example in Chapter 19: Graph Adaptors

It shows the grid_graph adaptor, which might match your use case pretty closely. If not, it should give you good ideas about how to create implicit graph models according to the concept requirements.

[2]:

sehe
  • 374,641
  • 47
  • 450
  • 633
  • I'm confused because my use case is more like a 2-dimensional matrix. Do you have an example which is more descriptive than the examples from the book? (Which I wouldn't even call examples in some cases... but that's another story). What I'm trying to achieve is having some callback which gets the two bundled vertices and returns if there's a connection (i.e. edge) between them. – fhw72 Jul 11 '19 at 06:48
  • What I just found: Some kind of dynamic Adjacency matrix is more or less what I need... but documentation states: "No Boost Graph Library algorithms currently use this concept.". In other words I'm unsure if I can achieve what I want with BGL (easily). – fhw72 Jul 11 '19 at 08:50
  • @fhw72 I've [written about that model/concept before](https://stackoverflow.com/a/48613020/85371). I cannot assess whether you indeed need it. (Sidenote: Floyd-Warshall Shortest Paths is in the library now, and it uses a DistanceMatrix representation instead?) – sehe Jul 11 '19 at 09:43
  • Ok. I see... adjacency_matrix checks for an actual connection via "edge" function in AdjacencyMatrix concept. Do you see a possibility to overwrite that specific function? I don't want to copy&paste the adjacency_matrix copy just in order to modify this single function. – fhw72 Jul 11 '19 at 11:42
  • I refined my question in order to better explain what I try to do. – fhw72 Jul 11 '19 at 11:52
  • @fhw72 In general you can "just" implement the concept requirements on whatever data structure you prefer/have. If you adhere to the performance constraints, then you are also guaranteed to get the performance characteristics of the algorithms invoked. See e.g. here where I show how to rig up the entire model hierarchy from scratch just reading through concept requirements: https://stackoverflow.com/questions/56193619/what-is-needed-to-use-bgl-algorithms-on-existing-data-structures-edges-and-ver/56203763#56203763 – sehe Jul 12 '19 at 09:20
  • Thanks. I just refined the question again... at least it compiles but doesn't work. – fhw72 Jul 12 '19 at 09:27