Ivan Lazar Miljenovic schrieb:
Pros for allowing you to use a custom node type: * Matches your data better * No need for extra lookup maps when converting your data to FGL form
Cons: * Makes type-sigs uglier/more verbose
Unlabelled graphs with custom node type would have only one type parameter. :-)
* Restricts the ability to optimise
That's my question. As far as I know the set of node identifiers in a graph is not contiguous, thus you cannot use Arrays but you must use IntMap or so.
Using Int gives us a fixed-size data type with known good comparison performance and with a range that should suit most purposes.
Replacing IntMap by Map is not much slower, is it?
As an alternative, see how I have Graphalyze create an FGL graph from [n] and [(n,n,e)]: http://hackage.haskell.org/packages/archive/Graphalyze/0.9.0.0/doc/html/Data...
We're also considering using MPTCs or ATs to let you place restrictions on the label types (when defining a new graph instance). However, before you again state how you don't want labels, consider this:
* It's easier to make a labelled graph act as an unlabelled one than the other way around.
Sure, it's the same argument that in MatLab everything is a complex-valued matrix. They even represent Bool by a 1x1 complex-valued matrix. Possible, but clean? From today's viewpoint separation of labelled and unlabelled graphs is additional work, but I'm afraid there will arise problems with this design. Unfortunately, I can't tell them today.
The current "type Node = Int" alias is only there to provide a unique index type for referencing nodes; the actual Ints don't really represent the nodes IMHO, the labels do (in conjunction with the index for colouring, etc.). In your example case of using PkgName (I assume you mean PackageName or PackageIdentifier?), can you guarantee that each PkgName value is unique before you go blindly using it (what about having the same library installed in both the global and user database?)?
Of course you must choose data as key, that is actually a key. But this is not the problem of FGL. And with Node = Int, I also have to choose a key for my dictionary (Map Something Node). In my case I consider packages that are to be installed, so no distinction between globally and locally installed packages. I want really the package name as key.