Graph connectivity 2

This is a follow up page to the page on graph algorithms and connectivity. It contains some ideas on how you can find paths in a graph; how you can use Maple to create diagrams of your C++ graphs, and an interesting improvement of the "distances" algorithm using a "fifo" or "queue".

1. Finding paths in a graph

Sometimes you want to know more than the distance between two vertices in a graph: you also want to know a shortest path from one vertex to another. This can be done using a modification of the distances algorithm. The C++ function looks like this,

/* 
 * computes a shortest directed path "path" in g from vertex v0 to vertex v1 in g,
 * and returns 0 on success, or returns 1 if there is no such path
 *
 * On success, the "path" vector will contain a sequence of vertices
 * starting with v0 and ending with v1:
 *    path[0]==v0, path[1], ... , path[k-1], path[k]==v1
 */
void findpath( vector< vector<int> >& g, int v0, int v1, vector<int>& path) {
  int n = g.size();
  // the rest is over to you ...			  
}

A suggested algorithm is as follows.

Start with a "distances" vector as before and search vertices of the graph, fillng the distances vector with the distance of the vertex from v0 as before.
However, if the previous algorithm ever "looks at" v1 then you should stop filling the "distances" vector straight away as you will have found the distance ( $k$ say) from v0 to v1; and a suitable path can be found from the "distances" vector. (As follows.)
Resize path to have size $k + 1$ and put path[k] = v1.
For each l from k - 1 to 0 going down in steps of 1,
- Find a vertex $u$ in g with distance $l$ from v0 such that there is an edge from $u$ to the vertex path[l+1]. Put this in path[l].

Exercise.

Implement this.

A modification of this could find all shortest pathes from v0 to v1. (Exercise.)

2. Displaying graphs in Maple

There is a "GraphTheory" package in Maple. If you like Maple, a sensible idea is to get C++ to write text that is compatible with Maple, containing the Maple commands for what you want to do, and then copy the output from C++ into a Maple window using the mouse.

It is possible to copy text from Microsoft's cmd.exe Command Prompt window, but this is not particularly easy with MS-Windows prior to version 10. You will also need to load the "GraphTheory" package in Maple of course before pasting graph commands into Maple.

All this works, up to a point, but as far as I can see, Maple's graphs do not allow loops, and many of the graphs here do have loops. (I do not know if multiple edges are allowed.)

But if the graph is simple, or is a digraph with no loops or multiple edges, we can do this. My C++ code producing Maple-compatible output follows.

/* 
 * prints instructions for Maple to display the graph
 */
void printgraphformaple( vector< vector<int> >& g ) {
  int n = g.size();
  bool simp = issimple(g);
  bool hasloop = false;
  for (int i=0; i<n; i++) {
    if (adjacent(g,i,i)) {
      // loop found, print warning message
      if (!hasloop) {
	// print this for first loop found only
	cout << "Warning: this graph has at least one loop, and Maple is not able to display loops!" << endl;
	cout << "Loops found: ";
	hasloop = true;
      }
      // print this for all loops found
      cout << "(" << i <<","<< i << ") ";
    }
  }
  if (hasloop) {
    // finish warning message with end-line
    cout << endl;
  }
  cout << "GraphTheory[DrawGraph]( GraphTheory[Graph]( [";
  for (int i=0; i<n-1; i++) { cout << i << ","; }
  cout << (n-1) << " ] , { ";
  if (simp) {
    // maple expects undirected edges to be indicated by { .. }
    bool started = false;
    for (int i=0; i<n; i++)	 {
      int s = g[i].size();
      for (int j=0; j<s; j++) {
	if (g[i][j]<=i) continue; // don't repeat edges if it is simple
	if (!started) { started=true; } else { cout << ","; } 
	cout << "{" << i << "," << g[i][j] << "}";
      }	
    }
  } else {
    // maple expects directed edges to be indicated by [ .. ]
    // and does not allow loops
    bool started = false;
    for (int i=0; i<n; i++)	 {
      int s = g[i].size();
      for (int j=0; j<s; j++) {	      	
	int k = g[i][j];
	if (k==i) continue; // don't print loops!
	if (!started) { started=true; } else { cout << ","; } 
	cout << "[" << i << "," << k << "]";
      }	
    }
  }
  cout << " } ) ) ;" << endl; 
}

As before, copy this code into your program, and modify "main" to call it. When it runs, if it finds a loop then it will display a warning message and a list of all loops in the graph, and then it prints the Maple instructions to display the graph with loops removed, which you can copy and paste into Maple.

It is not compulsory, but do try it out!

If you are keen you might like to think about alternatives. Maybe getting C++ to write LaTeX code is a good idea, especially with packages like TikZ for LaTeX, see e.g. http://www.texample.net/tikz/examples/tag/graphs/ .

3. FIFOs

The algorithm I presented to you for "distances" in the previous page was a simplification that is a little easier to program but which has an issue affecting its efficiency. (Please note that for the programming parts of this assessment, if you did it correctly as described up to now you will get full marks. It is not compulsory to program the ideas here, though you should at least read them and there may be quiz questions on them.)

The issue is that, given a value for the "current distance" $d$ the algorithm has to search for a vertex at distance $d$ from v0. This search should not be necessary because a suitable vertex was recently visited in a previous part of the algorithm.

The improvement I am going to suggest requires you to somehow record the recently visited vertices and use them later, instead of doing an unnecessary search. Unfortunately, when we visit a vertex at distance $d$ from v0 it may have many neighbours, some of which are at distance $d + 1$ from v0. In other words, sometimes visiting a vertex gives a list of many new vertices to visit, and sometimes it gives no new vertices.

This can be solved in C++ using something variously known as a queue or fifo. A queue is a special kind of variable in which you can both insert new numbers and retrieve old numbers whenever you like (provided there are at least as many inserted as retreived). The order that the numbers get retrieved is this: the oldest item that was inserted and not yet retrieved is always the next item to be retrieved. (It is called FIFO for "First In First Out".)

A FIFO or queue can be made using a C++ vector. Here we want to insert and retrieve int values so we use a vector<int>. To each vector used in this way we need to also have an index saying where the next item to be retrieved is.

/* simple implementation of a fifo or queue */

// declaration: a vector (initially empty) and an index
vector<int> myfifo(0); // the 0 says it is initially empty
int myfifoindx=0;      // the position of the next item

// how to insert an int i into the queue
myfifo.push_back(i);

// how to test if the fifo has items in it to be retrieved
if (myfifo.size() > myfifoindx) {
  // there are items to be got
} else {
  // fifo is empty
}

// how to get an item from the queue and put it in a variable j
j = myfifo[myfifoindx]; // get the value
myfifoindx++;           // increment the indx

You can copy and paste these snippets of code where they are needed, or insert them into functions with appropriate names.

This simple implementation has a disadvantage: old values that were in the queue stay in memory and do not get deleted. This is a problem sometimes, but for our particular application it is not a major problem because the queue is local to the "distances" function and it gets deleted completely when the "distances" function finishes. However, C++ has a standard kind of object called queue (related to "vector") that deals with this problem efficiently. Use it like this:

/* standard C++ implementation of a fifo or queue */

// the #include line you need
#include <queue>

// if this next line is not used replace "queue" by "std::queue"
using namespace std;

// declaration: an initially empty queue
queue<int> myfifo;

// how to insert an int i into the queue
myfifo.push(i);

// how to test if the queue has items in it to be retrieved
if (myfifo.empty()) {
  // myfifo is empty
} else {
  // there are items to be got
}

// how to get an item from the queue and put it in a variable j
j = myfifo.first(); // get it
myfifo.pop();       // and remove it from the queue

This is documented at http://www.cplusplus.com/reference/queue/queue/ .

Using one of these two approaches, keen students can make their distances algorithm faster by

Initialise dist as before.
Initialise a fifo as initially empty and then push v0 into it.
While the fifo is not empty...
- Pop a vertex v from the fifo and look at $v$ ...
  - ...meaning, for each vertex u that is adjacent to v look at the edge $v \to u$ ...
    - ...meaning, if the distance from v0 to u was previously recorded as "infinity" change this value to dist[v] + 1 and push the vertex u onto the fifo.

Note that "for each vertex u that is adjacent to v" is best implemented by looking at the adjacency list for v directly, and not using the "adjacent" function and a loop over all vertices, since most vertices in most graphs typically have degree rather less than the total number of vertices in the graph, and this is always true if there are no multiple edges.

The algorithms used here (especially when implemented using a FIFO) are closely related to "Breadth first searches" and "Depth first searches". See https://en.wikipedia.org/wiki/Breadth-first_search and https://en.wikipedia.org/wiki/Depth-first_search for more information.

Remark: there is also an important related concept of stack or lLIFO (Last In First Out) which "pushes" in the same way as a queue, but always pops the last (most recent) item and leaves the oldest item to last. If anything, stacks are even more useful than queues. C++'s vectors make very good stacks because of the push_back(), back() and pop_back() functions on vectors. (See arrays.html.) C++'s vectors are not so good at making FIFOs because it is slower to delete the first element of a vector than the last element.