1
$\begingroup$

I am a newbie to graph theory and this may possibly be quite a strange quesion.

Can a graph exist such that contains both weighted and unweighted edges? If yes, could you also let me know what can be a practical application of such a graph?

I am now writing a tiny program that tries to do a requested job, e.g. to find the shortest path with a given graph, source, and destination. I am wondering what to do if the given graph contains both weighted and unweighted edges. If it is an impossible case at all, then I can feel free to simply throw an exception. But, if it is a possible case, then I would like to study it further more.

Thank you.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

A tricky question. From a programming perspective, I suspect that you have (in pseudocode):

if edge has a weight:
     process(edge)
  else:
     ???

however, this will probably never be an issue. Say there is a real world problem where you might have both weighted and unweighted edges; say some kind of metabolic network, with edges that represent boolean bound/unbound and edges that represent enzyme transformation with some probability. Possibly unrealistic, but whatever.

To model this, it would be easiest to use a weight of 0 for the unweighted edges so that all edges have weight. Of course, it has to make sense for your shortest path to include both 'types' of edge in the first place!

The only difficulty would be in the unlikely case where an edge with a weight of 0 means something different to an unweighted edge. A little like the difference between null/0 in many languages. From a design point of view, it might be best to not design for weird edge cases until you find them.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.