Assignment:

In this assignment, we consider a simple Graph class in C++ supporting some basic functionalities of graphs. These include the following support:

Reading and writing graphs from files specified in the format used by graphviz.

Constructing random (directed or undirected) graphs of a given size.

Iterating through vertices or edges (two styles of iterators).

Searching on an input graph (Breadth First Search and Depth First Search).

Sources:

graph.h and graph.cpp: define the Graph class for this assignment.

make_graph.cpp: generates random graphs.

bfs_graph.cpp and dfs_graph.cpp: run Breadth and Depth First Searches on an input graph (in graphviz format) and outputs the BFS/DFS trees (in graphviz format).

Makefile.

For this assignment, provide the missing pieces in the template above. Note: don't modify the template class definitions.

Files:

makefile:

CC = g++

FLAGS = -g -Wall

DFLAGS =

INPUT_FILE = in_graph.txt

BFS_FILE = out_bfs.txt

DFS_FILE = out_dfs.txt

GRAPH_SIZE = 5

SOURCE = make_graph.cpp bfs_graph.cpp dfs_graph.cpp

EXECS = test_make_graph test_bfs test_dfs

all: test_make_graph test_bfs test_dfs run_make run_bfs run_dfs

run_make:

./test_make_graph $(GRAPH_SIZE) $(INPUT_FILE); dot -Tps $(INPUT_FILE) -o in.ps

run_bfs:

./test_bfs $(INPUT_FILE) $(BFS_FILE); dot -Tps $(BFS_FILE) -o out_bfs.ps

run_dfs:

./test_dfs $(INPUT_FILE) $(DFS_FILE); dot -Tps $(DFS_FILE) -o out_dfs.ps

test_make_graph: make_graph.cpp

$(CC) $(FLAGS) $(DFLAGS) -o test_make_graph make_graph.cpp

test_bfs: bfs_graph.cpp

$(CC) $(FLAGS) $(DFLAGS) -o test_bfs bfs_graph.cpp

test_dfs: dfs_graph.cpp

$(CC) $(FLAGS) $(DFLAGS) -o test_dfs dfs_graph.cpp

clean:

rm -f $(EXECS)

bfs_graph.cpp

#include

#include

#include

#include

#include

#include "graph.h"

using namespace std;

/* main:

* test driver for Breadth First Search (BFS) on graphs.

* to compile:

* g++ -g -o test_bfs bfs_graph.cpp

* to run:

* ./test_bfs in_graph.txt out_bfs.txt

* this reads a graph from the file "in_graph.txt" and

* runs BFS (starting at first vertex) on the input graph

* and writes out the BFS tree to "out_bfs.txt"

*/

int main( int argc, char *argv[] )

{

assert( argc > 2 );

// read in graph

Graph my_graph;

ifstream in;

in.open( argv[1] );

in >> my_graph;

in.close();

#ifdef DEBUG

// show input graph

cerr << "Input graph:" << endl;

cerr << my_graph;

#endif

// run BFS

int start_vertex = 0;

Graph my_bfs_tree( my_graph.BFS(start_vertex) );

// write out graph

ofstream out;

out.open( argv[2] );

out << my_bfs_tree << endl;

out.close();

#ifdef DEBUG

// show output graph

cerr << "Output BFS tree:" << endl;

cerr << my_bfs_tree;

#endif

}

dfs_graph.cpp:

#include

#include

#include

#include

#include

#include "graph.h"

using namespace std;

/* main:

* test driver for Depth First Search (DFS) on graphs.

* to compile:

* g++ -g -o test_dfs dfs_graph.cpp

* to run:

* ./test_search_graph in_graph.txt out_dfs.txt

* this reads a graph from the file "in_graph.txt" and

* runs DFS on the input graph and outputs the DFS tree

* to the file "out_dfs.txt"

*/

int main( int argc, char *argv[] )

{

assert( argc > 2 );

// read in graph

Graph my_graph;

ifstream in;

in.open( argv[1] );

in >> my_graph;

in.close();

#ifdef DEBUG

// show input graph

cerr << "Input graph:" << endl;

cerr << my_graph;

#endif

// run DFS

Graph my_dfs_tree( my_graph.DFS() );

// write out graph

ofstream out;

out.open( argv[2] );

out << my_dfs_tree << endl;

out.close();

#ifdef DEBUG

// show output graph

cerr << "Output DFS tree:" << endl;

cerr << my_dfs_tree;

#endif

}

graph.cpp

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

/////////////////////////////////////////////////////////

// constructors

/////////////////////////////////////////////////////////

// construct a random graph

template

Graph::Graph( const vector &vertex_set, bool is_directed )

{

size = vertex_set.size();

directed = is_directed;

// FILL IN

}

/////////////////////////////////////////////////////////

// accessors

/////////////////////////////////////////////////////////

template

vector Graph::vertices()

{

vector vertex_set;

for (vertex_iterator i = begin(); i != end(); i++) {

vertex_set.push_back(i->first);

}

return vertex_set;

}

/////////////////////////////////////////////////////////

// mutators

/////////////////////////////////////////////////////////

// insert edge

template

void Graph::insert( const T &u, const T &v )

{

adjacency_list[u].push_back(v);

}

/////////////////////////////////////////////////////////

// predicates

/////////////////////////////////////////////////////////

template

bool Graph::is_vertex( const T &u ) const

{

return (adjacency_list.find(u) != end());

}

template

bool Graph::is_edge( const T &u, const T &v ) const

{

vertex_iterator i = adjacency_list.find(u);

if (i == end()) {

return false;

}

assert( i->first == u );

typedef typename std::vector NeighborList;

typedef typename NeighborList::const_iterator neighbor_iterator;

NeighborList neighbors = i->second;

neighbor_iterator j = find( neighbors.begin(), neighbors.end(), v );

return (j != neighbors.end()) ? true : false;

}

////////////////////////////////////////////////////////////

// Breadth First Search

////////////////////////////////////////////////////////////

#define INFINITY -1

enum COLOR {WHITE, GRAY, BLACK};

template

struct BFS_Vertex {

COLOR color;

int distance;

T previous;

};

template

Graph Graph::BFS( const T & start_vertex )

{

map > BFS_Tree;

Graph outputTree;

queue BFS_Queue;

// FILL IN

return outputTree;

}

////////////////////////////////////////////////////////////

// Depth First Search

////////////////////////////////////////////////////////////

template

struct DFS_Vertex {

COLOR color;

int discover_time, finish_time;

T previous;

};

template

Graph Graph::DFS()

{

map > DFS_Tree;

Graph outputTree;

stack DFS_Stack;

// FILL IN

return outputTree;

}

graph.h

#ifndef GRAPH_H

#define GRAPH_H

#include

#include

#include

using namespace std;

template

class Graph

{

private:

typedef typename std::map< T, vector > AdjacencyList;

AdjacencyList adjacency_list;

int size;

bool directed;

public:

// constructors

Graph():size(0), directed(false) { adjacency_list.clear(); }

// for empty graph

Graph( const vector &vertex_set, bool is_directed );

// for random graph

Graph( const Graph &g ):size(g.size), directed(g.directed)

{ adjacency_list = g.adjacency_list; }

// copy constructor

// destructor

~Graph() { adjacency_list.clear(); }

// accessors

int getSize() { return size; }

// returns the number of vertices

vector vertices();

// returns all vertices in the graph

// predicates

bool is_vertex( const T &u ) const;

// true if u is a vertex in the graph

bool is_edge( const T &u, const T &v ) const;

// true if (u,v) is an edge in the graph

bool is_directed() const { return directed; }

// true if the graph is directed

// mutator(s)

void setDirected(bool b) { directed = b; }

void insert( const T &u, const T &v );

// adds a new edge (u,v) to the graph

// iterator for vertices

// reuses iterator for std::map

typedef typename AdjacencyList::const_iterator vertex_iterator;

vertex_iterator begin() const { return adjacency_list.begin(); }

vertex_iterator end() const { return adjacency_list.end(); }

// iterator for neighborhoods

// uses an inner iterator class

class neighbor_iterator {

public:

neighbor_iterator( Graph &g, T &v )

{ alist = g.adjacency_list[v]; }

T begin() { it = alist.begin(); return *it; }

bool end() { return (it == alist.end()); }

T next() { return *(++it); }

private:

typedef typename vector::const_iterator private_iterator;

vector alist;

private_iterator it;

};

// overloaded output (generates graphviz format)

friend ostream & operator<<(ostream &out, Graph &graph) {

// FILL IN

return out;

}

// overloaded input (assumes graphviz format)

friend istream & operator>>(istream &in, Graph &graph) {

// FILL IN

return in;

}

// graph searches

Graph BFS( const T &start_vertex );

Graph DFS();

};

#include "graph.cpp"

#endif

make_graph.cpp:

#include

#include

#include

#include

#include

#include "graph.h"

using namespace std;

/* main:

* test driver for generating a random graph.

* to compile:

* g++ -g -o test_make_graph make_graph.cpp

* to run:

* ./test_make_graph 13 my_graph.txt

* this creates a graph on 13 vertices and writes it to the file "my_graph.txt"

*/

int main( int argc, char *argv[] )

{

assert( argc > 2 );

// create random graph of a given size

int size;

size = atoi( argv[1] );

vector my_vertices;

for (int i=0; i

my_vertices.push_back(i);

}

Graph my_random_graph( my_vertices, true );

#ifdef DEBUG

cerr << "Random graph of size " << size << ":" << endl;

cerr << my_random_graph;

#endif

// write graph out to file

ofstream out;

out.open( argv[2] );

out << my_random_graph;

out.close();

}

in_graph.txt:

digraph {

0 -> 1;

0 -> 3;

0 -> 4;

1 -> 0;

1 -> 2;

2 -> 0;

2 -> 1;

2 -> 4;

3 -> 1;

3 -> 2;

}

out_bfs.txt:

digraph {

0 -> 1;

0 -> 3;

0 -> 4;

1 -> 2;

}

out_dfs.txt:

digraph {

0 -> 1;

0 -> 3;

1 -> 2;

2 -> 4;

}