Is there a reason why graphs in fgl are labeled by default, and unlabelled graphs must be constructed by labeling with () ? In my opinion the more natural design would be to number the nodes and edges with an Enum type instead of Int and to retrieve the labels from an array. This would support the "from simple to complex" design.
Henning Thielemann wrote:
Is there a reason why graphs in fgl are labeled by default, and unlabelled graphs must be constructed by labeling with () ? In my opinion the more natural design would be to number the nodes and edges with an Enum type instead of Int and to retrieve the labels from an array. This would support the "from simple to complex" design.
The design of the fgl could be improved. Labels for nodes (only) are (also) supported by Data.Graph.Inductive.NodeMap. (Keeping just a list of edges makes it difficult - leaves it to the user - to find certain edges after insertions or deletions) Sometimes the "from simple to complex"-design contradicts the possibility of reuse by generalizations, though. Cheers Christian
On Thu, 14 Feb 2008, Christian Maeder wrote:
Henning Thielemann wrote:
Is there a reason why graphs in fgl are labeled by default, and unlabelled graphs must be constructed by labeling with () ? In my opinion the more natural design would be to number the nodes and edges with an Enum type instead of Int and to retrieve the labels from an array. This would support the "from simple to complex" design.
The design of the fgl could be improved. Labels for nodes (only) are (also) supported by Data.Graph.Inductive.NodeMap.
I was not aware of NodeMap so far. It seems to add a mapping from labels to nodes, whereas node labels (that is mappings from Node to a Label of arbitrary type) are already provided by the Data.Graph.Inductive.Graph.Graph type constructor class and the type concrete Data.Graph.Inductive.Tree.Gr type constructor. A graph type is 'gr a b', but 'a' is not an index type. The nodes are indexed by Node which is a synonym for Int. For the tasks I had so far there was no need for the label type 'a', I just needed a more specific index type than Node (=Int), say an enumeration. The library designer seems to appreciate that applications may not need the labels, and provided functions like mkUGraph and type synonyms like Data.Graph.Inductive.Tree.UGr = Gr () (), which seems for me the wrong way around. It would be simple to add labels to an arbitrary indexed but unlabeled graph, say Ix i => gr i.
(Keeping just a list of edges makes it difficult - leaves it to the user - to find certain edges after insertions or deletions)
Henning Thielemann wrote:
'gr a b', but 'a' is not an index type. The nodes are indexed by Node which is a synonym for Int. For the tasks I had so far there was no need for the label type 'a', I just needed a more specific index type than Node (=Int), say an enumeration. The library designer seems to appreciate that applications may not need the labels, and provided functions like mkUGraph and type synonyms like Data.Graph.Inductive.Tree.UGr = Gr () (), which seems for me the wrong way around. It would be simple to add labels to an arbitrary indexed but unlabeled graph, say Ix i => gr i.
I agree that Ix (or only Ord) may be desirable as node types, but still some applications may need more sophisticated labels or may want to change the labels associated to nodes. For these cases I don't see how you get rid of specializations to "()" without duplicating the library. Christian
On Thu, 14 Feb 2008, Christian Maeder wrote:
Henning Thielemann wrote:
'gr a b', but 'a' is not an index type. The nodes are indexed by Node which is a synonym for Int. For the tasks I had so far there was no need for the label type 'a', I just needed a more specific index type than Node (=Int), say an enumeration. The library designer seems to appreciate that applications may not need the labels, and provided functions like mkUGraph and type synonyms like Data.Graph.Inductive.Tree.UGr = Gr () (), which seems for me the wrong way around. It would be simple to add labels to an arbitrary indexed but unlabeled graph, say Ix i => gr i.
I agree that Ix (or only Ord) may be desirable as node types, but still some applications may need more sophisticated labels or may want to change the labels associated to nodes.
No problem. If the node labels are in a separate array you can even do in-place updates in ST monad.
For these cases I don't see how you get rid of specializations to "()" without duplicating the library.
The library could provide a record like LabeledGraph i nodeLabel edgeLabel = LG (Gr i) (Array i nodeLabel) (Map (i,i) edgeLabel) with the interface that is now used for (Graph gr). However, I suspect that finding the label for an edge is then less efficient then now.
Henning Thielemann wrote:
The library could provide a record like
LabeledGraph i nodeLabel edgeLabel = LG (Gr i) (Array i nodeLabel) (Map (i,i) edgeLabel)
with the interface that is now used for (Graph gr). However, I suspect that finding the label for an edge is then less efficient then now.
Interesting, the nodeLabel bit looks good (although I would use a "Map i nodeLabel"). Considering that "Gr i" is also implemented as something like "Map i <Context>" the structure is already duplicated, although keeping the separate node labels in sync is fairly easy and maybe the price for the added value (namely node labels). In particular during decomposing the graph the node-label-map does not need to be changed (although lookups may be faster in smaller maps). W.r.t edge labels more needs to be done: 1. there may be several edges between a node pair 2. Getting a whole context (all in- and outgoing labelled edges) of a node is less efficient (as you said above) 3. Some identity of edges (i.e. a unique number, apart from the label) is desirable, to locate or (re-)insert/delete certain edges. W.r.t to the fgl-Design I would more complain about the many type synonyms for tuples instead of using new (algebraic data) types. Also wrapper types are an idea to keep the general implementation but present a simplified interface to users of unlabeled graphs. Cheers Christian
participants (2)
-
Christian Maeder -
Henning Thielemann