3
$\begingroup$

I have never taken any formal classes in graph theory, but I have recently been using a number of graph theory concepts in my daily work. One area that I have not seen much work on, however, is analysis of multiple graphs constructed from the same nodes but with different edges. For example, take the first five letters of the alphabet and the underline (_) representing a space.

We can make the following image representing the phrase "a bad bed":

A simple graph of

where the colors represent different structural elements.

  • Black = alphabetical order
  • Green = first word "a" plus termination indicator "_"
  • Red = second word "bad" plus termination indicator "_"
  • Blue = third word "bed"

Given a graph like this, I would like to do things like construct a graph consisting of selected subgraphs; in this case they would be "a", "bad", and "bed", but the concept should be general. Or, I would like to be able to examine properties of specific subgraphs without having to create duplicate nodes. For example, if you assign a number to each letter based on the alphabetical order, I would like to be able to examine aspects of the numbers associated with each subgraph. Keep in mind that this is just a generic description, I'm working with physical processes, not linguistics.

I have looked into nested heirarchical graphs and many other areas, but nothing quite fits what I'm going for and I don't know enough of the theory even to be able to tell if I'm using the correct language. Does anyone have any suggestions of where I should look?

  • 0
    I looked at relational databases as well, but none of them seemed much better. I think a part of my problem with relational databases is that I'm often concerned with material that is not countable (e.g. 1.35 gallons of milk transfered from Tank A to Tank B). Ultimately I need to compare uncertainties on such transfers and make inferential statements about the material. Given 10.2 +- 0.6 gallons in Tank A, and 9.35 +- 0.2 transfered to Tank B, and we measured 8.21 +- 0.1 gallons in Tank C after another transfer, how much milk is where with what confidence.2011-12-09

1 Answers 1

1

I think you should look at

1) Finite state machines: http://en.wikipedia.org/wiki/Finite-state_machine

2) Petri nets: http://en.wikipedia.org/wiki/Petri_net.

For programming puposes I recommended you to consider this libraries

1) For C++ http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html

2) For C# http://quickgraph.codeplex.com/

3) For Java http://jgrapht.sourceforge.net/

  • 0
    Thanks. So $f$ar I've been workin$g$ with networkx and Python(x,y) but I'll check out those sources.2011-12-09