Tags: appropriate, class, following, graph, net, represent, sharp, strings, structure, undirected, weighted

The right class?

On .Net » .Net C# (C sharp)

3,794 words with 1 Comments; publish: Mon, 02 Jun 2008 18:49:00 GMT; (10078.13, « »)

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

All Comments

Leave a comment...

  • 1 Comments
    • 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

      #1; Mon, 02 Jun 2008 18:50:00 GMT