I have a graph with 14 nodes and 21 links. This graph shows an optical network. The links are bidirectional and there are some resources on each link. Assume there is a working path from a source to a destination which carry a packet containing data and uses some resources(some amount of bandwidth of the link that it is traversed by). for each source and destination, I must establish a working and a protection path simultaneously in advance in case of a link failure but they muse be link disjoint.(they cannot traverse any common link)
For example I send a packet from node1 to node4 through route<1,2,3,4> as the working path. If link 1-2 fails, I have to send the packet through a protection path that has been established in advance and is disjoint with the working path. for example my protection path may be <1,9,3,4>.
The purpose is write a code in C/C++ to find the protection path which is link disjoint with the working path. Actualy I couldn't get an idea for doing that. Any help would be greatly appreciated.
This is a piece of my code where I have allocate resources to working paths, I don't know how I can do the same for establishing protection path under condition that it must be disjoint with the working path.
int required_fs;
int des;
int idpk;
double holding;
int src;
//get the information about the packet that is sent from source to destination.
Packet *pkptr;
pkptr = op_pk_get (0);
op_pk_nfd_get(pkptr,"bw_fs",&required_fs);
op_pk_nfd_get(pkptr,"des",&des);
op_pk_nfd_get(pkptr,"src",&src);
op_pk_nfd_get(pkptr,"id",&idpk);
op_pk_nfd_get(pkptr,"ht",&holding);
bw_req=bw_req + required_fs;
number_of_req=number_of_req+1;
if (number_of_req > 1000000)
{
FILE* file1=fopen("C:/400f_rsa.txt","a+");
fprintf(file1,"\n");
fprintf(file1,"number_of_req ,number_of_nack,number_of_ack , bw_req , bw_nack , bw_ack " );
fprintf(file1,"\n");
fprintf(file1," %d , %d , %d , %d , %d , %d ", number_of_req, number_of_nack ,number_of_ack,bw_req,bw_nack,bw_ack );
fprintf(file1,"\n");
fprintf(file1,"------------------------------- ");
fclose (file1);
op_sim_end("1000000 paket","","","");
}
// Allocate the resources on each link to the working path, This part must be the same for the protection path too.
int determined_t=0;
int determined_r=0;
int determined_p_f=0;
int determined_p_e=0;
int determined_k=0;
for ( int i=1; i<=10; i++)
{
if (transmitter[src][i]==0)
{
determined_t=i;
break;
}
}
if (determined_t!=0)
{
for ( int i=1; i<=10; i++)
{
if (reciever[des][i]==0)
{
determined_r=i;
break;
}
}
if (determined_r!=0)
{
for ( int k=1; k<=2 ; k++)
{
determined_p_f=0;
determined_p_e=0;
int count = paths_node[src][des][k][2][14];
zero_array();
for (int i=1; i<=count; i++)
{
finding_fs( k, i, des, src );
}
if ( ff_rr==0)
{//ff
////checking gap
determined_p_f=find_first_free_gap(required_fs);
if (determined_p_f!=0)
{
determined_p_e=determined_p_f+required_fs-1;
if (determined_p_e != 1000)
{
determined_p_e=determined_p_e+1;
}
determined_k=k;
break;
}
}
else if (ff_rr==1)
{//rr
clear_rr_gap();
find_rr_gap(required_fs);
int index=rr_spectrum();
determined_p_f=ary_rr[index].first;
if (determined_p_f!=0)
{
determined_p_e=ary_rr[index].last;
determined_k=k;
break;
}
}
}
if (determined_p_f!=0)
{
//add to ls , applying
int count_link = paths_node[src][des][determined_k][2][14];
for ( int i=1; i<=count_link ; i++)
{
int num_link_p=paths_node[src][des][determined_k][2][i];
for ( int j=determined_p_f ; j<=determined_p_e; j++)
{
links_fs[num_link_p][j]=1;
}
}
reciever[des][determined_r]=1;
transmitter[src][determined_t]=1;
ls(determined_p_f,determined_p_e,determined_r,determined_t,determined_k,src,des,idpk);
number_of_ack= number_of_ack +1 ;
bw_ack= bw_ack + required_fs;
op_intrpt_schedule_self(op_sim_time ()+ holding,idpk);
op_pk_destroy(pkptr);
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
Note well in the first place that the information you have presented in no way ensures that there will be even one path between any two particular nodes, much less two disjoint ones. If your graph is structured in such a way that it is guaranteed to have two disjoint paths between each pair of nodes, however, then your best bet is probably to use your knowledge of that structure to find the wanted pairs of paths. For example, if you know that the graph contains a loop that traverses all nodes, then you can obtain two disjoint paths between each node pair by traversing that loop in opposite directions from one to the other.
On the other hand, if you're trying to find such disjoint path pairs where they exist, and elsewhere to determine that no such pair exists, then you have some options.
Conceptually easiest would be to determine for each pair of nodes all non-looping paths between them, and then to look for two that have only the start and end nodes in common. You could use either a depth-first or a breadth-first search for the path enumeration. This is computationally challenging on general graphs because the number of paths scales exponentially, but with the relatively small and fairly sparse graph you describe, it would probably work.
You could refine that approach by testing each new path, as you discover it, against all the previously-discovered ones. You may that way sometimes discover usable pairs without enumerating every path. If you do this then a BFS-based approach will tend to find a usable pair more quickly than DFS-based one. This will still enumerate all the paths between your nodes when there is no disjoint pair.
I can imagine more elaborate approaches in which you search disjoint pairs together, instead of searching individual paths, but I'm inclined to think that these would tend to be inefficient on account of involving a lot of duplicate work. That suggests a possible resolution via dynamic programming, but at this point I'm indulging fairly heavily in speculation.
What you cannot reliably do is simply choose one path and and then look for another that traverses the remaining nodes. It is entirely possible that there are suitable path pairs, but the first path you choose is not a member of such a pair.