Topological Sort

Notice:

You may use all standard libraries available on ecelinux. This includes the Standard Template Library (STL), cstring, etc.

Requirements

In this project, you will implement one class:

1. A directed acyclic graph: Directed_acyclic_graph

Note that there are no templates used in this project.

Description

This class stores a number of prioritized vertices and edges which connect those vertices. Initially the class has no edges and the priority (a double) of each vertex is equal to its numeric identifier (0 through n - 1). A topological sort is performed in the following manner: at any step of the topological sort where there are more than one vertices with in-degree zero, that vertex with highest priority (smallest numeric value) is chosen next.

Member Variables

The design of the class is up to you: you may use any data structure you see fit.

Member Functions

Constructors

The constructor takes an argument n which defines a graph with vertices numbered from 0 through n - 1. The vertex i is given an initial priority of i. The default value of n is 10.

Destructor

The destructor frees up any memory allocated by the constructor.

Copy Constructor

The copy constructor makes a complete copy of the directed acyclic graph passed in the argument.

Assignment Operator =

The default assignment operator is used.

Accessors

This class has six accessors:

int in_degree( int i ) const

Returns the in degree of the given vertex i. If i is outside the range 0, ..., n - 1, throw an illegal argument exception.

int out_degree( int i ) const

Returns the out degree of the given vertex i. If i is outside the range 0, ..., n - 1, throw an illegal argument exception.

int edge_count() const

Returns the number of edges in the graph. bool

adjacent( int i, int j ) const

Returns true an edge exists from vertex i to vertex j. If i or j are outside the range 0, ..., n - 1, throw an illegal argument exception.

bool connected( int i, int j ) const

Returns true there exists a directed path from vertex i to vertex j. Consider using a queue. Also, ask yourself: is (i) a path? If i or j are outside the range 0, ..., n - 1, throw an illegal argument exception.

void topological_sort() const

Print a topological sort of the vertices (as described above) in the DAG by printing the vertices separated by a dash -. The restriction is, if there are multiple possible vertices which could be included next in the ordering, the one with the highest priority value must be chosen. Recall that each topological sort must print all n vertices. The output should not have an end-of-line character at the end. An example of valid output of the code fragment cout << ">>>>>>>>>"; graph.topological_sort(); cout << "<<<<<<<<<"; may be >>>>>>>>>1-3-2-4-5-7-6-9-0-8<<<<<<<<<

Note that the >>>>>>>>> and <<<<<<<<< are a result of the two cout statements, both before and after.

Mutators

This class has four mutators:

bool set_priority( int i, double priority )

If another vertex already exists with that argument priority, return false and do nothing; otherwise, set the priority of vertex i to priority and return true. If i is outside the range 0, ..., n - 1, throw an illegal argument exception.

bool insert_edge( int i, int j )

Insert a new edge from vertex i to vertex j so long as the new vertex does not cause a cycle to appear. Return true if the insertion was successful, and false otherwise. If i equals j, return false and if an edge from i to j already exists, again, return false. If i or j are outside the range 0, ..., n - 1, throw an illegal argument exception.

void clear_edges()

Removes all the edges from the graph.

void reset_priorities()

Sets the priority of all of the vertices to their default value.

Friends

The class has no friends.

Testing

Consider testing your code with something like:

#include < iostream>
#include "Directed_acyclic_graph.h"
using namespace std;

int main() {
Directed_acyclic_graph graph(4);
graph.insert_edge( 0, 2 );
graph.insert_edge( 2, 1 );
graph.insert_edge( 1, 0 ); // should return false
graph.insert_edge( 0, 3 );
graph.connected( 0, 1 ); // should return true
graph.connected( 1, 0 ); // should return false
graph.adjacent( 0, 1 ); // should return false
graph.adjacent( 0, 2 ); // should return true
graph.adjacent( 1, 0 ); // should return false
graph.adjacent( 2, 0 ); // should return false
graph.topological_sort(); // prints 0-2-1-3 cout << endl;
graph.set_priority( 3, 0.5 );
graph.topological_sort(); // prints 0-3-2-1 cout << endl;

return 0;
}

Common Issues

Note that if there are no edges in the graph, the topological sort will be a printout of the vertices in order of their priority.

Recall that the order in which member variables are assigned in the copy constructor is the same order in which the member variables are declared in the class definition. Thus, the following would fail:

class Faulty { private:
int *array; int towers;

public:
Fault( int );
Fault( Fault const & );
};

// 'array' is assigned before 'towers' even though it looks like // 'towers' is assigned the value of the argument first.
Fault::Fault( int n ):
towers( n ), array( new int[towers] ) {
// empty
}

// Similarly, 'array' is assigned before 'towers' even though it looks like
// 'towers' is assigned the value of 'faulty.towers' first.
Fault::Fault( int n ):
Fault::Fault( Fault const &faulty ):
towers( faulty.towers ), array( new int[towers] ) { for ( int i = 0; i < towers; ++i ) { array[i] = faulty.array[i];
}
}