|
To throw or not to throw (Jade.Ai.Graphs)
|
| Author |
Message |
Vicente
Administrator
Posts: 972
Group: Administrators
Joined: Sep 2006
Status:
Offline
|
To throw or not to throw (Jade.Ai.Graphs)
Hi,
these last days I've been working in the Jade.Ai.Graphs namespace. The code is based on the Boost Graph Library and another C# implemenation of it (Quickgraph, also in Codeplex).
Most of the code I wanted to write is now finished but I have one doubt about the implementation. I have an AdjacencyList class that represents a directed mutable graph with the following method (as an example):
public void AddEdge(TEdge edge)
{
List<TEdge> edges;
if (!_vertexOutEdges.TryGetValue(edge.Source, out edges))
return;
if (!_allowsParallelEdges)
{
foreach (TEdge oldEdge in edges)
if (oldEdge.Target.Equals(edge.Target))
return;
}
edges.Add(edge);
}
If the source vertex of the edge doesn't exist or if the edge is repeated but the graph doesn't allow repeated edges I just return. But would it be better to throw an exception? To add the source vertex if it didn't exist in the first case?
Currently all methods just return normally if there's a problem, but maybe throwing would be better for the end user. Any comments?
Regards!
Vicente
|
|
| 02-12-2008 11:46 PM |
|
 |
mihies
Forum Newbie
Posts: 15
Group: Registered
Joined: Nov 2007
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
Hi Vicente,
I would solve this in two steps.
1. Do throw an exception if edge can't be added. Otherwise developer won't realise that there was a problem.
2. If one can't foresee wheter the edge can be added in advance* I would add a method "bool TryAddEdge" that returns true/false (instead of throwing exception) based on AddEdge succeed or not.
* if adding and edge that can't be added is an obvious mistake then there is no need for this second method
|
|
| 02-13-2008 01:48 PM |
|
|
Vicente
Administrator
Posts: 972
Group: Administrators
Joined: Sep 2006
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
I already used that approach on the VFS, but I wanted to avoid having to duplicate several methods. But it seems it's something easy to understand, so I'll go that path.
Thanks for the input! Regards!
Vicente
|
|
| 02-13-2008 09:29 PM |
|
|
mihies
Forum Newbie
Posts: 15
Group: Registered
Joined: Nov 2007
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
I already used that approach on the VFS, but I wanted to avoid having to duplicate several methods. But it seems it's something easy to understand, so I'll go that path.
Just to make it clear: you would have one method and two paths to that method - one will yield an exception while the other won't.
This post was last modified: 02-14-2008 08:40 AM by mihies.
|
|
| 02-14-2008 08:40 AM |
|
|
Vicente
Administrator
Posts: 972
Group: Administrators
Joined: Sep 2006
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
Well, I was thinking that for example AddEdge and TryAddEdge will call bool InnerAddEdge(TEdge edge, bool throw), with true and false, and inside InnerAddEdge check if throw or return a boolean.
That was your idea also more or less, right? Regards!
Vicente
|
|
| 02-14-2008 08:51 AM |
|
|
mihies
Forum Newbie
Posts: 15
Group: Registered
Joined: Nov 2007
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
Yep, something like that.
|
|
| 02-14-2008 08:54 AM |
|
|
Vicente
Administrator
Posts: 972
Group: Administrators
Joined: Sep 2006
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
That was fast  I think I'll just make AddEdge call TryAddEdge and if it fails then throw
Regards!
Vicente
|
|
| 02-14-2008 08:57 AM |
|
|
mihies
Forum Newbie
Posts: 15
Group: Registered
Joined: Nov 2007
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
I see that you are storing edges in a list and comparing them in a loop. Did you consider using a dictionary perhaps (for Target edges)?
It should allow faster search...
This post was last modified: 02-14-2008 09:09 AM by mihies.
|
|
| 02-14-2008 09:08 AM |
|
|
Vicente
Administrator
Posts: 972
Group: Administrators
Joined: Sep 2006
Status:
Offline
|
RE: To throw or not to throw (Jade.Ai.Graphs)
In the BGL implementation you can pass to the template a Dictionary or a List as the edge container. It depends if you allow parallel edges or not (edges that start and end in the same node). A Dictionary is faster but doesn't allow parallel edges while a List search is slower but allows for parallel edges.
Quoting the BGL doc:
Choosing the OutEdgeList type
The OutEdgeList parameter determines what kind of container will be used to store the out-edges (and possibly in-edges) for each vertex in the graph. The containers used for edge lists must either satisfy the requirements for Sequence or for AssociativeContainer.
One of the first things to consider when choosing the OutEdgeList is whether you want adjacency_list to enforce the absence of parallel edges in the graph (that is, enforce that the graph not become a multi-graph). If you want this enforced then use the setS or hash_setS selectors. If you want to represent a multi-graph, or know that you will not be inserting parallel edges into the graph, then choose one of the Sequence types: vecS, listS, or slistS. You will also want to take into account the differences in time and space complexity for the various graph operations. Below we use V for the total number of vertices in the graph and E for the total number of edges. Operations not discussed here are constant time.
(more here: http://www.boost.org/libs/graph/doc/usin..._list.html)
But I haven't found a way to do the same in .NET so far as both containers don't have nearly anything in common 
That's related also to a "problem" I wasn't sure how to solve: when I try to add an Edge, I consider it to be the same Edge if it starts and ends in the same place, but it can be really a different Edge object. If instead of using Source and Target for equality I used the Edge object itself then I should be able to use the Dictionary for parallel edges (but the user wouldn't be able to add exactly the same Edge twice or to remove an Edge he would need to get that exact object).
That's why I used the List, but maybe it wasn't the right idea after all (although a Hash search involves calculating the hashcode and that can be pretty expensive sometimes...).
Any comments on this part? Regards!
Vicente
This post was last modified: 02-14-2008 09:31 AM by Vicente.
|
|
| 02-14-2008 09:28 AM |
|
|
Search
Member List
Calendar
Help
Downloads
