Read this article now - Try Goliath Business News - FREE!   
You can view this article PLUS...

• Over 5 million business articles
• Hundreds of the most trusted magazines, newswires, and journals (see list)
• Premium business information that is timely and relevant
• Unlimited Access

Tell Me More   Terms and Conditions

Purchase this article for $4.95

...problems: the travelling salesman problem, efficient routing of a package, network flows, and more--all are modeled as graphs and often solved by graph-based algorithms.

A common use of a graph-based representation is that of a computation graph. Simply put, it's a graph that models a set of functions Fl, F2, ..., Fk that take a set of inputs 11, 12, ..., In and computes a set of outputs O1, O2, ..., Om. As an example, Figure 1 shows a simple computation graph with a small number of nodes. This simple example represents the following equations:

O1 = F5(F1(11, 12), F4(F1(11, 12), F2(12, 13)))

02 = F6(F4(F1(11, 12), F2(12, 13)), 14)

03 = F3(13, 14)

Note that by managing the computation as a graph traversal you can eliminate computing F4 (F1(11, 12), F2(12, 13)) twice. The nodes modeling both F5 and F6 access the value computed by the node representing F4.

Computation graphs arise in many environments and tend to be the preferred way to model very complex computations and dependencies. In fact, most computationally intensive environments use graph-based computation structures. The most prominent example of such environments occurs in financial services, including computer-based portfolio management, computer trading, pricing systems, risk management systems, hedge systems, and insurance quoting systems. These structures also arise in contract management systems, constraint-based optimization, impact analysis, root cause determination, and simulation systems. The reason is that a graph is the perfect way to mode] the dependencies between computation elements as well as the perfect metaphor to program to.

Most current systems managing computation graphs make use of proprietary environments to model and manage such structures. In this article I'll walk you through a different approach, one that makes use of XML to represent computation graphs. The approach is based on an XML representation that can be handed to almost context-free computation engines that cooperate to compute very large computation structures. While there would seem to be overhead and inefficiency in using XML instead of proprietary methods, this is offset by the fact that the full computation graph is partitioned so that many CPUs can work in tandem to compute the full result set. This approach has additional advantages in areas involving the maintainability of the system and the total cost of ownership.

Since the full framework involves some very advanced, complex, and sometimes confidential graph-partitioning methods, this article focuses on the general framework and stays away from the mathematical aspects of the approach.

Graphs and Trees

Data structures representing graphs (and hierarchies, which are also graphs) have been in use since the dawn of computers. For example, the major database technologies before relational databases were...

NOTE: All illustrations and photos have been removed from this article.



More articles from XML Journal
Native XML databases for hierarchical data: preserving the value of XM..., August 01, 2002
XML in the enterprise: dynamic SQL generation using XSLT. (XML Labs).(..., August 01, 2002
Managing your XML documents with schemas: a powerful--and flexible--wa..., August 01, 2002
Model-driven programming using XSLT: an approach to rapid development ..., August 01, 2002
Show report. (web services Edge conference & expo).(SYS-CON's Web Serv..., August 01, 2002

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.