The right class?

  • Thread starter Thread starter Eleanor
  • Start date Start date
E

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
 
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
 
Back
Top