\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={An Extended Experimental Evaluation of SCC (Gabow's vs Kosaraju's) based on Adjacency List},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2013-01-15 (revised: 15 January 2013)}
\def\TheID{\makeatother }
\def\TheDate{2013-01-15}
\title{An Extended Experimental Evaluation of SCC (Gabow's vs Kosaraju's) based on Adjacency List}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{, Gulraiz  Iqbal}

             \author[2]{Saleh  Alshomrani}

             \affil[1]{  King Abdulaziz University}

\renewcommand\Authands{ and }

\date{\small \em Received: 9 December 2012 Accepted: 31 December 2012 Published: 15 January 2013}

\maketitle


\begin{abstract}
        


We present the results of a study comparing three strongly connected components algorithms. The goal of this work is to extend the understandings and to help practitioners choose appropriate options. During experiment, we compared and analysed strongly connected components algorithm by using dynamic graph representation (adjacency list). Mainly we focused on i. Experimental Comparison of strongly connected components algorithms. ii. Experimental Analysis of a particular algorithm.Our experiments consist large set of random directed graph with N number of vertices V and edges E to compute graph performance using dynamic graph representation. We implemented strongly connected graph algorithms, tested and optimized using efficient data structure. The article presents detailed results based on significant performance, preferences between SCC algorithms and provides practical recommenddations on their use. During experimentation, we found some interesting results particularly efficiency of Cheriyan-Mehlhorn-Gabow's as it is more efficient in computing strongly connected components then Kosaraju's algorithm.

\end{abstract}


\keywords{graph algorithms, directed graph, SCC (strongly connected components), transitive closure.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{Introduction}]{Introduction}\par
raphs are widely used in computer, mathematics as well in chemistry, biology and physics. Pair wise relation between objects e.g. Computer networks (Switches, routers and other devices are vertices and edges are wire / wireless connection between them), electrical circuits (vertices are diodes, transistors, capacitors, switched etc. and edges are wire connection between them), World Wide Web (web pages are vertices and hyperlink are edges) and Molecules (vertices are atoms and edges are bond between them) all benefits from the pair wise model \hyperref[b4]{[5,}\hyperref[b5]{6,}\hyperref[b14]{16]} . There are some additional examples of common graph based data.\par
? Traffic Networks, Locations are vertices and routes are vertices in traffic networks.\par
? Scientific citation Network, Papers are vertices and edges are citation between papers.\par
? Computer Network, PC's are vertices and network connections / devices are edges.\par
? Social Network sites, People are vertices and their acquaintances are edges.\par
Graph represent a collection of elements (Vertices or Nodes) V and connection between those elements are links known as edges E. Edges often have an associated weight and direction where edges weight might carry important data strength, importance or cost of an edge.\par
The sections of this paper are divided as following. The introduction section provides an overview of the relevant research in this area along with graph notation and its application. Section 2 explains the extensive literature review such as current java graph libraries available, graph representation techniques and basic graph algorithms and scc graph algorithms. In section 3, we discuss the implementation, and section 4 of the model is based on our experiments. Finally section 5 and 6 presents conclusions and some important future directions respectively. 
\section[{a) Notation \& Basic definition of Directed Graph}]{a) Notation \& Basic definition of Directed Graph}\par
A directed graph G is a finite set of vertices V and set of directed edges E that forms the pair (V, E) and E ? V × V is a set of directed graph. If (v, u) ? E, then u is called immediate successor of v, and v is called immediate predecessor of u.\par
Undirected graphs may be observed as a special kind of directed graphs, where directions ofedges are unimportant (v, u) ? E â??" (u, v) ? E [2, 6] . A directed graph G = (V, E) is called strongly connected if\par
there is a path between v to u and u to v \hyperref[b5]{[6]} . 
\section[{II.}]{II.} 
\section[{Literature Review}]{Literature Review}\par
The first task is to design and develop a flexible graph library such that the graph algorithm can be implemented and tested and their performance is analyzed using the library benchmark. Many graph libraries are available in java as well in other languages. Most of the java libraries use sequential approaches which are slower over large graphs. In \hyperref[b2]{[3]} Kurt, Stefan, and Peter mention optimization technique. We have also adopted their technique and compared our results. Later on, we will compare our algorithm with other libraries to make it computationally fast.\par
? Annas, is an open source Java framework suitable for developers and researchers in the field of graph theory, graph structure, algorithms and distributed systems. It has many features such as support for directed \& undirected graphs, multi graph, fully( D D D D D D D D )\par
generic and has capability to export DOT, XML and adjacency matrix files \hyperref[b11]{[13]}.\par
? Jung, The java universal network / graph framework is an open source library which provides extensive modeling, analysis and visualization tool for the graph or network. JUNG architecture has flexible support to represent the entities and their relations, such as directed and undirected graph, hyper graphs, and graphs with parallel edges. It also includes graph theory, data mining, social network, optimization and random graph generator  {\ref [12]} .\par
? JGraphT, is an open source Java graph library using structured approach to implement graph algorithms. Most of the library classes are generic for the ease of users. In this library several graph algorithms are implemented using structured approach \hyperref[b10]{[11]} .\par
? JDSL is an open source data structure library in java using structured approach. It's a collection of java interfaces and classes that implement fundamental data structure. Advance and complex graph algorithms are not available in JDSL library. One of the powerful and safe operations on internal data structure representation is accessors \hyperref[b15]{[17]} .\par
During our work we used the existing libraries to implement different strongly connected components algorithms. 
\section[{a) Graph Representation}]{a) Graph Representation}\par
There are many possible ways to represent a graph in computer program but according to Mark.C.Chu-Carroll, there are two standard techniques to represent graphs in computer.\par
i. Adjacency Matrix / Matrix base Representation An adjacency matrix is N×N matrix of 0/1 values, where a vertex V i,j is 1 only if there is an edge between V i and V j otherwise it is 0. If Graph is undirected then the matrix is symmetric V i,j = V j,i . In case of directed graph then V i,j =1 means that there is an edge from V i to V j \hyperref[b9]{[10]} . Adjacency matrix is useful to add an edge. It requires O(1) time which is equal to the time for the verification of an edge between two vertices but an extra computational effort is required. Adjacency matrix required extra memory to store large graphs. Few algorithms require knowledge of their adjacent vertices which results O (|V|) complexity \hyperref[b9]{[10,}\hyperref[b14]{16]} .\par
ii. Adjacency list / List based representations An alternative representation for a graph G (V, E) is based on adjacency list. For each vertex we keep a list of all the vertices adjacent to the current vertex. We say that vertex V i is adjacent to vertex V j if (V i , V j ) ? E. It requires less memory and in some particular situations it outperforms adjacency matrix such as it gets the list of adjacent vertices with in O (1). In our experiments we use adjacency list with a few improvements to avoid iterative procedure. In our implementation we maintain a list of all nodes adjacent to the current node. The time complexity for adjacency list is O (n+m) \hyperref[b9]{[10,}\hyperref[b14]{16]} .\par
The adjacency matrix is more effective when edges don't have data associated with them. In case of sparse graph adjacency matrix performance is poor and huge amount of memory is wasted. Adjacency list is efficient in case of sparse graph, it stores only the edges present in the graph and can store data associated to edges. Although there is no clear suggestion which graph representation is better, we selected adjacency list representation for our experiments \hyperref[b9]{[10]} . 
\section[{b) Strongly Connected Components}]{b) Strongly Connected Components}\par
Let G = (V, E) be a directed graph, where C is a strongly connected components (SCC) of V. C is strongly connected if a maximal set of vertices after every two vertices (u, v) ? C are mutually reachable.\par
There is a path from vertex u to v and v to u or if a sub graph is connected in a way that there is a path from each node to all other nodes. If a graph has the same property, then the graph is strongly connected  {\ref [6. 16]} .\par
Strongly connected components can be computed using different approaches as introduced by Tarjan's, Gabow and Kosaraju's. Tarjan's and Gabow algorithm require only one DFS, whereas Kosaraju's algorithm requires two DFS. In this paper we included Kosaraju's algorithm. The asymptotic analysis of such algorithm on dynamic graph representation algorithm is O(|v|+|E|) and O (|V| 2 ) on adjacency matrix based implementation. As our implementation is based on adjacency list, it will take linear time to compute SCC which is similar to Tarjan's and Gabow's algorithm on dynamic graph representation.\par
Our previous experiments indicate that Tarjan's algorithm is slower than Gabow's algorithm \hyperref[b14]{[16]} . 
\section[{c) Depth First Search Algorithm}]{c) Depth First Search Algorithm}\par
Depth first search is a technique to explore a graph using stack as the data structure. It starts from the root of the graph, explore its first child, explore the child of next vertex until it reaches the target matrix or to the final matrix which has no further child. Then, back tracking is used to return the last vertex which is not yet completely explored. Modifying the post-visit and previsit, DFS is used to solve many important problems and it takes O (|V|+|E|) steps. i. Pseudo-code: DFS 1. DFS (v ): visits all the vertices reachable from v in depth-first order. 2.\par
Mark v as visited 3.\par
for each edge v ?u  Year (depth first search), initially with an empty stack of vertices V and pushing vertices onto the stack as recursion which started from vertices V and after completion of traversal vertices V will be available in the stack. To obtain reverse graph, all the edges of graph are reversed. It starts with the top vertex on the stack and traverses from that vertex. All vertices are reachable from that vertex such that it forms strongly connected components. By removing SCC from the stack and repeating the process with the new obtained top of the stack, stack will be empty and a list of SCC is collected.\par
i. Pseudo-code: SCC Input : DAG G= (V, E) Output : Set of strongly connected components Let S be an empty stack While S does not contain all vertices Choose an arbitrary vertex v not in S Start DFS (V) Push (u) on S Reverse the direction of all edges to obtain transpose graph.\par
For vertex v with label n?.1 and find all reachable vertices from v and group them as an SCC. 
\section[{e) Cheriyan-Mehlhorn-Gabow Algorithms}]{e) Cheriyan-Mehlhorn-Gabow Algorithms}\par
Gabow strongly connected component is also similar to Kosaraju's algorithm. It accepts a directed graph as an input and result contains a collection of all possible strongly connected components. It also uses depth first search to explore all the nodes of the directed graph. Gabow algorithm maintains two stacks; one of them contains a list of nodes which are not yet computed as strongly connected components and other contains a set of nodes that do not belong to various strongly connected components. A counter is used to count number of visited nodes, which is used to compute preorder of the nodes  {\ref [2, 3, and 4]}.  
\section[{Implementation}]{Implementation}\par
In our implementation we used only dynamic graph data structure that used linked lists for the adjacency list. The graph generator class makes sure that each vertex is stored in consecutive location in the adjacency list, as a fact dynamic implementation consumes more space then static graph data structure. The graph structure package contains interfaces and abstract classes to provide interface to different types of graphs such as Directed Graph. All classes mentioned in our method are Generic and user can use them by their own style. Graph package also contains many interfaces for different graphs and interfaces for the different algorithms describing that describe prerequisite method for the algorithms. The undirected graph is not currently used in our method, but it can be considered in future.\par
We have used a lot of interfaces and abstract classes which helps in implementation of the graph classes. The directed graph interface defines many methods such that each node represents a unique data member of generic type and two nodes can't be added to graph if they representing the same node. The second attempt will be ignored and also multiple edges between two nodes are not allowed. An abstract Node<E> class node that also serves as an interface for the vertex of DirectedGraph<E> interface, each node maintains a list of its successors and predecessors. Abstract Node<E> class also defines a set of protected methods that can be used to add and remove adjacent nodes. They should only be used by implementers of the DirectedGraph<E> interface. A public integer data member num is introduced to avoid externally constructed mappings between the node and some integer (e.g. a dfs GraphGenerator class implementing the interface of directed graph is specially designed for testing and benchmarking. Initializing the graph generator class by providing an instance of a class implementing the directed graph interface, all graphs generated are the instances of that class. This class is used to generate random, acyclic, dense, sparse and complete graphs. number). It should only be used internally and never be a part of any public interface since its interpretation might be changed from one algorithm to another. 
\section[{IV.}]{IV.} 
\section[{Experiments}]{Experiments}\par
In our experiments we used GraphGenerator class to generate sparse and dense graph. Graph with minimal edges E=100 considered as a sparse graph and graph with maximum edges E = 500 is a dense graph. We designed benchmark which generates six graphs of same size as input and measure the run time computing strongly connected components of given graphs; we computed average time to obtain the( D D D D D D D D )\par
Year performance of specific algorithm on a specific number of nodes and edges. We also calculated standard deviation that indicates upper bounds and lower bounds to visualize the variations and outliers in the data set using error bars on chart. Analysis of random graphs is also not easy because they contain random nodes, edges and dynamic memory.\par
In our experiments we used dynamic graph data structure using linked list for the adjacency list. We use intel® Core? i5-2410M CPU @2.30GHz with 4 GB of memory for computing our algorithms.\par
We have used eclipse version Helios Service Release 2 as IDE for java developers in our experiments. We increased the heap size by providing the argument -Xms128m -Xmx1550m -XX: +UseParallelGC.\par
For recursive calls stack size is also important. In some scenarios such as on a large number of vertices and edges, stack over flow error occurs. 
\section[{a) Experiments on Kosaraju's Algorithm}]{a) Experiments on Kosaraju's Algorithm}\par
In these experiments, a set of random graph for each graph (Dense and Sparse) with minimum edges E=100 for sparse graph and maximum edges E=500 for dense graph is generated. Figure 1 shows the running time difference between dense and sparse graph on N number of nodes.\par
Kosaraju's algorithm compute strongly connected components efficiently with increase in number of nodes or increase in number of edges. So edges have a direct impact on its running time. 
\section[{i. Average Computation Time}]{i. Average Computation Time}\par
Figure 1 presents the results generated by one benchmark methods. It is clear from the figures that with increase in the number of nodes and edges, Kosaraju's strongly connected components algorithm takes more time to run.  
\section[{b) Experiments on Gabow's Algorithm}]{b) Experiments on Gabow's Algorithm}\par
We had the same set of experiments for Gabow's algorithm, for each graph (Dense and Sparse). We generated six random graph with minimum edges E=100 for sparse graph and maximum edges E=500 for dense graph.\par
We computed their average completion time and memory storage as the Figure  {\ref 3} \& 4 show the difference between dense and sparse graph on N number of nodes. Gabow's algorithm compute strongly connected components efficiently when numbers of edges are lower. So edges have a direct impact on its running time and memory. 
\section[{i. Average Computation Time}]{i. Average Computation Time}\par
In Figure 4, line chart is used to present the results generated by our benchmark which show that with increase in the number of nodes and edges Gabow's SCC algorithm takes more time to run. The same data is used to compute average run time for each node. Also data is combined to get a unique data that is used to compare Kosaraju's and Gabow's algorithms. In Figure 5 \& 6 average completion time is computed on sparse graph (E=100) and dense graph (E=500) for both Kosaraju's and Gabow's algorithm. Performance of both algorithms is remarkable; as Gabow's algorithm take less completion time and variation then Kosaraju's algorithm. Kosaraju's algorithm is simple in implementation. for both Kosaraju's and Gabow's algorithms but their runtime is different.\par
V. 
\section[{Conclusions}]{Conclusions}\par
In our research, we analyzed \& compared Kosaraju's and Gabow's strongly connected component algorithms to find their suitability for various applications. We produced dense and sparse graphs randomly to compute memory difference of the both the algorithms. We found that Gabow algorithm is shorter, simpler and more elegant. Kosaraju's algorithm takes more time then to Gabow's algorithm on both dense and sparse graph. There are some limitations in our experiments. In a limited data set, we produced six graphs with N=3900, using sparse graph E=100 and dense E=500 to compute average run time memory and average completion time. In future we will develop a large graph with increase in the stack size and java VM heap size.\par
In this research, we have focused on Kosaraju's and Gabow's algorithms only and data structure used is adjacency list. In future, we would implement Brute's algorithm to compute strongly connected components using a hybrid algorithm and as well involving other data structures for graph.\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}}\end{figure}
       			\footnote{EAn Extended Experimental Evaluation of SCC (Gabow's vs Kosaraju's) based on Adjacency List} 			\footnote{Egraph G as an input and performs a recursive DFS An Extended Experimental Evaluation of SCC (Gabow's vs Kosaraju's) based on Adjacency List} 			\footnote{An Extended Experimental Evaluation of SCC (Gabow's vs Kosaraju's) based on Adjacency List} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Website]{b10}\label{b10} 	 		\textit{},  		 			Jgraph Website 		.  		 \url{http://www.jgraph.com/}  		p. .  	 
\bibitem[Annas Website]{b11}\label{b11} 	 		\textit{},  		 			Annas Website 		.  		 \url{https://sites.google.com/site/annasproject/retrievedon09-2012}  		 	 
\bibitem[Holten et al. ()]{b13}\label{b13} 	 		‘An Extended Evaluation of the Readability of Tapered, Animated, and Textured Directed-Edge Representations in Node-Link Graphs’.  		 			Danny Holten 		,  		 			Petra Isenberg 		,  		 			Jarke J Van Wijk 		,  		 			Jean-Daniel Fekete 		.  	 	 		\textit{Pacific Visualization Symposium},  				 (Pacific Vis)  		2011. IEEE.  	 
\bibitem[Saleh Alshomrani and Iqbal (2012)]{b14}\label{b14} 	 		\textit{Analysis of Strongly Connected Components (SCC) Using Dynamic Graph Representation, IJCSI},  		 			Gulraiz Saleh Alshomrani 		,  		 			Iqbal 		.  		July 2012. 9.  	 
\bibitem[Shirinivas et al. ()]{b12}\label{b12} 	 		‘Application of graph theory in computer science an overview’.  		 			S G Shirinivas 		,  		 			S Vetrivel 		,  		 			Dr N M Elango 		.  	 	 		\textit{International Journal of Engineering Science and Technology}  		2010. 2  (9)  p. .  	 
\bibitem[Barnat et al.]{b1}\label{b1} 	 		‘Computing strongly connected components in parallel on CUDA’.  		 			Jiri Barnat 		,  		 			Petr Bauch 		,  		 			Lubos Brim 		,  		 			Milan Ceska 		.  	 	 		\textit{IEEE 2011 International Parallel \& Distributed Processing Symposium},  				 	 
\bibitem[Hopcroft and Kosaraju ()]{b0}\label{b0} 	 		‘Dividing a graph into triconnected compoents’.  		 			J E Hopcroft 		,  		 			R E Kosaraju 		.  	 	 		\textit{SIAM Journal on Computing}  		1973. 2  (3)  p. .  	 
\bibitem[Mehlhorn et al. ()]{b2}\label{b2} 	 		\textit{Engineering DFS based Graph Algorithms, Partially supported by DFG grant SA 933/3-1},  		 			Kurt Mehlhorn 		,  		 			Stefan Naher 		,  		 			Peter Sanders 		.  		2007.  	 
\bibitem[Barnat and Chaloupka ()]{b7}\label{b7} 	 		‘Jaco van de Pol, Distributed algorithms for SCC decomposition’.  		 			Jiri Barnat 		,  		 			Jakub Chaloupka 		.  	 	 		\textit{Journal of Logic and Computation}  		2011. 21  (1)  p. .  	 
\bibitem[Mark and Chu-Carroll]{b9}\label{b9} 	 		 			C Mark 		,  		 			Chu-Carroll 		.  		 \url{http://scienceblogs.com/goodmath/2007/10/computing\textunderscore strongly\textunderscore connected\textunderscore c}  		\textit{The website Science blog},  				p. .  	 
\bibitem[Gabow ()]{b3}\label{b3} 	 		‘Path-based depth first search strong and biconnected components’.  		 			H N Gabow 		.  	 	 		\textit{Information Processing Letters}  		2000. 74  (3-4)  p. .  	 
\bibitem[Easley and Kleinberg ()]{b8}\label{b8} 	 		\textit{Reasoning about a highly connected world, Textbook},  		 			David Easley 		,  		 			Jon Kleinberg 		.  		2010. Cambridge University Press.  	 
\bibitem[Skeina]{b15}\label{b15} 	 		 			Steven Skeina 		.  		 \url{http://www.cs.sunysb.edu/\textasciitilde algorith/implement/jdsl/implement.shtml}  		\textit{The Stony brook algorithm Repository},  				p. .  	 
\bibitem[Sedgewick and Wayne]{b5}\label{b5} 	 		\textit{The Text Book},  		 			Robert Sedgewick 		,  		 			Kevin Wayne 		.  		 	 	 (Algorith 4 th Edition http://algs4.cs.princeton.edu/ home/ retrieved on 04-2012) 
\bibitem[Steinhaus (2008)]{b6}\label{b6} 	 		\textit{The text book, Comparisons of mathematical programs for data Analysis},  		 			Stefan Steinhaus 		.  		July 2008.  	 
\bibitem[Marije De (2011)]{b4}\label{b4} 	 		\textit{Towards a Library of Parallel Graph Algorithm in Java, 14 th Twente Student conference on},  		 			Heus Marije De 		.  		January 21 st 2011.  	 
\end{bibitemlist}
 			 		 	 
\end{document}
