Thread: How to use C++ graphs?

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    2

    How to use C++ graphs?

    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?

  2. #2
    Registered User
    Join Date
    Oct 2005
    Posts
    43
    Quote Originally Posted by eur0dad
    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,

    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.

    Code:
    struct TPoint {double x, y;};
    typedef vector<TPoint> TGraph;
    Then e.g. if you have a Windows Device Context, DC, with a white background, then you can do things like:
    Code:
    register int i;
    for (i = 0; i < Graph.size(); i++)
    {
     SetPixel(DC, Graph[i].x, Graph[i].y, RGB(0,0,0));
    }
    Other OS's will have something similar.
    Last edited by kidburla; 10-14-2006 at 07:59 AM. Reason: forgot ()
    Windows XP Professional SP2, Code::Blocks Studio 1.0rc2, GCC/G++ 3.4.2 (20040916-1), mingw32-make 3.80.0-3, GDB 5.2.1-1, W32API 3.6

    MingW Runtime 3.9, BinUitls 2.15.91 (20040904-1), MingW Utilities 0.3, Tcl/Tk 8.4.1-1

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    2
    Quote Originally Posted by kidburla
    Hi,

    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.

    Code:
    struct TPoint {double x, y;};
    typedef vector<TPoint> TGraph;
    Then e.g. if you have a Windows Device Context, DC, with a white background, then you can do things like:
    Code:
    register int i;
    for (i = 0; i < Graph.size(); i++)
    {
     SetPixel(DC, Graph[i].x, Graph[i].y, RGB(0,0,0));
    }
    Other OS's will have something similar.
    I meant this kind of graph:

    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.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    The boost graph library might have code to help you with what you are looking for.

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Create a node class. Each node has an adjacency list containing nodes that it links to.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graphs and the STL
    By smitsky in forum C++ Programming
    Replies: 1
    Last Post: 12-04-2004, 06:32 PM
  2. graphs and algorithms
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2004, 01:13 PM
  3. Generate Graphs
    By beet in forum C Programming
    Replies: 6
    Last Post: 08-19-2003, 07:14 PM
  4. graphs
    By cmpcnic1@livjm. in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2003, 07:06 AM
  5. graphs
    By res025ol in forum C++ Programming
    Replies: 0
    Last Post: 03-28-2002, 08:31 PM