C++

Forum

 
Graphs

helios (17574)
How do you do general graph structures? I.e. those where any node in the structure can point to any number of nodes in the structure without restriction.
The only sane way I've found of managing the memory of such structures is to hold all the objects in a central owning vector and to use weak pointers for the edges.
lastchance (6980)
If the nodes are 0, 1, 2, ... then
1
2
3
4
5
6
7
 
struct Edge
{
   int dest;
   double wt;
};
bool operator < ( Edge a, Edge b ) { return a.dest < b.dest; }
using Graph  = vector< set<Edge> >;



If the nodes have some other type (e.g. char), then
1
2
3
4
5
6
7
8
 
using NodeType = .....
struct Edge
{
   NodeType dest;
   double wt;
};
bool operator < ( Edge a, Edge b ) { return a.dest < b.dest; }
using Graph  = map< NodeType, set<Edge> >;
Last edited on
Duthomhas (13206)
Agreed.

Directed Adjacency Graph, unweighted edges:

1
2
 
#include <unordered_map>
#include <unordered_set> 
1
2
3
4
5
 
template <typename Node>
using Edges = std::unordered_set <Node>;

template <typename Node>
using Graph = std::unordered_map <Node, Edges <Node> >;

Example where I used this very structure:
https://cplusplus.com/forum/lounge/228897/#msg1039365

[edit]
IDK what’s up with the weird formatting...
Last edited on
helios (17574)
But what if the graph may contain duplicate nodes with different connections?
1
2
3
4
5
6
 
auto node1 = graph.add("foo");
auto node2 = graph.add("foo");
auto node3 = graph.add("bar");
node1->connect_to(node2);
node2->connect_to(node1);
node2->connect_to(node3);
jonnin (11437)
if it can duplicate, you use a different container.

a graph..
can be given a set of rules that makes it a tree
which can be reduced with more rules to a binary tree
or a different set of rules can make a linked list

so you CAN make a graph using the textbook design of pointers to self, the key concepts you used to make lists, and trees in school:
1
2
3
4
5
 
struct graph
{
   something data;
   vector<graph*> outgoing_links;
}

where each node can go to N other nodes via the links. The links could have a cost attached to them, you could use a <pair> for that or whatever.

this is woefully inefficient in the long run, of course -- same as how textbook design pointer trees and LL are inefficient -- so after understanding the above "shape" of the data structure, you end up with the suggestions for performance and code simplification reasons. A container that lets you get to any node, or touch each node, saves having to traverse the convoluted and cyclical structures to do a simple search or whatnot, and adjacency lists do the same for traversing it properly if you need that.
Last edited on
Duthomhas (13206)
IMHO, any time you have a graph containing “duplicate nodes” — nodes that cannot be distinguished without traversing the graph — then you have a design problem. Fix that.
dhayden (5798)
1
2
3
4
5
 
template <typename Node>
using Edges = std::unordered_set <Node>;

template <typename Node>
using Graph = std::unordered_map <Node, Edges <Node> >;
Shouldn't Edge be an unordered_set<Node*> instead? Otherwise the Node in an edge is different from the Node in a graph.

I usually do graphs like this:

1
2
3
4
5
6
7
8
9
10
11
12
 
struct Node {
    vector<Edge> edges;
};

struct Edge {
    Node *from, *to;
};

struct Graph {
    vector<Node*> nodes;
    vector<Edge*> edges;
};

The graph itself owns the nodes and edges. Thsi way there's only 1 copy of each node and each edge. Of course you need methods to add notes and edges to the graph. Sometimes it's helpful to have Node and/or Edge contain a reference back to the graph that owns them.


helios (17574)
IMHO, any time you have a graph containing “duplicate nodes” — nodes that cannot be distinguished without traversing the graph — then you have a design problem.
Would you mind expanding on that? I can think of reasons why you could have a graph where two nodes are identical but in different places in the topology. One reason might be that they're mutable and can sometimes end up in the same states. Restricting the set of valid graphs to only those that have unique nodes seems arbitrary to me. It seems equivalent to saying that a linked list should never have duplicate elements.
Last edited on
Duthomhas (13206)
Ah, I see. We seem to be mixing up the node with the node’s value.
Last edited on
Cubbi (4774)
How do you do general graph structures?
I just use boost.graph until/unless there's a need to roll something special
helios (17574)
So, earlier when you said that a graph that contains duplicate nodes suggests there's a design problem, did you mean something like this?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class Node{
public:
    int id;
    std::vector<int> connections;
};

class Graph{
public:
    std::vector<Node> nodes;
};

Node a{0};
Node b{1};
Node c{1};
Node d{2};
Graph g;

a.connections.push_back(1);
b.connections.push_back(0);
c.connections.push_back(2);
g.nodes.push_back(a);
g.nodes.push_back(b);
g.nodes.push_back(c);
g.nodes.push_back(d);
That would certainly cause problems.
Last edited on
lastchance (6980)
a.connections.push_back(1);


Surely that is trying to connect to the DATA at the node (and is ambiguous here), not the node itself?
Last edited on
helios (17574)
The elements of Node::connections reference a Node by its Node::id, therefore the structure above would not be a well-formed graph.
Duthomhas (13206)
Yes, in my Graph structure, Node might have better named "NodeId".
Topic archived. No new replies allowed.