# graph with its demands

• 07-22-2013, 02:21 PM
pegool
graph with its demands
hello i am new to java
I need to write a graph with some nodes v={1,2,3,4,5,6,7} and edges E={(1-2),(2-3), (3,4),(4-7), (3-6), (2-6), (5-6), (1-5)} and also with some demands D=(s,d)={(1-3),(2-3), (4-5). (7-7), (6-4),(2-7)} which are some path with an exact source an destination for this network. How can I write this in Java? Can anyone help me please?
• 07-23-2013, 06:10 AM
kjkrum
Re: graph with its demands
I've never encountered the term "demands" in relation to graphs... but a graph is completely defined by its nodes and edges. Seems like you just need to write classes for Node and Edge and give them the appropriate properties.
• 07-23-2013, 09:30 AM
JosAH
Re: graph with its demands
Nodes can have 'supplies' or 'demands'. The sum of both can be equal and the problem can be solved such that the costs over each edge is minimal. It's a classic assignment or transportation problem. But we don't know if the OP wants to solve anything or just make a model for the problem (which is a graph with supplies/demands on the vertices). The OP has to give more details ...

kind regards,

Jos
• 07-23-2013, 07:28 PM
kjkrum
Re: graph with its demands
Ah. Are supply and demand related to flow? Sounds like it might be the same properties I learned to call source and sink.
• 07-23-2013, 07:37 PM
JosAH
Re: graph with its demands
Quote:

Originally Posted by kjkrum
Ah. Are supply and demand related to flow? Sounds like it might be the same properties I learned to call source and sink.

Yep, flow goes over the edges/arcs, as much as supply/demand dictate; the generalized problem is an mcnf (Minimal Cost Network Flow) problem which has an integer solution iff the demands and supplies are integer. Solving such a problem if it has upperbounds on flow over its edges can be nasty if you have the wrong representation of the graph ...

kind regards,

Jos