Closed michaelpj closed 5 years ago
@michaelpj Could you let me know why you'd like to use Relation
in particular? I was planning to remove Relation
from the library, because it doesn't seem to provide anything on top of AdjacencyMap
and is slower on most operations (although it may be worth double-checking using @nobrakal's benchmarks).
Answering your questions:
If you want a
Relation
, you should construct something polymorphically using the (non-higher-kinded)Graph
class, instantiated toRelation
.
Not necessarily: you can also use the Relation
API directly, e.g. Algebra.Graph.Relation.path
.
Relation
is not an instance of the higher-kindedGraph
class, I assume due to theOrd
constraint onconnect
and the fact thatSet
isn'tTraversable
.
Yes, that's right: both overlay
and connect
require the Ord
constraint. Do you necessarily need the higher-kinded Graph
type class?
The easiest way to fix this would just be to add a function that converts a
Graph
into aRelation
(ToGraph
exists, but it doesn't do the right thing, I think).
You are right, ToGraph
does not allow you to convert a Graph
into a Relation
. But it does allow you to convert a Graph
to an AdjacencyMap
. For example:
import qualified Algebra.Graph as G
import qualified Algebra.Graph.AdjacencyMap as AM
import qualified Algebra.Graph.ToGraph as T
g :: G.Graph Int
g = G.path [1..5]
am :: AM.AdjacencyMap Int
am = AM.path [1..5]
check :: Bool
check = (T.toAdjacencyMap g == am)
main :: IO ()
main = print check -- True
It's also pretty useful if you happen to have been given a (non-polymorphic)
Graph
and now you want to do construct the transitive graph or similar.
Aha! Are you using Relation
only to gain access to relational operations like transitiveClosure
? In this case, perhaps, adding these operations to AdjacencyMap
or even ToGraph
would be a better solution?
Yes, what I really want is transitiveClosure
. If I can get that without Relation
I'd be very happy! My assumption was that Relation
was the intended way to do it.
@michaelpj I see, thank you. I've edited the title of the issue.
Relation
appeared together with AdjacencyMap
when I was exploring possible traditional (non-algebraic) representations for graphs, but over time I found AdjacencyMap
easier to work with. I think it doesn't make sense to maintain both in the library in the long term.
Sounds very reasonable to me.
I guess my documentation comment is that at the moment the various graph representations support sightly different sets of algorithmic operations, and it's a little hard to tell which to use!
Yes, indeed. I will add a top-level description of various graph representations available in the library and the intended way of using them.
@michaelpj I've added implementations of relational operations (compose
, closure
, reflexiveClosure
, symmetricClosure
, transitiveClosure
) to adjacency maps (#146), and provided a brief overview of available adjacency maps flavours to the top-level Hackage description.
I plan to release 0.3
within a few days.
Feel free to reopen if I missed anything.
Great, thanks! I'll try and take a moment to update us to 0.3 when you release it and check out the new stuff.
As I understand it, at the moment the following things are true:
Relation
, you should construct something polymorphically using the (non-higher-kinded)Graph
class, instantiated toRelation
.Relation
is not an instance of the higher-kindedGraph
class, I assume due to theOrd
constraint onconnect
and the fact thatSet
isn'tTraversable
.Consequently, if you want to use the higher-kinded
Graph
class to construct your graph, you can't use it to make aRelation
.The easiest way to fix this would just be to add a function that converts a
Graph
into aRelation
(ToGraph
exists, but it doesn't do the right thing, I think). While somewhat wasteful, I think it would be handy. It's also pretty useful if you happen to have been given a (non-polymorphic)Graph
and now you want to do construct the transitive graph or similar.