Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Design a DTD to represent the data model for DAGs

Design a DTD to represent the data model for DAGs

Design a DTD to represent the data model for DAGs

Dear all,

I am really stuck on this question and am really struggling as the deadline approaches. So I was wondering if any of you have any ideas that you can share with me. The question is as follows:

A Directed acyclic graph (DAG) has a unique name and consists of a set of nodes and a set of edges. Each node has a label that uniquely identifies it. A node may be a part of more than one graph. Each edge connects two distinct nodes and has an edge weight. An edge is directed from a "head" node to a "tail" node, i.e., an edge connecting head node u to tail node v is different from an edge connecting head node v to tail node u .

In a single graph, given a head node and a tail node, there is at most one edge from the head node to the tail node. A single graph may contain an edge from u to v and an edge from v to u , since these two edges are distinct. In addition, an important property of a DAG is that it does not have any cycles. A sequence of nodes forms a cycle if an edge connects each node in the sequence to the next node in the sequence and an edge also connects the last node in the sequence to the first.

(a) Design a DTD to represent the data model for the DAGs
(b) Is it possible to model the fact that a DAG does not contain a cycle? Justify your answer.

All I have managed is this so far:

<!ELEMENT dags (dag+)>
<!ELEMENT dag (node+, edge+)>
<!ELEMENT edge (h_node, t_node, weight)>
<!ELEMENT weight (#PCDATA)>

<!ATTLIST node label ID #REQUIRED>

Any help will greatly appreciated. Thank you for reading.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close