patrickdoc/hash-graph

A hashing-based graph implementation in Haskell

hash-graph's Issues

Duplicate information of node label

Hi,

It disturbed me since I read the code: the current implementation of graph is:

type GraphRep a b = HM.HashMap b (Context' a b)

data Context' a b = Context'
    { heads :: !(HS.HashSet (Head a b)) -- ^ Predecessors of the node
    , self  :: !b                       -- ^ The node label
    , tails :: !(HS.HashSet (Tail a b)) -- ^ Successors of the node
} deriving (Eq, Generic, Show)

So the node label is stored two times: one as a key in the HashMap, one in the Context'.

Is this really needed ? I tried to remove the self record of Context' and successfully (it build and the semantic only changed for some functions, I certainly made mistakes) did it (only for the Data.HashGraph.Strict module), you can see the results here: nobrakal@82a676c

I don't do anything with algorithm implementation, but it can be certainly removed.

I know the definition of Context in the fgl paper include the node, but I think the real context can be viewed as the association key -> value in the HashMap.

What do you think ?

Add function for finding all possible paths from a given node

The Graphalyze library has the useful pathTree function, which finds all possible paths from a given node. It would be very useful to have such a function in Data.HashGraph.Algorithms.

This is connected to the currency exchange example from #3, where we could imagine having a graph consisting of the following edges:

[ SomeExchangeRate “EUR” “USD” 1.2
, SomeExchangeRate “USD” “GBP” 0.6
, SomeExchangeRate “EUR” “JPY” 136
, SomeExchangeRate “JPY” “GBP” 0.006
]

As we can see there are two possible paths from “EUR” to “GBP”: one through “USD” and one through “JPY” and — depending on the various exchange rates — one path might be more profitable than another.

HashMap.fromList speedup

HM.fromList offers a significant speedup over foldl' insert. I need to find an efficient way to convert from the user interface of Edge n1 label n2 to each node paired with all its half edges.

Definition of (&)

Hi,

Just saw the implementation of (&):

(&) :: (Eq a, Eq b, Hashable a, Hashable b) => Context' a b -> Gr a b -> Gr a b
(&) ctx@(Context' _ l _) g
    = if member l g
        then fromList ((l, ctx) : toList (delNode l g))
        else fromList ((l, ctx) : toList g)

And I came to a simpler one:

(&) :: (Eq a, Eq b, Hashable a, Hashable b) => Context' a b -> Gr a b -> Gr a b
(&) ctx@(Context' _ l _) (Gr g) = Gr $ HM.insert l ctx g

insert works in log(n) and replace an existing pair (key -> value) by the new one, like the actual definition.

It looks too simple, I am missing something ?

Currency exchange example

From Reddit:

Does this support finding all possible paths between two specific nodes, where each edge is represented by a Money.ExchangeRate src dst? I.e. can I use arbitrary types for defining edges and nodes?

I want to use an ExchangeRate src dst to represent a path from src to dst, but fgl forces me to reduce all nodes to an Int, which means I lose a lot of information, and it becomes non-obvious to me how to restore this if I use pathTree for finding paths (which returns just [Int]).

It's not really about type-level vs. value-level, though. So if it works for SomeExchangeRate that's more than fine, too.

This example is precisely the kind of thing that should benefit from hashing for information preservation.

Consider arbitrary edge types.

Upload to Hackage

Hi Patrick, nice library. Would you consider uploading your library to Hackage? This would make it a lot easier for others to use it.

Best,
Sven

Implementing transpose: are Head and Tail difference necessary ?

Hi,

I am trying to implement transpose (the function that invert all the edges of the graph) for my benchmarks.

I made:

transpose :: Gr () Int -> Gr () Int
transpose (Gr g) = Gr $ M.map (\(Context' h t) -> Context' (Set.map (\(Tail a b) -> Head a b) t) (Set.map (\(Head a b) -> Tail a b) h)) g

Basically, I am inverting heads and tails. But because there is a type difference between an Head and a Tail, I must convert them (and thus map into the two sets).

But:

data Head a b = Head !a !b deriving (Eq, Generic, Show)
data Tail a b = Tail !a !b deriving (Eq, Generic, Show)

They look very similar.

So two questions:

• Does my implementation of transpose is reasonable ?
• Does the difference between Head and Tail is deeper than just cosmetic ^^ ?

Edge arguments

Hi,

I want to benchmark hash-graph for the 2018 Google Summer of Code and I need to construct edges with Edge.

data Edge a b = Edge !b !a !b deriving (Eq, Generic, Show)

What is the purpose of the mid-term of type a ? Is it for labeled-graphs ? I saw you use it for the Ord instance, and your use of it in the benchmark suite is obscure to me...

Space improvements

The half edge type benefits greatly from unpacking on smaller types.

data Head a b = Head !a !b
data SmallHead = SmallHead !Char !Int

Due to -funbox-small-strict-fields, SmallHead will be 3 words, while Head Char Int will be 7. This benefit falls off for larger types, but should be exploited on common node and edge labels