fgl uses pretty much the most beautiful way of abstracting graphs I&#39;ve seen; a brief review:<br><br>type Context a b -- a collected representation of a vertex&#39;s number, label, and all information on edges going into and out of that vertex<br>

<br>match :: Graph gr =&gt; Node -&gt; gr a b -&gt; (Maybe (Context a b), gr a b)<br>-- if a vertex is in the graph, extracts its adjacency information in a Context and returns the graph without that vertex<br><br>(&amp;) :: DynGraph gr =&gt; Context a b -&gt; gr a b -&gt; gr a b<br>

-- melds a vertex and its adjacency&nbsp; information into the graph<br><br>I&#39;ve been doing a huge amount of messing around with graph algorithms recently, and this inductive style of graph querying and modification make several algorithms far more intuitive than most imperative implementations I&#39;ve seen.&nbsp; In addition, both of these lend themselves well to use in a State monad.&nbsp; Take the following code to extract the connected component of a vertex in an undirected graph:<br>
<br>
extractComponentM :: DynGraph gr =&gt; gr a b -&gt; Node -&gt; State (gr a b) (gr a b)<br>extractComponentM partialComponent v = State (match v) &gt;&gt;= maybe (return partialComponent) expandContext where<br>&nbsp;&nbsp;&nbsp; expandContext cxt = liftM (cxt &amp;) (foldM extractComponentM partialComponent (neighbors&#39; cxt))<br>
<br>extractComponent :: DynGraph gr =&gt; gr a b -- the initial graph<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; -&gt; Node -- the node whose component to find<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; -&gt; (gr a b, gr a b) -- the original graph without the component, and the component<br>
extractComponent g v = runState (extractComponentM empty v) g<br><br>That&#39;s far more compact -- and intuitive to someone familiar with both fgl and the State monad -- than a standard connected-component finder in an imperative language, speaking as someone who wrote code along these lines imperatively for several years.&nbsp; (Fun fact: I&#39;ve been working on a nice encapsulation of priority queues as monad transformers to make other common graph algorithms both efficient and make them this pretty to read, too.&nbsp; Any thoughts on that would be appreciated.)<br>
<br>I strongly feel that fgl, though it could be improved in some areas, makes a better truly general graph abstraction than anything else I&#39;ve seen.&nbsp; Areas that could specifically be improved include the stuff that uses LRTrees, and other stuff that isn&#39;t especially intuitive, elegant, or even efficient in fgl&#39;s implementation.<br>
<br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br>