Author |
Topic: problem in implementing a research paper (Read 516 times) |
|
ONS
Newbie
Gender: 
Posts: 41
|
 |
problem in implementing a research paper
« on: Mar 26th, 2010, 7:40am » |
 Quote  Modify
|
i was going through a research paper-"Efficient Identification of Design Pattern with Bit-Vector Algorithm" when i got struck at one place-
"A digraph is typically not Eulerian, i.e., it does not contain a Eulerian circuit, a cycle which uses each edge exactly once. We transform a digraph of a design motif or of a program in a Eulerian graph automatically and consistently. A directed graph is Eulerian if and only if every vertex has equal in-degree and out-degree (respectively the numbers of incoming and outgoing edges for a vertex). The transformation consists in adding dummy edges between vertices with unequal in-degree and out-degree. We use the transportation simplex to obtain the number of dummy edges to be added
among vertices. We consider the vertices with greater in-degree as suppliers and the vertices with greater out-degree as demanders. We assume uniform unitary shipping costs between suppliers and demanders. The transportation simplex computes the optimal solution (minimum cost), a list of flows among suppliers and demanders. In our case, a flow represents a dummy edge between vertices. If the flow is greater than one, then as many dummy edges must be added between
the vertices."
i have following doubts:
a) shouldn't the total no. of outgoing arcs be equal to total no. of incoming arcs. i.e total outgoing arcs from suppliers= total incoming arcs for demanders.
b) from highlighted portion we find the cost to be unitary along any path.
if above assumptions are correct then where do we find the need of using the simplex algorithm? Can't we randomly add dummy edges between suppliers and demanders?
hope i made myself clear...
|
|
 IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: problem in implementing a research paper
« Reply #1 on: Mar 26th, 2010, 8:40am » |
Quote Modify
|
I'm not sure, but I think the difficulty is this: assuming the digraphs can't have multiple directed edges, if a supplier and a demander already have a bidirectional edge between them, you can't add more edges between them. Although the last sentence seems to suggest the digraphs might be allowed to have multiple edges.
In fact, the first example graph on the Wikipedia page for Directed graph has this feature: while there is one supplier and one demander, you can't add another directed edge between them to make the graph Eulerian, since that edge is already bidirectional. In this case, the only way to make the graph Eulerian is to make all edges bidirectional.
If you are allowed to add multiple edges, then I agree that the problem is trivial assuming all edges have the same cost. Just link suppliers to demanders arbitrarily at random and you'll arrive at a solution with a minimum number of edges.
|
| « Last Edit: Mar 26th, 2010, 8:41am by Obob » |
IP Logged |
|
|
|
ONS
Newbie
Gender:
Posts: 41
|
|
Re: problem in implementing a research paper
« Reply #2 on: Mar 26th, 2010, 11:19am » |
Quote Modify
|
i suppose you didnt get my question.... surely multiple edges are allowed. Problems comes as the author is giving unitary cost to each edge and as you assert in last sentence the problem becomes trivial. So, where is the need of the transportation simplex algorithm?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print