In this section we list the C++sources for some of the graph algorithms in the library (cf. section Graph Algorithms).
Depth First Search
#include <LEDA/graph.h>
#include <LEDA/stack.h>
list<node> DFS(graph& G, node v, node_array<bool>& reached)
{
list<node> L;
stack<node> S;
node w;
if ( !reached[v] ) {
reached[v] = true;
S.push(v);
}
while ( !S.empty() ) {
v = S.pop();
L.append(v);
forall_adj_nodes(w,v)
if ( !reached[w] ) {
reached[w] = true;
S.push(w);
}
}
return L;
}
Breadth First Search
#include <LEDA/graph.h>
#include <LEDA/queue.h>
void BFS(graph& G, node v, node_array<int>& dist)
{
queue<node> Q;
node w;
forall_nodes(w,G) dist[w] = -1;
dist[v] = 0;
Q.append(v);
while ( !Q.empty() ) {
v = Q.pop();
forall_adj_nodes(w,v)
if (dist[w] < 0) {
Q.append(w);
dist[w] = dist[v]+1;
}
}
}
Connected Components
#include <LEDA/graph.h>
int COMPONENTS(ugraph& G, node_array<int>& compnum)
{
node v,w;
list<node> S;
int count = 0;
node_array(bool) reached(G,false);
forall_nodes(v,G)
if ( !reached[v] ) {
S = DFS(G,v,reached);
forall(w,S) compnum[w] = count;
count++;
}
return count;
}
Depth First Search Numbering
#include <LEDA/graph.h>
int dfs_count1, dfs_count2;
void d_f_s(node v, node_array<bool>& S,
node_array<int>& dfsnum,
node_array<int>& compnum,
list<edge> T )}
{
// recursive DFS
node w;
edge e;
S[v] = true;
dfsnum[v] = ++dfs_count1;
forall_adj_edges(e,v) {
w = G.target(e);
if ( !S[w] ) {
T.append(e);
d_f_s(w, S, dfsnum, compnum, T);
}
}
compnum[v] = ++dfs_count2;
}
list<edge> DFS_NUM(graph& G, node_array<int>& dfsnum,
node_array<int>& compnum)
{
list<edge> T;
node_array<bool> reached(G,false);
node v;
dfs_count1 = dfs_count2 = 0;
forall_nodes(v,G)
if ( !reached[v] ) d_f_s(v, reached, dfsnum, compnum, T);
return T;
}
Topological Sorting
#include <LEDA/graph.h>
bool TOPSORT(graph& G, node_array<int>& ord)
{
node_array<int> INDEG(G);
list<node> ZEROINDEG;
int count=0;
node v,w;
edge e;
forall_nodes(v,G)
if ( (INDEG[v]=G.indeg(v))==0 ) ZEROINDEG.append(v);
while ( !ZEROINDEG.empty() ) {
v = ZEROINDEG.pop();
ord[v] = ++count;
forall_adj_nodes(w,v)
if( --INDEG[w]==0 ) ZEROINDEG.append(w);
}
return ( count==G.number_of_nodes() );
}
// TOPSORT1 sorts node and edge lists according to
// the topological ordering:
bool TOPSORT1(graph& G)
{
node_array<int> node_ord(G);
edge_array<int> edge_ord(G);
if ( TOPSORT(G,node_ord) ) {
edge e;
forall_edges(e,G) edge_ord[e]=node_ord[target(e)];
G.sort_nodes(node_ord);
G.sort_edges(edge_ord);
return true;
}
return false;
}
Strongly Connected Components
#include <LEDA/graph.h>
#include <LEDA/array.h>
int STRONG_COMPONENTS(graph& G, node_array<int>& compnum)
{
node v,w;
int n = G.number_of_nodes();
int count = 0;
int i;
array<node> V(1,n);
list<node> S;
node_array<int> dfs_num(G), compl_num(G);
node_array<bool> reached(G,false);
DFS_NUM(G,dfs_num,compl_num);
forall_nodes(v,G) V[compl_num[v]] = v;
G.rev();
for (i=n; i>0; i--)
if ( !reached[V[i]] ) {
S = DFS(G,V[i],reached);
forall(w,S) compnum[w] = count;
count++;
}
return count;
}
Dijkstra's Algorithm
#include <LEDA/graph.h>
#include <LEDA/node_pq.h>
void DIJKSTRA( graph& G, node s, edge_array<int>& cost,
node_array<int>& dist, node_array<edge>& pred )
{
node_pq<int> PQ(G);
int c;
node u,v;
edge e;
forall_nodes(v,G) {
pred[v] = 0;
dist[v] = infinity;
PQ.insert(v,dist[v]);
}
dist[s] = 0;
PQ.decrease_inf(s,0);
while ( ! PQ.empty()) {
u = PQ.del_min();
forall_adj_edges(e,u) {
v = G.target(e) ;
c = dist[u] + cost[e] ;
if ( c < dist[v] ) {
dist[v] = c;
pred[v] = e;
PQ.decrease_inf(v,c);
}
} // forall_adj_edges
} // while
}
Bellman/Ford Algorithm
#include <LEDA/graph.h>
#include <LEDA/b_queue.h>
bool BELLMAN_FORD(graph& G, node s, edge_array<int>& cost,
node_array<int>& dist, node_array<edge>& pred)
{
node_array<bool> in_Q(G,false);
node_array<int> count(G,0);
int n = G.number_of_nodes();
b_queue<node> Q(n);
node u,v;
edge e;
int c;
forall_nodes(v,G) {
pred[v] = 0;
dist[v] = infinity;
}
dist[s] = 0;
Q.append(s);
in_Q[s] = true;
while (!Q.empty()) {
u = Q.pop();
in_Q[u] = false;
if ( ++count[u] > n) return; //negative cycle
forall_adj_edges(e,u) {
v = G.target(e);
c = dist[u] + cost[e];
if ( c < dist[v] ) {
dist[v] = c;
pred[v] = e;
if ( !in_Q[v] ) {
Q.append(v);
in_Q[v]=true;
}
}
} // forall_adj_edges
} // while
return true;
}
All Pairs Shortest Paths
#include <LEDA/graph.h>
void all_pairs_shortest_paths(graph& G, edge_array<double>& cost,
node_matrix<double>& DIST)
{
// computes for every node pair (v,w)
// DIST(v,w) = cost of the least cost path from v to w;
// the single source shortest paths algorithms BELLMAN_FORD
// and DIJKSTRA are used as subroutines
edge e;
node v;
double C = 0;
forall_edges(e,G) C += fabs(cost[e]);
node s = G.new_node(); // add s to G
forall_nodes(v,G) G.new_edge(s,v); // add edges (s,v) to G
node_array<double> dist1(G);
node_array<edge> pred(G);
edge_array<double> cost1(G);
forall_edges(e,G)
cost1[e] = (G.source(e)==s) ? C : cost[e];
BELLMAN_FORD(G,s,cost1,dist1,pred);
G.del_node(s); // delete s from G
edge_array(double) cost2(G);
forall_edges(e,G)
cost2[e] = dist1[G.source(e)] + cost[e] - dist1[G.target(e)];
forall_nodes(v,G)
DIJKSTRA(G,v,cost2,DIST[v],pred);
forall_nodes(v,G)
forall_nodes(w,G)
DIST(v,w) = DIST(v,w) - dist1[v] + dist1[w];
}
Minimum Spanning Tree
#include <LEDA/graph.h>
#include <LEDA/node_partition.h>
void MIN_SPANNING_TREE(graph& G, edge_array<double>& cost, list<edge>& EL)
{
node v,w;
edge e;
node_partition Q(G);
G.sort_edges(cost);
EL.clear();
forall_edges(e,G) {
v = G.source(e);
w = G.target(e);
if ( !(Q.same_block(v,w)) ) {
Q.union_blocks(v,w);
EL.append(e);
}
}
}