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]

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("node0", new Transition("node1", 5); // node0->node1,5
graph.Add("node1", new Transition("node0", 5); // node1->node0,5
graph.Add("node1", new Transition("node2", 3); // node1->node2,3
graph.Add("node2", new Transition("node1", 3); // node2->node1,3
graph.Add("node0", new Transition("node2", 1); // node0->node2,1
graph.Add("node2", new Transition("node0", 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
UndirectedWeightedGraph that encapsulates the logic of constructing the
graph and performing common operations (ie. Dijkstra's Algorithm) on
it.

Brian
Eleanor wrote:

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