Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-06-25
2002-11-05
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06476814
ABSTRACT:
A Computer Program Listing Appendix containing the following files:
testclass.java 3 KB
wordgraph.java 17 KB
edge.java 1 KB
line.java 2 KB
digraph.java 4 KB
node.java 1 KB
tempEdge.java 1 KB
tempNode.java 1 KB
on two identical copies of compact discs created on Jul. 16, 2002 for application Ser. No. 09/104,909 is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
The present invention relates in general to the field of automated graph drawing and display.
Complex systems are being used with increasing frequency. Examples of complex systems include a highway system connecting cities, a telephone system providing communication connections among a group of businesses with telephone, computers, fax machines and beepers, and a genealogical family tree. Complex systems are also used in the organization of distributed data base information systems and artificial neural networks.
These complex systems each can be described, explained and illustrated as a collection of objects and connecting paths between selected pairs of the objects. The mathematical model for these systems is a directed graph. A directed graph, G=(V,E), is defined by a set and a collection: a finite set, V, of elements (also referred to as “nodes”) and a finite collection, E, of elements of ordered pairs of nodes (also referred to as “edges”). Each ordered pair of nodes comprises an initial node and a terminal node. With directed graphs, an edge is “incident out of” its initial node and is “incident into” its terminal node.
An “incidence list” for a directed graph is a list of all the edges that are incident into or incident out of each node of the directed graph. An “incident out” list for a node is a subset of the incidence list containing the edges which are incident out of that node. Likewise, an “incident in” list for a node is a subset of the incidence list containing the edges which are incident into that node.
FIG. 1
is an illustration of one representation of a directed graph
10
, with the nodes labeled n
1
, n
2
, n
3
, etc. and the edges labeled e
1
, e
2
, e
3
, etc. As shown, a node is represented by a circle and an edge is represented by a line segment or arc segment between two nodes. The initial node and terminal node of the edge are distinguishable by the edge's “orientation” represented by an arrow on the edge pointing from the initial node to the terminal node.
The comprehension of a complex system from its representative pictorial representation of its representative directed graph is relatively easy when the graph contains on
1
y a few nodes and few edges (i.e., G has a small number of elements). However, when the number of nodes or the number of edges is great, the resulting dense directed graph and the represented system becomes difficult to understand. Additionally, a visual representation of a dense directed graph is not easily rendered for display on computer output devices nor is it convenient to electronically transmit such a graph. These problems have been associated with dense directed graphs of static information, and even more problems exist where the complex system is dynamic.
Examples of system models which can be represented mathematically by directed graphs include data flow diagrams, subroutine-call graphs, program nesting trees, object-oriented class hierarchies, class interfaces and entity-relationship (ER) diagrams for software engineering, matrix organizational charts, use-case diagrams, process flow charts for business process management, petri nets and state transition diagrams for real-time system modeling, PERT charts and activity trees for decision support systems, knowledge-representation (KR) diagrams, conceptual graphs, Bayesian networks, concept charts, semantic networks and associative networks for artificial intelligence and knowledge representation, SLD-trees for logic programming, concept lattices for medical science, evolutionary trees for biology, molecular drawings for chemistry, family trees for. genealogy and network diagrams for communications theory and network engineering.
There are numerous ways to model and render complex systems that share the concepts of directed graphs. The nodes of directed graphs generally represent atomic or elemental concepts or things. Terms such as entity or element are analogous to a directed graph node indicating indivisibility or at least unique identity. The edges of directed graphs represent associations, relationships, paths, links or connections between pairs of nodes and those terms are used interchangeably with directed graph edges depending on the model.
Because of the combinatorial and geometric nature of the systems modeled and the wide array of application domains, research on graph drawing has been conducted in such diverse areas such as discrete mathematics (topological graph theory, geometric graph theory, order theory), algorithmics (graph algorithms, data structures, computational geometry) and human-computer interaction (visual languages, graphical user interfaces, software visualization). For an example of the rich literature available on the subject of graph drawing see “Algorithms for Drawing Graphs: An Annotated Bibliography”,
Computer Geometric Theory and Applications,
G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis 4(5):235-282 (1994), which is incorporated by reference herein for all purposes.
Much effort has gone into developing better, faster, more readable and newer ways to draw, present, use, traverse, search and understand graphs, including arbitrary directed graphs.
Practitioners in fields dealing with complex systems strive to recognize, define, arrange and depict, according to some system, the elementary concepts and relationships between these elementary concepts derived from observation, study, experimentation, design and agreement. For example, biological taxonomists strive to agree on the classification of plants and animals. They use formal systems to recognize the discovery of new species and relate them to their classification scheme. Computer network administrators strive to document and communicate the design, implementation and maintenance of their networks including their nodes and connections using network diagrams and other tools and thus they must define each node, the connections (edges) between nodes and their orientations in some cases.
One method for representing complex systems is termed “exposition”, using text to convey relationships. Using text to convey an understanding of relationships between entities is pervasive. For example, in the sentence: “Prince Charles is the son of Queen Elizabeth II.”, a relationship between two entities is presented. Exposition is limited as a way of representing complex systems because of the large number of words, which would be necessary to describe and represent even a small number of relationships. Another limitation of exposition is that any mental pictures of the system are left to the listener or reader. Of course, textual exposition has the advantage of being easily communicated. Exposition is considered a linear (“one-dimensional”) data type of information visualization.
Another method used to display complex systems or relationships is termed “tabulation”. Tables A and B provide an example of tabulation.
FIG. 1
shows a graphical representation of a directed graph. Tables A and B provide the same information, albeit in a less graphical form.
TABLE A
Node Table
ID
Name
0
n1
1
n2
2
n3
3
n4
4
n5
5
n6
6
n7
TABLE B
Edge Table
ID
Name
Initial Node
Terminal Node
0
e1
n1
n2
1
e2
n1
n2
2
e3
n1
n3
3
e4
n3
n1
4
e5
n2
n4
5
e6
n3
n4
6
e7
n4
n4
7
e8
n5
n6
8
e9
n4
n4
The directed graph may be conceptualized as tables representing the collections of a graph G=(V,E). In the above example, Tables A and B represent the nodes in the graph and the collection of edges, respectively. Each element (row) of Table A provides an ID (a unique numeric identifier for the node) and a Name (a unique name or label applied to the node). Each element (row) of Table B provides an ID (a unique numeric identifier for the edge)
Albert Philip H.
Brier Jeffery
Townsend & Townsend & Crew LLP
Wordgraph, Inc.
LandOfFree
Display structure for representation of complex systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Display structure for representation of complex systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Display structure for representation of complex systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984806