Search Contact information
University of Cambridge Home Department of Engineering
University of Cambridge >  Engineering Department >  computing help

The cuedgraph CUED graph library

This library can be used from C++ to perform simple tree and graph operations. It's designed with education more than performance foremost in mind.

The main object is a Graph with nodes and edges. Using

    Graph g(binarytree)

restricts the nodes to having no more than 2 children. Default graphs have no restrictions. Graphs have nodes and edges

Several of the routines make use of a Search_Description object to describe options.

class Search_Description
{
public:
  Search_Description() {
    order=preorder;
    searching=depth_first;
    startnode="";
    goalnode="";
    debug=false;
    printnodelabel=false;
  };
  ordering order; 
  search_mode searching;
  string startnode;
  string goalnode;
  bool debug;
  bool printnodelabel;
};
The enumerated types used to set options are
enum direction {directional, nondirectional};
enum ordering {preorder, inorder, postorder};
enum search_mode {breadth_first, depth_first, hill_climbing, best_first, 
     Astar, shortest_paths, min_spanning_tree};
enum minormax {minimaxMIN, minimaxMIN};

Routines

Graph member functions include

Examples

To compile a source file ex1.cc to produce a program called ex1 use
   g++ -oex ex1.cc -lcuedgraph

Example 1

graph The code below creates a graph then finds the minimum distance from node "B" to each of the other nodes.

#include "graphs.h"

string numtostr(float f) {
std::ostringstream o;
   if (o << f)
     return o.str();
   // some sort of error handling goes here...
   return "conversion error";
}

int main()
{
    Graph g;
    Search_Description s;
    vector<string> nodenames;

    s.goalnode="B";
    s.searching=shortest_paths;

    // Set up a graph
    g.addEdge("A","B",7,"AB road",true, nondirectional);
    g.addEdge("A","C",1,"AC road",true, nondirectional);
    g.addEdge("A","D",4,"AD road",true, nondirectional);
    g.addEdge("B","C",7,"BC road",true, nondirectional);
    g.addEdge("B","D",3,"BD road",true, nondirectional);
    g.addEdge("C","D",2,"CD road",true, nondirectional);

    cout << "The graph has " << g.num_vertices() << " vertices. ";
    if (g.cyclecheck()) {
      cout << "It's not a tree - at least one cycle exists. ";
    }
    else
      cout << "It's a tree.";
    cout << endl << endl;
    g.shortestpaths(s.goalnode);
    return 0;
}
Output is
  The graph has 4 vertices. It's not a tree - at least one cycle exists. 
  A is 6 from the source.
  Shortest path is B along BD road to D along CD road to C along AC road to A
  B is 0 from the source.
  Shortest path is B is unreachable
  C is 5 from the source.
  Shortest path is B along BD road to D along CD road to C
  D is 3 from the source.

Example 2

The code below traverses a mathematical expression in various ways. It first creates some nodes, joins them up, and labels them.
             A                             -	     
           /   \		         /   \     
          B     C		        *     *    
         / \   / \		       / \   / \   
        D   E F   G		      2   + 3   -  
           / \   / \		         / \   / \ 
          H   I J   K		        x   5 y   4
#include "graphs.h"
#include <string>
using namespace std;

int main() {
    Graph g(binarytree);

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("B", "E");
g.addEdge("C", "F");
g.addEdge("C", "G");
g.addEdge("E", "H");
g.addEdge("E", "I");
g.addEdge("G", "J");
g.addEdge("G", "K");

g.addnodelabel("A","-");
g.addnodelabel("B","*");
g.addnodelabel("C","*");
g.addnodelabel("D","2");
g.addnodelabel("E","+");
g.addnodelabel("F","3");
g.addnodelabel("G","-");
g.addnodelabel("H","x");
g.addnodelabel("I","5");
g.addnodelabel("J","y");
g.addnodelabel("K","4");

 Search_Description s;
 s.order=postorder;
 s.printnodelabel=true;
 s.startnode="A";
 cout << "Postorder" << endl;
 g.search(s);

 s.order=preorder;
 cout << "Preorder" << endl;
 g.search(s);

 s.order=inorder;
 cout << "Inorder" << endl;
 g.search(s);

}
Output is
Postorder
4
y
-
3
*
5
x
+
2
*
-
Preorder
-
*
-
4
y
3
*
+
5
x
2
Inorder
2
*
x
+
5
-
3
*
y
-
4

Example 3

This solves a game where 2 players take turns at adding an integer from 1 to MAXINCREMENT to a running total, the winner being the one who reaches a particular target number.

The first character of the node name is WHITE or BLACK, indicating whose move it is. The rest of the name is the value of the running total.

#include "graphs.h"
#include <string>
using namespace std;
#define WHITE '1'
#define BLACK '2'

#define MAXINCREMENT 3

int strtonum(string s) {
std::istringstream i(s);
   int x;
   if (i >> x)
     return x;
   // some sort of error handling goes here...
   return 0;
}

string numtostr(int f) {
std::ostringstream o;
   if (o << f)
     return o.str();
   // some sort of error handling goes here...
   return "conversion error";
}

// If target reached, return the winner (WHITE or BLACK) else return 0
int win(string s, int target) {
int t=strtonum(s.substr(1));
  if (t==target)
   return WHITE + BLACK -s[0];
 else
   return 0;
}

Graph g;
void nextgo(string nodename, int target) {
  int winner;
  string newnodename;
  int t=strtonum(nodename.substr(1));   // get current total
  int limit=min(target-t,MAXINCREMENT);

  for(int i=1;i<=limit;i++) {        // play all possible moves
    newnodename=" " + numtostr(t+i);
    newnodename[0]=WHITE + BLACK -nodename[0];
    g.addEdge(nodename,newnodename);
      // give values to terminal modes
      if (winner=win(newnodename,target)) {
        if (winner==BLACK) 
          g.addnodevalue(newnodename,-1);
        else 
	  g.addnodevalue(newnodename,1);
      }
      else {
	g.addnodevalue(newnodename,0);
        nextgo(newnodename, target);
      }    
  }
}

int main( int argc, char *argv[ ] )
{
  float result;
  cout << "Maximum increment=" << MAXINCREMENT << endl;

  for(int i=3;i<=10;i++) {
    g.clearAll();
    nextgo("10",i); // White starts, sum=0 
    cout << "For target=" << i;
    if( (result=g.minimax("10",minimaxMAX)) == -1)
      cout << " player 2 wins" << endl;
    else if (result==1)
      cout << " player 1 wins" << endl;
    else 
      cout << " it's a draw" << endl;
    }
}
The output is
Maximum increment=3
For target=3 player 1 wins
For target=4 player 2 wins
For target=5 player 1 wins
For target=6 player 1 wins
For target=7 player 1 wins
For target=8 player 2 wins
For target=9 player 1 wins
For target=10 player 1 wins
© Cambridge University Engineering Dept
Information provided by Tim Love (tpl)
Last updated: February 2008