Graphic display of network topology

• US 5,276,789 A
• Filed: 05/14/1990
• Issued: 01/04/1994
• Est. Priority Date: 05/14/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Smith, Darren D., Besaw, Lawrence M., Wu, Jeff C., Chang, Cho Y., Kean, Mark J.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Jankus, Almis
• Application Number:
  US07/523,168
• Time in Patent Office: 1,331 Days
• Field of Search: 395/155-161, 395/138, 395/139, 395/140-143
• US Class Current: 345/440
• CPC Class Codes: G06F 2111/02 CAD in a network environment, e.g. collaborative CAD or distributed simulation
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: Y10S 715/969 Network layout and operation interface

Abstract

A system for automatically laying out and graphically displaying the topology of a computer network system. The layout system retrieves a list of the nodes within the network and their interconnections from a database which can be manually built by a network administrator or automatically constructed by other software. The system will provide any of three views that can be requested by the user. An internet view is the largest and shows the interconnection of different networks. A network view can be shown for any of the networks described in the internet view. A network is comprised of segments and the system will display a view of the nodes connected to any one of the segments. The system will automatically update the view as new nodes become available in the database. This aspect of the system and allows the system to dynamically update the graph when the list of nodes is being supplied by other software. The system also allows the user to dynamically alter the graph by using a graphical input device to move any of the objects displayed on the graph.

Claims

1. A computer implemented method for displaying, on a graphic output device connected to a computer system, a plurality of graphic objects, wherein each said graphic object has zero, one or a plurality of connecting lines that connect said graphic object to other graphic objects, said method comprising the steps of:

(a) programmatically placing said graphic objects into a graph and assigning each said graphic object to one of a plurality of vertices of said graph;

(b) programmatically placing said connecting lines into said graph and assigning each said connecting line to one of a plurality of edges of said graph, whereby a vertex is said to have an edge if said vertex has one or more connecting lines to other vertices;

(c) programmatically dividing said vertices into clusters comprising the steps of

(c1) temporarily removing one of said edges,

(c2) starting from each of said vertices, programmatically examining each of said edges to programmatically determine if all said vertices are connected through one or more of said edges,

(c3) if one or more vertices is determined by step (c2) to not be connected, collecting said one or more not connected vertices into a separate cluster, and

(c4) repeating steps (c1) through (c3) for said separate cluster;

(d) programmatically arranging each of said vertices within each of said clusters on said graph;

(e) programmatically arranging said clusters on said graph;

(f) displaying said graph on said graphic output device; and

(g) moving a selected one of said graphic objects in response to each move request entered through a graphical input device.

2. The process of claim 1 wherein the following step is performed between steps (b) and (c):

programmatically collecting all vertices having zero edges into a cluster and designating said cluster as an orphan cluster.

3. The process of claim 1 wherein the following steps are performed between steps (b) and (c):

(b1) temporarily removing all vertices having one edge; and

(b2) repeating step (b1) until no vertices with one edge remain in said graph.

4. The process of claim 3 wherein step (d) comprises the steps of:

(d1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(d2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(d3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(d3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(d3b) if no vertex having said connection is found in step (d3a), selecting any remaining unplaced vertex, and

(d4) repeating step (d3) until all said vertices of said cluster have been placed on said circumference.

5. The process of claim 4 wherein step (d1) further comprises the following steps performed prior to defining said circle:

(d1a) selecting a vertex having exactly two edges;

(d1b) marking said selected vertex for placement outside of said circumference of said circle; and

(d1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

6. The process of claim 4 further comprising the step of reintroducing said vertices removed in steps (b1) and (b2) and placing said reintroduced vertices outside said circumference of said circle and adjacent said vertex to which said reintroduced vertices were originally connected.

7. The process of claim 1 wherein step (d) comprises the steps of:

(d1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(d2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(d3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(d3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(d3b) if no vertex having said connection is found in step (d3a), selecting any remaining unplaced vertex, and

(d4) repeating step (d3) until all said vertices of said cluster have been placed on said circumference.

8. The process of claim 7 wherein step (d1) further comprises the following steps performed prior to defining said circle:

(d1a) selecting a vertex having exactly two edges;

(d1b) marking said selected vertex for placement outside of said circumference of said circle; and

(d1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

9. The process of claim 1 wherein step (e) further comprises arranging said clusters into a row and column format.

10. The process of claim 1 further comprises arranging a new graphic object on said graph each time said new graphic object is programmatically placed into said graph.

11. The process of claim 10 further comprising the steps of:

determining if a user has requested an autolayout function;

if autolayout has been requested, repeating steps (a) through (f) each time said new graphic object can be loaded; and

if autolayout has not been requested, placing said new graphic object in a holding area on said graphic output device each time said new graphic object can be loaded.

12. The process of claim 11 further comprising the step of rescaling said graph if autolayout has been requested and said new graphic object could not be placed within bounds imposed by said graphic output device.

13. A computer implemented method of displaying, on a graphic output device attached to a computer system, a view of a computer internetwork comprising the steps of:

(a) programmatically assigning each network within said internetwork to one of a plurality of vertices in a graph stored in said computer system;

(b) programmatically assigning each gateway in said internetwork to one of said plurality of vertices of said graph and programmatically collecting all vertices having zero edges into a cluster and designating said cluster as an orphan cluster;

(c) programmatically assigning each connection between said vertices to one of a plurality of edges in said graph, whereby a vertex is said to have an edge if said vertex has one or more connections to other vertices;

(d) programmatically dividing said vertices into clusters comprising the steps of

(d1) temporarily removing one of said edges,

(d2) starting from each of said vertices, programmatically examining each of said edges to programmatically determine if all said vertices are connected through one or more of said edges,

(d3) if one or more vertices is determined by step (d2) to not be connected, collecting said one or more not connected vertices into a separate cluster, and

(d4) repeating steps (d1) through (d3) for said separate cluster;

(e) programmatically arranging each of said vertices within each of said clusters on said graph;

(f) programmatically arranging said clusters on said graph; and

(g) displaying said graph on said graphic output device.

18. The process of claim 13 wherein step (e) comprises the steps of:

(e1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(e2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(e3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(e3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(e3b) if no vertex having said connection is found in step (e3a), selecting any remaining unplaced vertex, and

(e4) repeating step (e3) until all said vertices of said cluster have been placed on said circumference.

19. The process of claim 18 wherein step (e1) further comprises the following steps performed prior to defining said circle:

(e1a) selecting a vertex having exactly two edges;

(e1b) marking said selected vertex for placement outside of said circumference of said circle; and

(e1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

20. The process of claim 13 wherein step (f) further comprises arranging said clusters into a row and column format.

21. The process of claim 13 wherein step (a) further comprises arranging a new vertex on said graph each time a network is programmatically assigned to a vertex.

22. The process of claim 21 further comprising the steps of:

determining if an autolayout function has been requested by a user of a said computer system;

if autolayout has been requested, repeating steps (a) through (f) each time said new vertex can be loaded; and

if autolayout has not been requested, placing said new vertex in a holding area on said graphic output device each time said new vertex can be loaded.

23. The process of claim 22 further comprising the step of rescaling said graph if autolayout has been requested and said new vertex could not be placed within bounds imposed by said graphic output device.

24. The process of claim 13 further comprising the step of moving a selected one of said vertices in response to each move request entered through a graphical input device attached to said computer system.

14. The process of 13 wherein step (b) further comprises the steps of:

(b1) temporarily removing all vertices having one edge; and

(b2) repeating step (b1) until no vertices with one edge remain in said graph.

15. The process of claim 14 wherein step (e) comprises the steps of:

(e1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(e2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(e3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(e3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(e3b) if no vertex having said connection is found in step (e3a), selecting any remaining unplaced vertex, and

(e4) repeating step (e3) until all said vertices of said cluster have been placed on said circumference.

16. The process of claim 15 wherein step (e1) further comprises the following steps performed prior to defining said circle:

(e1a) selecting a vertex having exactly two edges;

(e1b) marking said selected vertex for placement outside of said circumference of said circle; and

(e1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

17. The process of claim 15 further comprising the step of reintroducing said vertices removed in steps (b1) and (b2) and placing said reintroduced vertices outside said circumference of said circle and adjacent said vertex to which said reintroduced vertices were originally connected.

25. A computer implemented method of displaying, on a graphic output device attached to a computer system, a view of a computer network comprising the steps of:

(a) programmatically assigning each segment within said internetwork to one of a plurality of vertices of a graph;

(b) programmatically assigning each connection between said vertices to one of a plurality of edges of said graph, whereby a vertex is said to have an edge if said vertex has one or more connections to other vertices;

(c) programmatically dividing said vertices into clusters comprising the steps of

(c1) temporarily removing one of said edges,

(c2) starting from each of said vertices, programmatically examining each of said edges to programmatically determine if all said vertices are connected through one or more of said edges,

(c3) if one or more vertices is determined by step (c2) to be unconnected, collecting said one or more not connected vertices into a separate cluster, and

(c4) repeating steps (c1) through (c3) for said separate cluster;

(d) programmatically arranging each of said vertices within each of said clusters on said graph;

(e) programmatically arranging said clusters into a row and column format on said graph; and

(f) displaying said graph on said graphic output device.

26. The process of claim 25 wherein step (b) further comprises the step of:

(b1) programmatically collecting all vertices having zero edges into a cluster an designating said cluster as an orphan cluster.

31. The process of claim 25 wherein step (d) comprises the steps of:

(d1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(d2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(d3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(d3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(d3b) if no vertex having said connection is found in step (d3a), selecting any remaining unplaced vertex, and

(d4) repeating step (d3) until all said vertices of said cluster have been placed on said circumference.

32. The process of claim 31 wherein step (d1) further comprises the following steps performed prior to defining said circle:

(d1a) selecting a vertex having exactly two edges;

(d1b) marking said selected vertex for placement outside of said circumference of said circle; and

(d1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

33. The process of claim 25 wherein step a further comprises programmatically arranging a new vertex on said graph each time a segment is assigned to said new vertex.

34. The process of claim 33 further comprising the steps of:

determining if an autolayout function has been requested by a user of said computer system;

if autolayout has been requested, repeating steps (a) through (f) each time said new vertex can be loaded; and

if autolayout has not been requested, placing said new vertex in a holding area on said graphic output device each time said new vertex can be loaded.

35. The process of claim 34 further comprising the step of rescaling said graph if autolayout has been requested and said new vertex could not be placed within bounds imposed by said graphic output device.

36. The process of claim 25 further comprising the step of moving a selected one of said vertices in response to each move request entered through a graphical input device attached to said computer system.

27. The process of 25 wherein step (b) further comprises the steps of:

(b1) temporarily removing all vertices having one edge; and

(b2) repeating step (b1) until no vertices with one edge remain in said graph.

28. The process of claim 27 wherein step (d) comprises the steps of:

(d1) defining a circle with a circumference large enough to graphically contain all vertices of a first of said clusters;

(d2) selecting a first of said vertices to place at a first location on said circumference of said circle;

(d3) selecting a second of said vertices to place at a next location on said circumference comprising the steps of

(d3a) locating one of said remaining vertices having an edge connecting to said first vertex,

(d3b) if no vertex having said connection is found in step (d3a), selecting any remaining unplaced vertex, and

(d4) repeating step (d3) until all said vertices of said cluster have been placed on said circumference.

29. The process of claim 28 wherein step (d1) further comprises the following steps performed prior to defining said circle:

(d1a) selecting a vertex having exactly two edges;

(d1b) marking said selected vertex for placement outside of said circumference of said circle; and

(d1c) repeating steps (d1a) through (d1b) until no more unmarked vertices having exactly two edges remain in said cluster.

30. The process of claim 29 further comprising the step of reintroducing said vertices removed in steps (b1) and (b2) and placing said reintroduced vertices outside said circumference of said circle and adjacent said vertex to which said reintroduced vertices were originally connected.