INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• 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.

# Design a DTD to represent the data model for DAGs

## Design a DTD to represent the data model for DAGs

(OP)
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:

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

<!ATTLIST dag name ID #REQUIRED>
<!ATTLIST node label ID #REQUIRED>
<!ATTLIST h_node label IDREF #REQUIRED>
<!ATTLIST t_node label IDREF #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.

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:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!