The right class?

[Eleanor]

Hi,

Could you please help me finding out whether the following is an
appropriate data structure.
I represent an undirected weighted graph of strings that is searchable
and enumeratable as:

Hashtable graph (string nodeA, Hashtable intern); and Hashtable
intern (string nodeB, double weight)

In which each edge is added twice (once for nodeA -> nodeB, and once for
nodeB -> nodeA)

I guess I'm wondering whether there really is not any collection that is
directly "accessible " from two sides. For instance, suppose there exists
something like a three-cell storage Hashtable (instead of a two-cell
storage), that is accessible through the key or through the "last"
value. In case of the undirected graph, one would be able to go from
nodeA->weight->nodeB and from nodeB->weight->nodeA (without adding the
edge twice of course).

Thanks in advance.

Eleanor

[Brian Gideon]

Re: The right class?

Eleanor,

You have several choices. I have presented 2 below.

1) Store the graph in an adjacency map.

You will have one hashtable that will use the string as the key and a
user defined structure that contains the transition node and weight as
the value. Since the graph is undirected you will need two entries in
the hashtable for each edge of the graph. The following example
constructs a graph with 3 nodes where every node has a transition to
every other node.

Hashtable graph = new Hashtable();
graph.Add("node 0", new Transition("nod e1", 5); // node0->node1,5
graph.Add("node 1", new Transition("nod e0", 5); // node1->node0,5
graph.Add("node 1", new Transition("nod e2", 3); // node1->node2,3
graph.Add("node 2", new Transition("nod e1", 3); // node2->node1,3
graph.Add("node 0", new Transition("nod e2", 1); // node0->node2,1
graph.Add("node 2", new Transition("nod e0", 1); // node2->node0,1


2) Store the graph in an adjacency matrix.

You will use a 2 dimensional array where the first dimension represents
the source node and the second dimension represents the destination
node. The array will contain the weight of the transition. The
following example constructs the same graph as above. A transition
with a weight of zero is assumed to be nonexistent.

int nodes = 3;
int[,] graph = new int[nodes, nodes];
graph[0, 1] = 5;
graph[1, 0] = 5;
graph[1, 2] = 3;
graph[2, 1] = 3;
graph[0, 2] = 1;
graph[2, 0] = 1;

To make things simpler you might want to create your own class called
UndirectedWeigh tedGraph that encapsulates the logic of constructing the
graph and performing common operations (ie. Dijkstra's Algorithm) on
it.

Brian


Eleanor wrote:[color=blue]
> Hi,
>
> Could you please help me finding out whether the following is an
> appropriate data structure.
> I represent an undirected weighted graph of strings that is
> searchable and enumeratable as:
>
> Hashtable graph (string nodeA, Hashtable intern); and
> Hashtable intern (string nodeB, double weight)
>
> In which each edge is added twice (once for nodeA -> nodeB, and once
> for nodeB -> nodeA)
>
> I guess I'm wondering whether there really is not any collection that
> is directly "accessible " from two sides. For instance, suppose there
> exists something like a three-cell storage Hashtable (instead of a
> two-cell storage), that is accessible through the key or through the
> "last" value. In case of the undirected graph, one would be able to
> go from nodeA->weight->nodeB and from nodeB->weight->nodeA (without
> adding the edge twice of course).
>
> Thanks in advance.
>
> Eleanor[/color]