System and method for preprocessing and delivering multimedia presentations

Description Submit all comments and votes

RELATED APPLICATIONS AND PATENTS

U.S. patent application Ser. No. 08/274,503, entitled Apparatus and Method for Preprocessing Multimedia Presentations, and filed on Jul. 13, 1994 concurrently with, and for the same inventors of, the present application, pending U.S. patent application Ser. No. 08/143,007, entitled Apparatus and Method for Predicting Subjective Quality of Compressed Images and filed on Oct. 26, 1993 for T. H. Judd, and pending U.S. patent applications Ser. No. 07/884,516, entitled Communications Architecture and Method of Distributing Information Services, which issued on Dec. 9, 1994 and U.S. Pat. No. 5,371,532, and Ser. No. 07/884,515, entitled Communications Architecture and Buffer for Distributing Information Services, which issued on Aug. 23, 1994 as U.S. Pat. No. 5,341,474, both for A. D. Gelman, H. Kobrinski, L. S. Smoot, and S. B. Weinstein, all of which are assigned to the assignee hereof, contain subject matter related to that of the present application.

FIELD OF THE INVENTION

This invention relates to a method and system for preprocessing and delivering multimedia presentations.

BACKGROUND OF THE INVENTION

Multimedia information is a combination of different types of information (e.g., still images, text, graphics, audio, and motion video) integrated into a single presentation. The growing market for multimedia presentations has stimulated interest in efficient and cost-effective mechanisms for delivering multimedia presentations from providers to customers.

Some prior delivery schemes provide real-time delivery of multimedia presentations from an information warehouse, where multimedia presentations of one or more providers are stored, to multiple customers. Illustratively, FIG. 1A depicts a prior delivery system 10 which includes an information warehouse 20, a distribution network 30, and a plurality of customer premises equipments (CPEs) 40-1 through 40-K corresponding to customers 41-1 through 41-K, respectively. The information warehouse 20 includes mass storage 21, where multimedia presentations are stored, and a server 22, which retrieves multimedia presentations from storage 21 and delivers these presentations to the CPEs of requesting customers.

The multimedia presentation includes objects which contain the images, text, graphics, or other information to be presented to the customer. On receiving a customer's request for a multimedia presentation, the server sends to the customer's CPE, a script corresponding to the multimedia presentation, which script contains instructions for retrieving the objects from the server and presenting the objects to the customer. The CPE then plays out the presentation to the customer as instructed in the script along a main presentation path and sends requests for objects of the presentation to the server 22 as needed. On receiving a request from a customer for a multimedia object, the server delivers the object to the customer's CPE as requested as quickly as possible, thereby operating in a reactive mode in delivering objects to the CPE. This reactive mode of operation between the server and the CPE characterizes the conventional client-server model.

At times during the presentation, the customer may have the opportunity to select interactive features. Such features may include moving to another screen of information or selecting the display of a sidebar. Should the customer select an interactive feature, the customer's CPE sends a request to the server for the appropriate objects of the presentation to be played out in response to the customer's selection. The server reacts by sending the requested objects of the presentation as quickly as possible to the CPE. The CPE switches from presenting the multimedia presentation along the main presentation path to presenting the multimedia presentation along a sub-presentation path corresponding to the selected interactive feature.

For purposes of illustrating the shortcomings of a reactive mode of operation characterizing prior multimedia delivery systems, FIGS. 1B and 1C depict a table and graph, respectively, of objects representing an original multimedia presentation (OMP). An OMP is used to clearly specify the behavior of a multimedia presentation. In FIG. 1B, each row corresponds to an object and the column entries represent the following:

Object Number: a unique identifier for each object.

Object Description: a comment (meant for the reader) that describes the object's purpose. The Object Description is for illustrative purposes only and would not be part of an OMP in practice.

Object Type: the medium contained in the object.

Object Size: the size of the object in bytes.

Presentation Times: the time at which the presentation of the object is to begin (Start) and the time at which the presentation of the object is to end (End). For visible images, the End Time is the time at which the object will be removed from the display. For audio objects, the End Time is the time at which the audio will no longer be audible to the customer.

Clock: the logical clock used to base this object's Start and End Times. Logical clocks are used to represent alternative paths through the presentation (paths being chosen as a result of an interactive feature). By convention, the presentation begins on Clock 1. In this example, Clock 2 represents the only alternative sub-presentation path in this presentation.

The OMP of FIGS. 1B and 1C is simplified and may not be exemplary of typical multimedia presentations. However, this illustrative presentation serves our purposes of presenting an easy-to-understand example. As shown in FIGS. 1B and 1C, our illustrative multimedia presentation comprises a main presentation which includes Objects 1 through 5 and a sub-presentation which includes Objects 6 and 7. The objects of the main presentation have presentation times based on Clock 1, and the objects of the sub-presentation have presentation times based on Clock 2.

As shown in FIGS. 1B and 1C, the OMP begins along the main presentation path and the active presentation clock is Clock 1. After a 5-second delay, the image of Object 1 is presented at t.sub.1 =5 seconds, and this image remains visible until t.sub.1 =20 seconds. Object 2, a sidebar icon, appears 9 seconds into the main presentation indicating to the customer that there is additional, optional information that may be viewed by choosing the sidebar interactive feature. The icon of Object 2 remains for 10 seconds until t.sub.1 =19 seconds. FIG. 1D depicts an interaction table for the OMP which shows that the interactive feature is enabled during the 10 second interval from t.sub.1 =9 seconds to t.sub.1 =19 seconds, and disabled at all other times. Each row of the interaction table corresponds to an interactive feature, and the meaning of the column entries in FIG. 1D are as follows:

Enable Time: the time at which this interactive option is enabled (the interactive feature can not be chosen unless it is enabled).

Disable Interaction Time: the time at which the interaction is disabled.

Interaction Clock: the Clock on which to base the Enable and Disable Times of the interactive features.

Jump Event Description: a description of the user interaction that will result in this event being selected. In practice, this entry would hold one of a number of possibilities, such as "user selects object on screen" or "user types in a number".

Clock: the clock on which the presentation will continue.

If the customer selects the interactive feature during this interval, the customer's CPE jumps from requesting and presenting objects along the main presentation path to the sub-presentation path. The screen is cleared of the main presentation objects, the active clock is now Clock 2 (t.sub.2 =0) corresponding to the sub-presentation path, and the image of Object 6 appears at t.sub.2 =0 remaining visible for 10 seconds. After t.sub.2 =10 seconds, the image of Object 7 appears and remains visible for 10 seconds until t.sub.2 =20 seconds. The sub-presentation is terminated at t.sub.2 =20 seconds, and presentation along the main presentation path is then resumed at the point in time where interrupted by the sub-presentation.

If the customer does not select the sidebar interactive feature during the 10 second interval, the presentation continues along the main presentation path without interruption. At 16 seconds into the main presentation (t.sub.1 =16 seconds), the image of Object 3 appears alongside the previous image of Object 1 and the sidebar icon of Object 2 and remains until t.sub.1 =25 seconds. At 17 seconds into the main presentation (t.sub.1 =17 seconds), the image of Object 4 similarly appears, alongside the previous images and remains until t.sub.1 =25 seconds. At 19 seconds into the main presentation (t.sub.1 =19 seconds), the sidebar icon disappears, the interactive feature is disabled, and selecting the sidebar has no effect. At t.sub.1 =25 seconds, the previous images of Objects 3 and 4 disappear and Object 5 appears and remains until t.sub.1 =30 seconds. The presentation terminates at t.sub.1 =30 seconds.

Now, we assume that the OMP shown in FIGS. 1B and 1C, as described above, is delivered by delivery system 10 of FIG. 1A which operates under the conventional client-server model. We also assume that the distribution network 30 operates at a network bit rate of 128 kb/s and that the memory capacity at the customer's CPE is 250 Kbytes. On receiving the customer's request for this presentation, a script of the presentation (the OMP and the Interaction Table) is transmitted from the server to the customer's CPE, and the CPE requests the objects of the presentation to be sent along the main presentation path of the presentation. In responding to the CPE's requests for delivery of the OMP, the server 22 begins by delivering objects along the main presentation path following Clock 1, with each object being transmitted as soon as requested. The CPE also tracks the size of objects to be transmitted to the CPE to ensure that the next object to be transmitted can be accommodated by the CPE memory. If the object cannot be accommodated, requests to the server are halted until the presentation time of previously delivered objects has passed, and objects are deleted from memory thus making memory available to store the next object.

Therefore, the CPE will request, and the server will deliver, Objects 1, 2, 3, 4, and 5, consecutively, with delivery start and end times as shown in FIG. 1E. Requests to the server are halted after Object 5 since the memory at the customer's CPE is full (250 Kbytes) and cannot accommodate additional objects at this time. Therefore, if the customer were to select the sidebar interactive feature after Object 5 has been sent to the CPE and before the interval ends at t.sub.1 =19 seconds, then the customer will experience a delay between the selection of the sidebar interactive feature and the presentation of Object 6. This delay would be attributable, in part, to the unavailable memory capacity at the CPE.

Even if the customer were to select the side bar at t.sub.1 =19 seconds, thereby essentially eliminating delays due to unavailable memory capacity, delays will also result due to interactive response time, which is the length of time between a customer's selection of an interactive feature and a change in the presentation reflecting the customer's selection. This response time includes the time necessary for the server to receive a request from the CPE reflecting the customer's selection, to react to the request, while simultaneously servicing requests of other customers, and to deliver objects to the CPE in response to the customer's interactive selection. Assuming that the customer's interactive selection is made at t.sub.1 =19 seconds and that the worst case interactive response time is 2 seconds, Objects 6 and 7 will be delivered with start and end times as shown in FIG. 1E.

The delays discussed above are largely a result of the reactive mode of operation of multimedia delivery systems operating under the conventional client-server model. Specifically, the server 22 delivers objects as requested by the customer's CPE along the main presentation path until the customer makes an interactive selection, and then the server reacts to the request of the customer's by transmitting those objects which fulfill the customer's selection as directed by the CPE. A drawback of such delivery systems is that the server in no way incorporates in its delivery strategy the delivery of objects that may be needed in the future to fulfill a customer's interactive selection such that delays or breaks in the presentation are eliminated.

Another major shortcoming of the server's reactive mode of operation is that the number of customers being served directly affects the interactive response seen by each customer. This means that as each new customer gains access to the system, the existing customers will likely notice decreased quality of performance, in the form of increased interactive response time. If one wishes to maintain interactive response time below a specified value, it is necessary to limit the number of customers or purchase a more powerful server. Otherwise, servicing more customers could result in significant contention at the server and ultimately interruptions or delays in the presentation of OMPs to customers. Since the server 22 must handle the delivery of OMPs to multiple customers simultaneously, it is important to properly scale the client-server ratio to ensure that delays in presenting the OMP will not exceed a preset maximum. This limitation imposed on the number of customers that can be serviced from a server affects the shared cost of the server among customers. Ideally, it is an objective to maximize the number of customers serviced by the server such that the cost of the server can be maximally shared among customers and widespread deployment of this delivery strategy can be achieved.

In view of the shortcoming of conventional approaches and mechanisms for delivering OMPs, an object of our invention is a system and method for providing interactive delivery of OMPs in real time. Another object of our invention is a delivery strategy which anticipates the object needs of the CPE along a main presentation path and delivers objects prior to the their presentation times. A further object of our invention is a delivery strategy which anticipates a customer's selections of an interactive feature and delivers objects that may be needed in the future to fulfill the customer's interactive selection such that delays or breaks in the presentation are virtually eliminated. Another objective of our delivery system and method is to increase the server-customer ratio realizable under a conventional client-server model without imposing unacceptable breaks or delays in the delivery of OMPs to customers.

SUMMARY OF THE INVENTION

An aspect of our invention is a system and method for preprocessing and delivering multimedia presentations to customers. Our inventive system comprises a preprocessor, mass storage, a delivery processor, a distribution network, and a plurality of presentation processors. The preprocessor receives as inputs an OMP, which includes presentation commands and associated objects, and presentation technology parameters (PTPs) indicating key information about the delivery processor, the distribution network, and the presentation processor which are to deliver and present the presentation to a requesting customer. This key information includes the round trip latency (RTL) between the delivery processor and the presentation processor, which RTL is the time for a 1 bit message to be sent from the presentation processor to the delivery processor and a response from the delivery processor to be received at the presentation processor.

Based upon these inputs, the preprocessor generates a preprocessed multimedia presentation (PMP) which includes a delivery schedule for delivering the presentation such that delays and gaps in presentation due to interactive response time are virtually eliminated.

The mass storage holds PMPs available for delivery, and the delivery processor delivers multimedia presentations requested by customers by following the delivery commands contained in the delivery schedule of the preprocessed multimedia presentation. Each customer has a corresponding presentation processor, and the delivery processor transmits a requested presentation to the presentation processor corresponding to the requesting customer via the distribution network. The presentation processor presents the objects of the presentation to the customer according to associated presentation commands received from the delivery processor.

The preprocessor includes a presentation scheduler, which analyzes the objects of the presentation, their associated presentation times, and customer interactive features and generates a delivery schedule such that:

1) each object and its associated presentation command arrive at the presentation processor no later than the time at which the object is to presented;

2) any object and its associated presentation command which are delivered to the presentation processor can be accommodated in its memory; and

3) the interactive response time due to the customer's selection of an interactive feature is virtually eliminated.

In generating the delivery schedule, the presentation scheduler also ensures that those objects to be presented in response to a customer's selection of an interactive feature are received at the presentation processor prior to their earliest possible presentation times.

The preprocessing of an OMP begins with the OMP and presentation technology parameters being loaded into the preprocessor. A delivery schedule in the form of a labelled, directed graph is generated by the presentation scheduler by defining a node including a delivery command for delivering a presentation command and its associated object from the delivery processor to the presentation processor. A presentation command and its associated object having the earliest presentation time are scheduled for earliest delivery, and each delivery command includes the delivery time and the identity of the presentation command and its associated object to be delivered.

The delivery processor delivers the presentation to the presentation processor corresponding to the requesting customer by executing the delivery schedule embedded in the PMP. Specifically, the delivery processor follows the labelled, directed graph representing the delivery schedule and executes the delivery command contained in each node of the graph. On encountering a node having multiple output leads, which indicates that an interactive feature is available for customer selection, the delivery processor checks if a message has been received from the presentation processor indicating the customer's selection of an interactive feature. Whether or not such a message is detected determines the path in the delivery schedule to be followed by the delivery processor in proceeding with the delivery of the presentation.

The presentation processor compares the time on its local clock with the time for executing each presentation command to determine if any of the presentation commands are due to be executed. If so, these commands are executed and then the commands and their associated objects are deleted from the memory. The presentation processor also monitors messages received from its corresponding customer indicating that an interactive feature has been selected. On receiving such a message, the presentation processor determines whether the interactive feature is enabled. If so, the presentation processor sends a message to the delivery processor indicating the customer's selection of the interactive feature.

Through our inventive, preprocessing and delivery system, multimedia presentations, which are conventionally delivered according to requests from a customer's CPE, are delivered based on a delivery schedule which ensures that each presentation command and associated object are delivered to the presentation processor prior to its presentation time even if an interactive feature is selected by the customer. Furthermore, the interactive response time of our system is virtually zero and remains so independent of the number of simultaneous customers actually being served by the delivery processor up to a fixed maximum. This result is not achievable in conventional systems employing the traditional client-server model, which systems have a greater than zero interactive response time that progressively worsens as more customers are simultaneously served by the conventional system.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1A depicts, from the prior art, an illustrative embodiment of a delivery system employing a prior client-server model for transporting multimedia presentations to customers.

FIGS. 1B and 1C depict a table and graph, respectively, of objects representing an original multimedia presentation for illustrative purposes.

FIG. 1D depicts on interaction table corresponding to the original multimedia presentation of FIGS. 1B and 1C.

FIG. 1E depict the delivery of Objects 1 through 7, consecutively, over a prior delivery system operating under a traditional client-server model.

FIG. 2 depicts an illustrative embodiment of our multimedia preprocessing and delivery system for preprocessing and delivering multimedia presentations to customers, in accordance with our invention.

FIG. 3 depicts an illustrative embodiment of our multimedia preprocessor in accordance with our invention.

FIG. 4 depicts an illustrative embodiment of our delivery processor in accordance with an aspect of our invention.

FIG. 5 depicts an illustrative embodiment of our presentation processor in accordance with an aspect of our invention.

FIG. 6A depicts a table of the delivery times of preprocessed multimedia presentation corresponding to the original multimedia presentation of FIGS. 1B and 1C, in accordance with an aspect of our invention.

FIG. 6B depicts a labelled, directed graph representing a delivery schedule for the preprocessed multimedia presentation, in accordance with an aspect of our invention.

FIGS. 7A through 7E depict flow diagrams showing a representative embodiment of our preprocessing method, in accordance with an aspect of our invention.

FIG. 8 depicts a flow diagram showing a representative embodiment of our delivery method in accordance with an aspect of our invention.

FIG. 9 depicts a flow diagram showing a representative embodiment of our presentation method, in accordance with an aspect of our invention.

The organization and operation of the invention will be better understood from a consideration of the detailed description of the illustrative embodiments thereof, which follow, when taken in conjunction with the accompanying drawing.

DETAILED DESCRIPTION OF THE INVENTION

Our invention is a system and method for preprocessing and delivering multimedia presentations to customers. Our inventive system and method entail preprocessing an original multimedia presentation (OMP), comprising multimedia objects and presentation commands, to generate a preprocessed multimedia presentation (PMP), which includes a delivery schedule for delivering the presentation. In generating the delivery schedule, the OMP is analyzed and the time at which each object of the presentation is to be presented to the customer and the interactive features available for customer selection in the presentation are taken into consideration. Furthermore, the characteristics of the system components, which will deliver the presentation, and the round trip latency between system components are considered. Specifically, objects along a main presentation path of the OMP, which are objects to be presented independent of the customer's selection of an interactive feature, are scheduled for delivery such that each presentation command and associated object will be available for presentation to the customer prior to the presentation time of the object despite transmission delays inherent to the delivery system and the number of simultaneous customers actually being simultaneously served by the delivery system. Furthermore, objects along a sub-presentation path of the OMP, which are conventionally delivered to the customer only after an appropriate customer interaction has been selected, are scheduled for pre-delivery in anticipation of the customer's interaction such that delays due to interactive response time are essentially eliminated.

FIG. 2 depicts an illustrative embodiment of our multimedia preprocessing and delivery system 100. Our system 100 includes a multimedia preprocessor 200, a mass storage 300, a delivery processor 400, a distribution network 500, and a plurality of presentation processors 600-1 through 600-N. The preprocessor 200 receives an OMP, which comprises multimedia objects and associated presentations commands for presenting the multimedia objects to a customer based upon the customer's interactive commands under a traditional client-server model. The preprocessor 200 also receives other inputs called presentation technology parameters (PTPs) which indicate key information characterizing components of system 100, which components are employed in delivering the presentation to a customer. This key information includes the round trip latency (RTL) between the delivery processor and the presentation processor, which RTL is the time for a 1 bit message to be sent from the presentation processor to the delivery processor and a response from the delivery processor to be received at the presentation processor. The PTPs also include the bit rate of distribution network and the memory capacity of the presentation processor. Based upon these inputs, the preprocessor generates a PMP.

In addition to the multimedia objects and presentation commands of the OMP, the PMP includes a delivery schedule to be executed by the delivery processor 400 for delivery of the presentation virtually without delays due to interactive response time.

The PMP generated at preprocessor 200 is stored at mass storage 300, which is connected to the preprocessor 200 via output 250 and which stores PMPs available for delivery on customer request. The delivery processor 400 is in communication with the presentation processors 600-1 through 600-N, which correspond to customers 601-1 through 601-N, respectively, via the distribution network 500. Upon receiving a request from a customer for a multimedia presentation, the delivery processor 400 retrieves the requested PMP from storage 300. The delivery processor 400 executes the delivery schedule embedded in the PMP and delivers the multimedia objects and presentation commands to the presentation processor corresponding to the requesting customer. The presentation processor 600 presents the multimedia objects to the customer according to presentation commands. The presentation processor 600 also receives messages from its customer, which messages may include the customer's selection of an interactive feature, and on receiving such a message, the presentation processor 600 forwards a message to the delivery processor 400 advising it of the customer's selection.

The distribution network 500 interconnecting the delivery processor 400 and the presentation processors 601-1 through 601-N comprises transmission equipment and transmission links of fiber optic, coaxial, or copper cable or other suitable transmission medium. Specifically, the distribution network could be the distribution portion of a public switched telephony network (PSTN), which employs Integrated Services Digital Network (ISDN) technology operating at a basic rate of 128 Kb/s or asymmetrical digital subscriber line (ADSL) technology, which provides transport at 1.5 Mb/s, downstream, and a few kilobits/second, upstream, overlaid on a telephony channel. Alternatively, the distribution network 500 could also include a local area network.

MULTIMEDIA PREPROCESSOR

A detailed depiction of an illustrative embodiment of our multimedia preprocessor 200 is shown in FIG. 3. The preprocessor 200 receives as an input at input port 210 an OMP, which is stored in OMP storage 201 and which may have been created using any of the well-known multimedia authoring systems. Such systems allow authors to create presentations including formatted multi-font text, animations, graphics images, photographic images, audio and motion video. Many of these systems, such as Macromedia's Authorware Professional, provide a graphical user interface enabling authors to create presentations by manipulating images on a computer display.

The output of the authoring system may not be in a format suitable as input to the preprocessor 200. Therefore, the output of the authoring system may require a software translation into the format suitable for the preprocessor 200. For purposes of discussion, it is assumed that the OMP is in a format acceptable to the preprocessor 200. An illustrative OMP is depicted in FIGS. 1B and 1C and is described in the Background of the Invention.

Another input to the preprocessor 200 at input port 230 is the presentation technology parameters (PTPs), which define characteristics of the delivery processor 400, the distribution network 500, and the presentation processor 600. The PTPs include the minimum bit rate of the distribution network 500, the maximum memory capacity of the presentation processor 600, and the round trip latency (RTL) between the delivery processor 500 and the presentation processor 600. The PTPs may be manually inputted at input port 230 from a human interface. Alternatively, the preprocessor may request the PTP from the system component being characterized by the PTP. For example, the preprocessor could prompt presentation processor 600-1 for its memory capacity, the delivery processor for the RTL between the delivery processor 400 and presentation processor 600-1, and the distribution network, connecting the delivery processor 400 and presentation processor 600-1, for its bit rate. Each component prompted by the preprocessor would electronically transmit the requested PTP to the preprocessor at input port 230. The delivery processor includes a PTP generator 407 (discussed infra), which transmits signals to and and receives signals from a presentation processor to measure a RTL as input to the preprocessor. Based on the PTPs and the OMP, the preprocessor 200 generates at output port 250 a PMP, which includes a delivery schedule comprising delivery commands to be executed by the delivery processor for delivery of the presentation to the presentation processor 500.

The preprocessor 200 comprises an OMP store 201 for receiving and storing the presentation to be preprocessed and a PTP store 203 for receiving and storing these parameters to be used during preprocessing. The preprocessor also includes a memory counter 206 for tracking the available memory at the memory store 603 (See FIG. 5, discussed infra) of the presentation processor 600 as multimedia objects are scheduled for delivery. The preprocessor 200 also includes an active clock 208 for tracking the current time into the presentation along a particular path of the presentation and associated with a particular clock.

Additionally, the preprocessor 200 comprises a presentation scheduler 205 which controls the preprocessing of the OMP. The presentation scheduler 205 assesses the objects to be delivered and their associated presentation times and the interactive features that may be selected by the customer during pre-specified intervals of the presentation. Considering the results of this assessment and the PTPs defining the characteristics of the delivery system which is to deliver and present the presentation, the presentation scheduler 205 generates a PMP comprising a delivery schedule for delivering the presentation such that interactive response delays and gaps in the presentation are virtually eliminated. In the case where a delivery schedule cannot be generated for a presentation to avoid such delays and gaps, the presentation scheduler 205 causes a message generator 207 to relay an error message indicating that an optimal delivery schedule is unachievable for the presentation over a delivery system having the specified PTPs.

In generating the delivery schedule, the presentation scheduler analyzes the objects, their associated presentation times, and optional customer interactive features. The presentation scheduler 205 then generates delivery commands which comprise the delivery schedule such that:

1) each presentation command and its associated object arrive at the presentation processor no later than the time at which the object is to presented;

2) any presentation command and associated object delivered to the presentation processor can be accommodated at the memory of the presentation processor; and

3) the interactive response time due to the customer's selection of an interactive feature is virtually eliminated.

For certain OMPs, it may not be possible to produce a delivery schedule meeting these constraints. In such cases, the presentation scheduler 205 may cause the message generator 207 to report an error and may halt the preprocessing operation.

The delivery schedule generated by the presentation scheduler during preprocessing can be best described as a labelled, directed graph, G, comp