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?

  • 1
    This is an odd thing to think of as a graph, in that they are really paths through the letters, rather than graphs. Yes, paths are a type of directed graph, but they are a very particular type. How many edges would be between $d$ and $e$ in your graph representation of the word "ceded"? I think you need to be clearer about your example.2011-12-09
  • 0
    For another example, the graph you'd get from "abacab" would have directed edges (a,b), (b,a), (a,c), and (c,_). But you cannot reconstruct the word from the graph because the graph for $acabab$ is the same, even if you add multiple edges for each pair of letters.2011-12-09
  • 0
    Yes, I could have been more explicit in my example; I was simply trying to keep things generic. What I am actually working with is material movement in a factory. I want to have one representation of the plant, but I want be able to query that representation so as to know whether material moves from Scale A to Forklift B to Pallet C; or from Room 100 to Room 120 depending on whether I am interested in equipment or rooms in any particular instance.2011-12-09
  • 0
    Part of my difficulty is that I am associating numbers to specific locations and I want to be able to do things like ask how many jugs of milk that are weighed on Scale A end up in Room 160.2011-12-09
  • 0
    This is more of a relational database thing than a graph theory thing. You have rooms, items, and other types of relationships (was weighed at.) You are definitely talking about paths for your movable items, rather than graphs, because a graph of the transitions of an item from room to room doesn't include the order of the transitions.2011-12-09
  • 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 far I've been working with networkx and Python(x,y) but I'll check out those sources.2011-12-09