Problem Description
Write a program that
-
generates a random series-parallel graph G (use OGDF’s generator, simply ignore the edge direction properties of the generated instance), and
-
prints a readable description of how the edges/subgraphs can be combined via parallel or serial combinations, in order to obtain G.
E.g., the graph with the edges {ab,bd,ac,cd,ad} would give an output similar to (there are multiple possibilities):
1 := SER ab bd 2 := SER ac cd 3 := PAR 1 ad G := PAR 3 2
(where the numbers just reference the lines where the corresponding subgraph was generated)
Find more details here.
Solution
/**
* This is the solution file for the Exercise 10
*
* @author Chameera Wijebandara
* @email chameerawijebandara@gmail.com
*
* Windows 7
* Vishual stuio 2010
* OGDF Snapshot 2014-02-28
*
*/
#include <ogdf/basic/Graph.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/basic/graph_generators.h>
#include <ogdf/layered/SugiyamaLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/FastHierarchyLayout.h>
#include <ogdf/layered/BarycenterHeuristic.h>
#include <map>
using namespace ogdf;
using namespace std;
// main
int main()
{
// init the new grapth
Graph G;
// genarate random series paralle grapth
randomSeriesParallelDAG(G, 6);
// set grapth attributes
GraphAttributes GA(G,
GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics |
GraphAttributes::nodeLabel | GraphAttributes::edgeStyle |
GraphAttributes::nodeStyle );
//maper to map node id
map<int, int> maper;
int nodeCount=0;
node v;
forall_nodes( v, G ){ // iterate through all the node in the graph
GA.fillColor( v ) = Color( "#FFFF00" ); // set node color to yellow
GA.height( v ) = 20.0; // set the height to 20.0
GA.width( v ) = 40.0; // set the width to 40.0
char id = (char)(nodeCount +'a');
GA.label( v ) = id;
maper.insert(make_pair(v->index(), nodeCount));
nodeCount++;
}
SugiyamaLayout SL; //init the SugiyamaLayout algorithm
SL.setRanking(new OptimalRanking);
SL.setCrossMin(new BarycenterHeuristic);
FastHierarchyLayout *fhl = new FastHierarchyLayout;
fhl->layerDistance(40.0); // set layer distance to 40.0
fhl->nodeDistance(20.0); // set node distance to 20.0.
SL.setLayout(fhl);
SL.call(GA);
GraphIO::drawSVG(GA, "execrise10.svg");
int n = G.numberOfNodes(); // get number of nodes
int m = G.numberOfEdges(); // get number of edges
if(n==1) // if grapth only contain 1 node
{
cout<<"G := a";
return 0;
}
if(n==2) // if grapth only contain 3 node
{
cout<<"G := ab";
return 0;
}
// init variblaes.
int* begin =new int[m];
int* end =new int[m];
int* state =new int[m];
// subgrapth index
int count =1;
int countHold=1;
// collect edeg data
edge e;
forall_edges(e,G){
int temp =e->index();
begin[temp] = maper.find(e->source()->index())->second ;
end[temp] = maper.find(e->target()->index())->second;
state[temp] = 0;
}
// count digree of the each node.
int* inCount = new int[n];
int* outCount = new int[n];
//go untill complete the graph
do{
countHold =count;
//init digree vaiables
for(int i=0; i<n; i++)
{
inCount[i]=0;
outCount[i]=0;
}
// calculate current degree
for(int i = 0; i < m; i++)
{
if(state[i]!=-1)
{
inCount[end[i]]++;
outCount[begin[i]]++;
}
}
// gothrough the each node
for(int i=0;i<n;i++)
{
// chaeck for seriall part
if(inCount[i] == 1 && outCount[i]==1)
{
// go througth every edge
for(int j=0;j<m;j++)
{
// check for second edge
if(begin[j]==i && state[j]!=-1)
{
for(int k=0;k<m;k++)
{
// chcheck edge is not used
if(end[k]==i && state[k]!=-1 && j!=k)
{
int tempCount=0;
for(int l=0;l<m;l++)
{
if(state[l]!=-1)
{
tempCount++;
if(tempCount>2)
{
break;
}
}
}
// print the output
if(tempCount>2)
{
cout<< count;
}
else
{
cout<<"G";
}
cout<<" := SER ";
if(state[k]==0)
{
cout<<(char)('a'+begin[k])<<(char)('a'+ end[k]);
}
else
{
cout<<state[k];
}
cout<<" ";
if(state[j]==0)
{
cout<<(char)('a'+begin[j])<<(char)('a'+end[j]);
}
else
{
cout<<state[j];
}
state[j] = -1;
cout<<endl;
// set new edge data
state[k] = count;
end[k] = end[j];
count++;
break;
}
}
break;
}
}
}
}
// chech for pararell part
for(int i=0;i<m;i++)
{
for(int j=i+1;j<m;j++)
{
// chaech for the same sorse and traget
if(begin[i] ==begin[j] && end[i]&& end[j] && state[i]!=-1 && state[j]!=-1)
{
int tempCount =0;
for(int k=0;k<m;k++)
{
if(state[k]!=-1)
{
tempCount++;
if(tempCount>2)
{
break;
}
}
}
// print the output
if(tempCount>2)
{
cout<< count;
}
else
{
cout<<"G";
}
cout<<" := PAR ";
if(state[i]==0)
{
cout<<(char)('a'+end[i])<<(char)('a'+begin[i]);
}
else
{
cout<<state[i];
}
cout<<" ";
if(state[j]==0)
{
cout<<(char)('a'+end[j])<<(char)('a'+begin[j]);
}
else
{
cout<<state[j];
}
cout<<endl;
// set new edge data
state[j] = -1;
state[i] = count;
count++;
break;
}
}
}
}while(count != countHold);
getchar();
// delet alocated memory
delete(begin);
delete(end);
delete(state);
delete(inCount);
delete(outCount);
}
Algorithm
do while( undiscovered edges ) // Find serial parts Find node if(indeg ==1 && out outdeg==1) // a -> b and b-> c Merge the sub graph // a -> c Print the sub graph details // i := SER ab bc // Find Parallel parts Find edges which has same source and target // a -> c and a -> c Merge the sub graph // a -> c Print the sub graph details // i := PAR 1 ac // State variable mange the state of the edge // -1 : finished // 0 : not yet discovered // >0 : already discovered( represent a sub graph)
Output
Chameerawijebandara's Blog 