Hello,
I'm new to C++ and in my current project I need a general Graph data structure. I can't seem to find any useful information online on how to use them. Is there some library that contains an implementation?
Printable View
Hello,
I'm new to C++ and in my current project I need a general Graph data structure. I can't seem to find any useful information online on how to use them. Is there some library that contains an implementation?
Hi,Quote:
Originally Posted by eur0dad
Why not just use a linked list of points in the graph? (or an STL vector). This is general, and is much more space-efficient than actually storing the value of each pixel in the graph itself.
e.g.
Then e.g. if you have a Windows Device Context, DC, with a white background, then you can do things like:Code:struct TPoint {double x, y;};
typedef vector<TPoint> TGraph;
Other OS's will have something similar.Code:register int i;
for (i = 0; i < Graph.size(); i++)
{
SetPixel(DC, Graph[i].x, Graph[i].y, RGB(0,0,0));
}
I meant this kind of graph:Quote:
Originally Posted by kidburla
http://www-h.eng.cam.ac.uk/help/tpl/...hs.html#Graphs
A tree is a special case of the more general graph (or net). Graphs have many uses from network analysis to spreadsheet operation. Graphs have vertices (or nodes) and edges (which can be one-way or undirected). Edges can have a cost associated with them, and the cost may depend on the direction taken along the edge. Popular graph-related puzzles include
* Finding whether one can traverse all edges without traversing any twice (an Euler Path).
* The Travelling Salesman Problem - how to visit all the nodes at a minimal cost
* Finding the shortest (least cost) path between 2 vertices
* Finding the "minimal spanning tree" - finding a tree (with the least-cost edges) that includes all nodes
More formally, a graph is a pair (V,E), where V is a finite set and E is a binary relation on V. V is called a vertex set whose elements are called vertices. E is a collection of edges, where an edge is a pair (u,v) with u,v in V. In a directed graph, edges are ordered pairs, connecting a source vertex to a target vertex. In an undirected graph edges are unordered pairs and connect the two vertices in both directions, hence in an undirected graph (u,v) and (v,u) are two ways of writing the same edge.
If some edge (u,v) is in graph , then vertex v is adjacent to vertex u. In a directed graph, edge (u,v) is an out-edge of vertex u and an in-edge of vertex v. In an undirected graph edge (u,v) is incident on vertices u and v. In a directed graph, the number of out-edges of a vertex is its out-degree and the number of in-edges is its in-degree. For an undirected graph, the number of edges incident to a vertex is its degree.
A path is a sequence of edges in a graph such that the target vertex of each edge is the source vertex of the next edge in the sequence. If there is a path starting at vertex u and ending at vertex v we say that v is reachable from u. A path is simple if none of the vertices in the sequence are repeated. A path is a cycle if the first and last vertex in the path are the same. A graph with no cycles is acyclic.
The boost graph library might have code to help you with what you are looking for.
Create a node class. Each node has an adjacency list containing nodes that it links to.