haskell / fgl Goto Github PK

Documentation says this:

  -- | Merge the 'Context' into the 'DynGraph'.
  --
  --   Contexts should only refer to either a Node already in a graph
  --   or the node in the Context itself (for loops).

Without looking at an implementation it's not clear to me what what does "merge" mean in this context. I think this could use more sentences. More specifically, I think it's worth adding that merge is for adding new stuff and updating labels, and it's not possible to remove an edge using it. Also, when a new edge A -> B added using this, predecessors of B is automatically updated.

Since DynGraph is a typeclass I think these should be specified so that using a different implementation would not break the program

Daniel Martin discovered that insEdges is not being properly specialized, and therefore the insEdge rewrite rule for Patricia trees is not firing. The fix was to mark insEdges INLINABLE. I would also recommend marking insEdge NOINLINE [0] or similar to make sure it doesn't inline prematurely and hide from the rule.

The original paper discusses an inductive Graph implementation based on "version tree" based arrays. I believe this was implemented in ML. Has there been any attempt to compare the performance of such an implementation in Haskell, perhaps using a library like this one? https://hackage.haskell.org/package/persistent-vector

xdfsWith allows to specify suc' or pre' when performing the search.

bfs is currently only possible with hard coded suc'

let's add an arg to bfsnInternal which allows to choose suc' or pre' with bfs?
let's add xbfsnWith, too.

ghc-7.0.4: http://hydra.cryp.to/build/994563/log/raw
ghc-7.2.2: http://hydra.cryp.to/build/994341/log/raw

The problem seems to be:

Data/Graph/Inductive/PatriciaTree.hs:115:16:
    Could not deduce (NFData (GraphRep a b))
      arising from a use of `rnf'
    from the context (NFData a, NFData b)
      bound by the instance declaration
      at Data/Graph/Inductive/PatriciaTree.hs:114:10-48
    Possible fix:
      add (NFData (GraphRep a b)) to the context of
        the instance declaration
      or add an instance declaration for (NFData (GraphRep a b))
    In the expression: rnf g
    In an equation for `rnf': rnf (Gr g) = rnf g
    In the instance declaration for `NFData (Gr a b)'

The documentation for DFS states the prefix for unidirectional functions is 'x', when it should be 'u'.

Diff of src/Data/Graph/Inductive/Query/DFS.hs:

< --      [@x@] undirectional: ignore edge direction

---
> --      [@u@] undirectional: ignore edge direction

Insertion, for example, should be able to use the ill-named differenceWithKey function. First, form a map consisting of operations to perform on predecessor/successor nodes; then use differenceWithKey to perform them. When inserting nodes with many predecessors/successors, this should be faster than modifying them all sequentially. The mergeWithKey function would probably be more appropriate, but I hope to deprecate that eventually in favor of a safer variation on the theme.

Currently the closest thing to tests is a bunch of pre-defined graphs in the Examples module and in the test/ directory.

...which ideally features at least a Hackage badge as well as a Travis badge, see
https://github.com/haskell/deepseq for an example

They are not even remotely legitimate and there should never be any reason to use them. IMO, they should be removed promptly in the next major version.

Data.Graph.Inductive.Internal.Queue isn't efficient for persistent use. It would be easier to ensure that it's not accidentally used persistently if it's given a monadic interface. It should probably also be benchmarked against other queue implementations, such as Control.Monad.Queue.Corec from control-monad-queue, my own considerable simplification thereof, or perhaps something fancier in ST.

In the module Data.Graph.Inductive.Query.TransClos, the function rc has the following description:

Finds the reflexive closure of a directed graph.
Given a graph G=(V,E), its transitive closure is the graph:
G* = (V,Er union E) where Er = {(i,i): i in V}

However, its implementation of the function rc is:

rc :: (DynGraph gr) => gr a b -> gr a ()
rc g = newEdges `insEdges` insNodes ln empty
  where
    ln       = labNodes g
    newEdges = [ (u, u, ()) | (u, _) <- ln ]

This very obviously computes the graph (V, Er), using the previous notation.

Proposed solution: replace the code with:

rc :: (DynGraph gr) => gr a b -> gr a ()
rc g = (newEdges ++ oldEdges) `insEdges` insNodes ln empty
  where
    ln       = labNodes g
    newEdges = [ (u, u, ()) | (u, _) <- ln ]
    oldEdges = [ (u, v, ()) | (u, v, _) <- labEdges g ]

I am following this issue with the corresponding PR.

Could we please have some traversals (lenses)? This is the entire implementation. It doesn't depend on anything outside FGL and base.

I'm happy to submit this as a PR if you guarantee you'll accept it.

module Data.Graph.Inductive.Lens
       ( traverseNodes
       , traverseEdges ) where

import           Control.Applicative        ((<$>), (<*>), pure, Applicative)
import qualified Data.Graph.Inductive.Graph as FGL
import           Data.Graph.Inductive.Graph ((&))
import qualified Data.Traversable           as T

-- | Walk all nodes in the graph in the order they were created
traverseNodes :: (FGL.DynGraph gr, Applicative f)
              => (a -> f a')
              -> gr a b
              -> f (gr a' b)
traverseNodes f = FGL.ufold (mergeNode f) (pure FGL.empty)

mergeNode :: (Applicative f, FGL.DynGraph gr)
          => (a -> f a')
          -> FGL.Context a b
          -> f (gr a' b)
          -> f (gr a' b)
mergeNode f (adj, node, a, adj') g =
  (\a' g' -> (adj, node, a', adj') & g') <$> f a <*> g

-- | Walk all edges in the graph in the order they were created
traverseEdges :: (FGL.DynGraph gr, Applicative f)
              => (b -> f b')
              -> gr a b
              -> f (gr a b')
traverseEdges f g = FGL.ufold (mergeEdge f) (pure FGL.empty) g

mergeEdge :: (Applicative f, FGL.DynGraph gr)
          => (b -> f b')
          -> FGL.Context a b
          -> f (gr a b')
          -> f (gr a b')
mergeEdge f (adj, node, a, adj') g =
  (\adj1 g' adj1' -> (adj1, node, a, adj1') & g')
      <$> (T.traverse . _1) f adj
      <*> g
      <*> (T.traverse . _1) f adj'

_1 :: Functor f => (a -> f a') -> (a, b) -> f (a', b)
_1 f (a, b) = (\a' -> (a', b)) <$> f a

Since it is not really possible to know before hand if a ++ b is faster than b ++ a, it might be better to use Data.Sequence.

This change can improve fgl's (&) performance from O(n) to potentially O(1), without loss of generality or ease of use.

I noticed this when the following change reduced my memory usage by half:
wuerges/vlsi_verification@45e7c30?diff=unified#diff-014d188201674e3d3062b5a764945832

This is due to fastInsEdge being implemented with addLists instead of (++)

I could evaluate this because my particular Graph has a huge amount of inn edges for each node and at most 2 out edges. The change above only made any difference in memory consumption when changing the input edge list, not the output.

It would be handy for the documentation to confirm the expected time and space complexity of the functions in fgl. Given that all the functions operate over instances of Graph (and friends) rather than concrete types these bounds might have to be given in terms of the number of calls the Graph's member functions, or given in terms of an idealized implementation of Graph.

This is particularly useful given the relative complexity of determining this information in Haskell.

The prettyPrint function drops any outgoing edge that it encounters "out of order":

*Main> import qualified Data.Graph.Inductive as G
*Main G> import qualified Data.Graph.Inductive.PatriciaTree as Pt
*Main G Pt> G.prettyPrint (G.mkGraph [(x, ()) | x <- [0..6]] [(0,6,()),(2,1,()),(3,2,()),(4,3,()),(5,4,()),(6,5,())] :: Pt.Gr () ())
0:()->[((),6)]
1:()->[]
2:()->[]
3:()->[]
4:()->[]
5:()->[]
6:()->[]

This makes it nearly useless for debugging most complicated graphs, and the only graphs it can even possibly print correctly are DAGs.

I'm writing some tests for my code which relies on fgl, and the Arbitrary instance for graphs is very helpful. I've got this repository subtreed into my own so I can use it, but it would be nice to get fgl-arbitrary through Hackage instead.

Just a heads-up that fgl fails to build with ghc-8.6.1:

Data/Graph/Inductive/Monad.hs:59:36: error:
    • Could not deduce (Control.Monad.Fail.MonadFail m)
        arising from a do statement
        with the failable pattern ‘(Just c, g')’
      from the context: GraphM m gr
        bound by the class declaration for ‘GraphM’
        at Data/Graph/Inductive/Monad.hs:42:20-25
      Possible fix:
        add (Control.Monad.Fail.MonadFail m) to the context of
          the type signature for:
            matchAnyM :: forall a b. m (gr a b) -> m (GDecomp gr a b)
          or the class declaration for ‘GraphM’
    • In a stmt of a 'do' block: (Just c, g') <- matchM v g
      In the expression:
        do (Just c, g') <- matchM v g
           return (c, g')
      In a case alternative:
          (v, _) : _
            -> do (Just c, g') <- matchM v g
                  return (c, g')
   |
59 |                      (v,_):_ -> do (Just c,g') <- matchM v g
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^

Take the following example:

test :: Gr Int String
test = insEdge (0,1,"foo") (mkGraph [] [])

An evaluation attempt of test throws the following exception:

mkGraph *** Exception: Data/Graph/Inductive/Graph.hs:229:5-38: Irrefutable pattern failed for pattern (Just (pr, _, la, su), g')

The reason this is being thrown is because the vertex indexed with 0 does not exist in the graph I am trying to insert the edge into:

-- | Insert a 'LEdge' into the 'Graph'.
insEdge :: (DynGraph gr) => LEdge b -> gr a b -> gr a b
insEdge (v,w,l) g = (pr,v,la,(l,w):su) & g'
  where
    (Just (pr,_,la,su),g') = match v g

I'll send a pull request to add an informative error message in this case.

In the case of vertices representing cities and edges representing roads. There are multiple edges between cities representing different route possibilities. Shortest path just gives me a list of nodes and there's no way to discover which edges are involved in the route from a list of nodes.

When adding a Context with the (&) operator to an existing graph, it seems as if incoming edges are silenty dropped if the edge references a node that is not yet in the graph. However, if the outgoing edge is referencing a node that is not yet in the graph, the edge is retained. This behaviour seems inconsistent to me.

Example:

> (([((), 1)], 2, (), [((), 3)]) & empty :: Gr () ())
mkGraph [(2,())] [(2,3,())]

Here, the edge from 2 to 3 is in the graph, the edge from 1 to 2 isn't. Even after adding node 1 into the graph, the information is lost:

> insNode (1, ()) $ (([((), 1)], 2, (), [((), 3)]) & empty :: Gr () ())
mkGraph [(1,()),(2,())] [(2,3,())]

If this behaviour is by intent, it should be at least documented.

According to the documentation of undir, we get:

"Make the graph undirected, i.e. for every edge from A to B, there exists an edge from B to A."

My expectation would be that if a graph has an edge from C to C, then well, in undirected form it will still have an edge from C to C, and that's it (concerning that self-edge). Except, I noticed something different. Here is a piece of code I had, with printing added for debugging:

  print theNodes
  print theEdges
  let numberedNodes = zip [0..] theNodes
  let graph = undir (mkGraph numberedNodes theEdges) :: Gr String String
  print graph

And here is the printed output:

["D$0","D$1","B$0","A$0"]
[(3,3,"y"),(3,0,"z"),(3,1,"z")]
mkGraph [(0,"D$0"),(1,"D$1"),(2,"B$0"),(3,"A$0")] [(0,3,"z"),(1,3,"z"),(3,0,"z"),(3,1,"z"),(3,3,"y"),(3,3,"y")]

Note the double occurrence of (3,3,"y") in there.

I get how the edges (3,0,"z"),(3,1,"z") before undir turn into (0,3,"z"),(1,3,"z"),(3,0,"z"),(3,1,"z") after it.

But why was the original edge (3,3,"y") duplicated into (3,3,"y"),(3,3,"y")? That seems uncalled for (and led to a wrong picture when feeding this graph into GraphViz).

Some RULES pragmas are used to specialize functions to specific graph implementations. I believe most or all of these could be eliminated by adding the relevant functions to Graph or DynGraph. If you are concerned that some of them may not really belong in the API, and don't know what user-friendly methods to add to support them, you can hide those methods by defining the class in an "internal" module, and only export some of its methods. Using the class system instead of rules, when possible, guarantees that the preferred implementation will always be used.

I just discovered that there is a class for monadic graphs, but there is only an IO based representation. I propose to add a more general implementation based on MArray that'd allow both IO and ST based representations. In particular the ST version would allow high performance while keeping results pure.

If this make sense, I'll be happy to eventually contribute this.

You can get a Data/Graph/Inductive/NodeMap.hs:159:9-32: Non-exhaustive patterns in Just es' with fgl-5.7.0.1.

Hi -

I've noticed that fgl behaves in unexpected ways for edges from vertices not in the vertex list.

For example, at the repl:

> import Data.Graph.Inductive.Graph as Graph
> import Data.Graph.Inductive.PatriciaTree (Gr)
> let g = Graph.mkGraph [(1,())] [(1,2,True), (2,1,False)] :: Gr () Bool
> g 
mkGraph [(1,()] [(1,2,True)] -- The edge (2,1,False) has disappeared.
> let g' = Graph.insNode [(2,())] g
> g'
mkGraph [(1,()), (2,())] [(1,2,True)] -- Just as we expect, the edge (2,1,False) is absent.
> Graph.delEdge (1,2) g'
mkGraph [(1,()), (2,())] [(2,1,False)] -- What!?!?! The edge (2,1,False) mysteriously reappeared!

Having mkGraph ignore edges from vertices not in the vertex list is fine. However, once those edges have been thrown away, they shouldn't come back unexpectedly.

NodeMap only allows insertion of nodes with automatic duplicate prevention. It does not support checking whether a node exists or reporting whether mkNode actually created a new node, though this feature should be easy to add.

Some graph construction algorithms involve inserting some initial nodes to an empty graph and operating recursively on newly-inserted nodes, where the recursion generates additional nodes to insert. If a generated node already exists in the graph, the algorithm does not recurse into it, so the algorithm needs to know whether a generated node already exists.

NodeMap doesn't support this use case. It can be supported by a variant of mkNode that additionally returns a boolean indicating whether the node already existed or was newly inserted. Another approach is to add a lookupNode function, which though more general, may be less performant because then when processing a new node (not yet inserted into the graph) there will be two lookups instead of one, one lookup from lookupNode and one lookup from mkNode.

I believe we should offer

freezeGraph :: (GraphM m mg, Graph g) => mg a b -> m (g a b)
thawGraph :: (GraphM m mg, Graph g) => g a b -> m (mg a b)

Hello,
looking at the Martin Erwigs' paper and the code in this repo, I do not see a function that would return the label of LEdge given the graph and the Edge. It is a basic function so I wonder if it was somewhere already.

More precisions about such function (label for edge):
label':: gr a b -> Edge -> Maybe b
Given a Graph and an Edge, gives the label of the edge if it exists.

I wonder if the NodeMap file tries to provide such utility.
Many thanks in advance for your help dealing with such a basic question.
By the way many thanks for maintaining this wonderful library.

The function "trc" in module TransClos computes the transitive, reflexive closure of a graph, rather than merely the transitive closure. The difference is acute when dealing with directed acyclic graphs: the transitive closure of a DAG should also be a DAG, but the transitive, reflexive closure will not be.

The reason this happens is because "trc" invokes a function that invokes "reachable", and the first element of the list returned by "reachable" is the node itself.

The comment documentation says that "trc" only computes the "transitive closure". I am happy to submit a pull request with my versions of these functions that separate transitive closure from reflexive closure. But I would like to know the naming convention desired here. It occurs to me that the name "trc" could stand for either "TRansitive closure" or "Transitive Reflexive Closure". The test cases in the library seem to assume that "trc" computes the transitive, reflexive closure. So perhaps it is best to leave "trc" as "Transitive Reflexive Closure", update the documentation, and create a new function for "Transitive Closure" (tentatively named "tc").

What do you think?

I expected the following two functions to be equivalent but ufold gives strange answers. Specifically, the context was missing self-loops and incoming edges, am I misusing ufold here?

consistency :: DTMC -> Maybe Node
consistency dtmc =
  foldr (\n c ->
    if sum (map edgeLabel (out dtmc n)) == 1
      then c
      else (Just n)) Nothing

consistency :: DTMC -> Maybe (Context [String] Rational)
consistency =
  ufold (\context c ->
    if sum (map edgeLabel (out' context)) == 1)
      then c
      else (Just context)) Nothing

Is there a some canonical way to enforce graph invariants in FGL?

I have been using FGL to implement a generalization of graphs that allows for arbitrary arity and nesting of relationships. It looks like this:

type RSLT = Gr Expr Role
data Expr = Word String
          | Template [String] -- e.g. "_ needs _ to _"
          | Relationship      -- e.g. "Gotham needs Batman to hurry"
data Role = TemplateRole | Member Int

Words and Templates emit no edges. Each Relationship emits an edge labeled "TemplateRole" to a Template of arity k, and k more edges, labeled "Member i" for i in [1,k]. Thus the model permits lots of invalid state.

I don't know whether it's relevant, but I just learned about the dependent map library, which implements a map that allows keys to specify the types of values associated with them.

I am using fgl as dependency in this project:

https://github.com/danfran/cabal-macosx/blob/master/cabal-macosx.cabal

On travis all the builds run successfully apart for GHC 7.0.4 and 7.2.2. The issue seems related to:

Downloading fgl-5.5.3.1...
Configuring fgl-5.5.3.1...
Building fgl-5.5.3.1...
Preprocessing library fgl-5.5.3.1...
[ 1 of 29] Compiling Paths_fgl        ( dist/build/autogen/Paths_fgl.hs, dist/build/Paths_fgl.o )
[ 2 of 29] Compiling Data.Graph.Inductive.Internal.Thread ( Data/Graph/Inductive/Internal/Thread.hs, dist/build/Data/Graph/Inductive/Internal/Thread.o )
[ 3 of 29] Compiling Data.Graph.Inductive.Graph ( Data/Graph/Inductive/Graph.hs, dist/build/Data/Graph/Inductive/Graph.o )
Data/Graph/Inductive/Graph.hs:132:3: Unrecognised pragma
[ 4 of 29] Compiling Data.Graph.Inductive.Basic ( Data/Graph/Inductive/Basic.hs, dist/build/Data/Graph/Inductive/Basic.o )
[ 5 of 29] Compiling Data.Graph.Inductive.PatriciaTree ( Data/Graph/Inductive/PatriciaTree.hs, dist/build/Data/Graph/Inductive/PatriciaTree.o )
Data/Graph/Inductive/PatriciaTree.hs:276:30:
    Not in scope: `IM.foldlWithKey''
Data/Graph/Inductive/PatriciaTree.hs:290:30:
    Not in scope: `IM.foldlWithKey''
Failed to install fgl-5.5.3.1

I assume that a way could be using "-f -containers042" for that versions but I have tried this on travis without any luck:

if [ $GHCVER = "7.0.4" ] || [ $GHCVER = "7.2.2" ];
     then
          cabal install --only-dependencies --enable-tests --enable-benchmarks -f -containers042;
     else
          cabal install --only-dependencies --enable-tests --enable-benchmarks;
     fi

as the flag is disabled only on the current cabal instance (not for dependencies).

Any idea how to use fgl as dependency with GHC 7.0.4 and 7.2.2?

The documentation for the latest version of this package is missing on Hackage. They've been pending on Hackage for some time, this usually indicated that Hackage wasn't able to build the package.

Is it possible for you to manually upload the package using cabal upload --doc, please?

Thanks!

I noticed #19, and currently fgl.cabal contains

    build-depends:    base < 5
                    , transformers
                    , containers
                    , array

    if impl(ghc >= 7.4)
       build-depends:
            deepseq >= 1.1.0.0 && < 1.5.0.0

However this underspecified, as in the ghc>=7.4 you clearly require also containers >= 0.4.2, so a better fix would be e.g

    build-depends:    base < 5
                    , transformers
                    , containers >= 0.4.2
                    , array
                    , deepseq >= 1.1.0.0 && < 1.5

or alternatively (but this leaves us with an API that conditionally provides the NFData feature depending on the containers version):

flag containers042
   manual: false
   default: true

library
-- ....
    build-depends:    base < 5
                    , transformers
                    , containers
                    , array

    if flag(containers042)
       build-depends:
            containers >= 0.4.2
            deepseq >= 1.1.0.0 && < 1.5
    else
       build-depends: containers < 0.4.2

PS: it's unsound to write an upper bound with trailing zeroes like <1.5.0.0 since 1.5 < 1.5.0 < 1.5.0.0

The gfiltermap function shows unexpected (for me, at least) behaviour. Its description: "Build a graph out of the contexts for which the predicate is true.", where context is represented by type Context, which is documented as follows: "Links to the Node, the Node itself, a label, links from the Node."

Given these descriptions, I would expect that for every node I get its predecessors and successors in the context. This does not appear the case in the example below:

{-# LANGUAGE TupleSections #-}

module Test where

import Debug.Trace
import Data.Graph.Inductive

main :: IO ()
main = prettyPrint test

test :: Gr () ()
test = gfiltermap filterGraph testGraph
  where
  filterGraph = Just . traceShowId
{-
 - 1 <-4<-- 2
 - /\    -/|
 -  \    /
 -   \3\/_
 -}
  testGraph = mkGraph testNodes testEdges
    where
    testNodes = map (,()) [1, 2, 3, 4]
    testEdges = [ (2, 4, ())
                , (4, 1, ())
                , (2, 3, ())
                , (3, 1, ())
                , (3, 2, ())
                ]

Executing main gives the following output, where the first four lines are the output from traceShowId and the last four lines the output of prettyPrint:

([((),3),((),4)],1,(),[])
([((),3)],2,(),[((),3),((),4)])
([],3,(),[])
([],4,(),[])

1:()->[]
2:()->[((),3),((),4)]
3:()->[((),1),((),2)]
4:()->[((),1)]

While the code faithfully reconstructs the original graph (as is also tested in the test suite), the trace output shows some strange behaviour. For example, I would expect node 4 to have node 1 and node 2 in its context, but its context is empty.

So, either gfiltermap has a bug, in which case it would be great if that could be fixed. Or gfiltermap's documentation should possibly be updated to reflect gfiltermap's current behaviour.

I am using revision 71b66d6.

Please raise the upper bound on QuickCheck to allow for QuickCheck 2.12.6.1

microbench "insEdge into AVL tree" insEdgeAVL
microbench "emap on AVL tree" emapAVL

We get

    * insEdge into AVL tree: .fgl-benchmark: insEdge: cannot add edge from non-existent vertex 1

and

    * emap on AVL tree: .fgl-benchmark: insEdge: cannot add edge from non-existent vertex 1

It should be possible to unify the IO and ST support, and indeed expand support to other PrimMonad instances.

Citing from http://hydra.cryp.to/build/943341/log/raw:

Data/Graph/Inductive/Arbitrary.hs:40:70:
    Module ‘Data.Graph.Inductive.Graph’ does not export ‘toEdge’

Is there any chance that numNodes could be added as a synonym for noNodes (and perhaps noNodes deprecated)?

noNodes really looks like "no nodes" and intuitively seems to suggest a Bool valued function which tells you whether there are no nodes in the graph!

GHC 8.6.1-beta1 enables the MonadFailDesugaring language extension by default as part of the migration plan for the MonadFail proposal. Currently fgl doesn't build with this new extension enabled:

        • Could not deduce (Control.Monad.Fail.MonadFail m)
            arising from a do statement
            with the failable pattern ‘(Just c, g')’
          from the context: GraphM m gr
            bound by the class declaration for ‘GraphM’
            at Data/Graph/Inductive/Monad.hs:42:20-25
          Possible fix:
            add (Control.Monad.Fail.MonadFail m) to the context of
              the type signature for:
                matchAnyM :: forall a b. m (gr a b) -> m (GDecomp gr a b)
              or the class declaration for ‘GraphM’
        • In a stmt of a 'do' block: (Just c, g') <- matchM v g
          In the expression:
            do (Just c, g') <- matchM v g
               return (c, g')
          In a case alternative:
              (v, _) : _
                -> do (Just c, g') <- matchM v g
                      return (c, g')
       |
    59 |                      (v,_):_ -> do (Just c,g') <- matchM v g

Ideally this would get fixed before the upcoming GHC 8.6.1 release.

I have recently read Martin Erwig's papers and looked over the fgl library. The graphs are backed by a Patricia tree through Data.IntMap which, as far as I can tell, defaults to Data.IntMap.Lazy.

I am currently considering porting parts of the fgl to another functional language that is strict by default, so I was wondering if the performance hinges on the lazy implementation or not? None of the papers mention laziness as a requirement for the backing data structure or even for the graph's implementation language, but I can understand why it would be the default in a language like Haskell.

Hi there, I seem to be getting loops in graphs when I use the NoLoops newtype.

for example:

someTest :: NoLoops Gr () () -> Bool
someTest (NL g) = ...

yields:

*** Failed! Exception: 'Prelude.head: empty list' (after 7 tests):       
NL {looplessGraph = mkGraph [(-3,()),(1,())] [(-3,1,()),(1,-3,()),(1,-3,())]}

I don't have a cycle finder to hand so I can't test it properly, but this particular graph does seem to contain a cycle to me.

The implementation of Eq of LPath is only looking at the first label in non-empty path here. This leads to incorrect results when comparing paths longer than 1, e.g.

GHCI> LP [(1,'a'),(2,'b')] == LP [(1,'a'),(2,'c')]
True

I believe the non-empty path case should be changed to something like:
(LP ((_,x):xs)) == (LP ((_,y):ys)) = x==y && LP xs == LP ys

There's similar problem with Ord instance.

_Is it possible to serialize / deserialize graph and nodemap to / from ByteString?

If not, is it possible to add this feature?_

figured it out. can use Data.Binary encode / decode

Is there really no way of counting edges in a graph? Graph has the noNodes method but there seems to be nothing corresponding to the number of edges. I hacked together this

noEdges :: FGL.Graph gr => gr a b -> Int
noEdges = FGL.ufold (\(a, _, _, a') i -> i + length a + length a') 0

but surely this functionality should be exposed from the library?

The Graph typeclass forces Node to be an alias to Int. Is there any way to overcome this?

fgl specifies hspec <2.4, but the current platform uses hspec =2.4 and jailbreaking fgl succeeds.