DynamicDirectedGraph Class Reference

Public Member Functions
	DynamicDirectedGraph (int vertices)
template<typename Iter >
Iter	get_vertices (Iter dest)
int	no_of_vertices ()
template<typename Iter >
Iter	adjTo (int vertex, Iter dest)
void	add_edge (int u, int v)
void	delete_edge (int u, int v)
int	in_degree (int vertex)
int	out_degree (int vertex)

Detailed Description

Algorithm

1. Export the graph object to an adjacency matrix.
2. Find the vertices which have 0 in-degree.
3. Add them to a queue.

Servicing a queue

1. Deque an element off the queue
2. Remove all the edges emnating from the element.
3. Add the element to topological order.
4. For every edge u-v emnating from u : delete_edge(u, v) if(in-degree(v) == 0) add v to the queue. Operations on the graph required. in-degree(v) - Read and write out-degree(v) - Read and write edge deletion adj(v)

Constructor & Destructor Documentation

DynamicDirectedGraph::DynamicDirectedGraph

(

int

vertices

)

                                                       {
    
    // Initialize total_vertices
    total_vertices = vertices;

    // Initialize the adj_matrix to all zeroes
    vector<int> zeroes(vertices);
    fill_n(zeroes.begin(), vertices, 0);
    for(int i = 0; i < vertices; i++)
        adj_matrix.push_back(zeroes);

    // Initialize the indeg and outdeg vectors to all zeroes
    fill_n(back_inserter(indeg), vertices, 0);
    fill_n(back_inserter(outdeg), vertices, 0);
}

Member Function Documentation

void DynamicDirectedGraph::add_edge	(	int	u,
		int	v
	)

                                                {
    
    adj_matrix[u][v] = 1;
    outdeg[u]++;
    indeg[v]++;
}

template<typename Iter >

Iter DynamicDirectedGraph::adjTo	(	int	vertex,
		Iter	dest
	)

                                                      {
    for(int idx = 0; idx < total_vertices; idx++)
        if(adj_matrix[vertex][idx] == 1)
            *dest++ = idx;
    return dest;
}

void DynamicDirectedGraph::delete_edge	(	int	u,
		int	v
	)

                                                   {
    adj_matrix[u][v] = 0;
    outdeg[u]--;
    indeg[v]--;
}

template<typename Iter >

Iter DynamicDirectedGraph::get_vertices

(

Iter

dest

)

                                                 {
    for(int i = 0; i < total_vertices; i++)
        *dest++ = i;
    return dest;
}

int DynamicDirectedGraph::in_degree

(

int

vertex

)

                                         {
    return indeg[u];
}

int DynamicDirectedGraph::no_of_vertices

(

)

                                         {
    return total_vertices;
}

int DynamicDirectedGraph::out_degree

(

int

vertex

)

                                          {
    return outdeg[u];
}

---

The documentation for this class was generated from the following file:

• alglib/graph/legacy/source_removal.cpp