Adaptive Graph Library

AGL is an experiment in Adaptive Programming. While the programmer is allowed to think about operations and properties of abstract types, the AGL library itself will take care of mapping the programmers intent to an implementation. It does this using a simple rule engine. An interesting aspect of the library is that AGL operations may modify the implementation type or even substitute another implementation if needed. The library attempts to optimize it's behavior over the lifetime of the program based on the programmer declared properties and those properties inferred by the program.

A graph is useful tool in many disciplines. A graph is represented by the pair (V,E) where V is the set of vertices and E is the set of edges. AGL provides users with a high level graph concept driven by properties. It also supplies a library of algorithms to operate on transperently on the abstract data types.

Some Examples:

• Edge data
• Graph types

Getting started:

• The tar file for Java
  
• The online documentation in javadoc format.

Graph Types

• Undirected Graph
• Directed Graph
• Bidirected Graph (both in/out edges are constant operations).
• Hyper (edges connect multiple nodes).
• Multi (multiple edges between nodes).

Graph Properties

Properties represent known or requested facts about the graph, for example the type of the graph or a known root.

• Undirected, Directed, Bidirected, Hyper, Multigraph
• Acyclic, Tree
• RootNode

Properties may have values such as integer, String, boolean or Object

Property Maps

Every graph has a set of property maps. Each Map represents the a function that binds vertices/edges to some data data such as node labels. Some maps are termed "natural" in that the representation may provide the map without programmer help. Others are simply java maps. All maps support the standard java map interface.

Graph Representation

The graph library will choose the best representation for the graph. This choice is based on a set of requested graph properties.

For example gb = new UngraphBuilder(new GraphTag[] { OBJECT_VERTEX }); would request a undirected graph which uses java Objects as verteces. Therefore, based on the requested properties, a bit matrix representation might be chosen.

Adding a request for an Edge data map, then we would prefer the use of Adjecency matrix or even Adjecency list. gb = new UngraphBuilder(new GraphTag[] { OBJECT_VERTEX, EDGE_DATA });

Currently the following representation are supported:
See the package for complete list.

• Adjecency List
• Adjecency Matrix
• Edge Set (user type).
• Nodes (Edges are stored in vertices)

Any object may be a vertex, but the graph library must represent connection betweens objects. Currently the library supports the following edge representations, each having specific properties discussed later.

Algorithms

• Shortest Path
• DepthFirst visitor
• Breadth First visitor
• Topological Sort

Concepts

Below are listed some important feature/concepts of AGL.

Representations

Representations manipulate edges and vertices. These provide fundamental ways of representing graph structures. In addition, each representation also exports vertex and edge type and set of tags and natural maps.

Properties

Each graph type supports certain properties. A graph may be undirected or support multiple edges between a pair of nodes. Each property of the graph is tagged. Representations also provide properties to a graph. Many property maps are predefined by the representations. For example, EDGE_DATA in Matrix Rep will provide a map like interface to edge data stored in the matrix. While for other representations will be simply implemented as a HashMap of Edge to Object.

Graphs

Each graph is made up of a Representation and a set of tags/properties. Graphs provide an abstraction layer that hides the representation and defines the allowed operations (in terms of properties). Algorithms work directly on graphs.

Builders

Builders construct graphs. They are also responsible for choosing the best representation of a graph based on a set of requested properties. Each builder maintains a representation and and a set of properties.

Algorithms

Algoirthms will operate on different types of graphs. Each algorithm has a set Suggest/Require graph tags for efficient runs. Algorithms may also decorate a graph with extra tags denoting some property of graph.

Listeners

Listeners are used during graph building events. Example : VERTEX_DATA property maintenence is done through a graph listeners. Internally these are used to maintain the maps. Users may create and add their own listeners.