Re: [Help-glpk] implementation of graphs and networks in glpk

[Andrew Makhorin]

>From my perspective as a network flow user, your graph
> and support types look perfectly reasonable.  The
> terminology is fine.  The use of an incidence list is
> probably a good choice.

Thanks. The design was inspired by the Stanford GraphBase developed
by Don Knuth <http://www-cs-faculty.stanford.edu/~knuth/sgb.html>.
The main difference is using data blocks associated with each vertex
and arc; this seems to be much more flexible than using a fixed set of
utility fields.

> Will there be restrictions on the graph objects, for
> instance, will parallel arcs be acceptable?  I guess
> that depends on the algorithm in use.  In which case,
> can you match structural restrictions with graph
> algorithms when programming in C?  And, if so, would
> you want to?

On a base level there are no restrictions--self-loops and multiple
arcs are allowed. Of course, particular restrictions as well as
interpretation of graph components depend on the problem to be solved.

> That then prompts the question of which network
> algorithms do you propose to implement?  Least-cost
> flow, maximum flow, minimum flow? (I use all three).
> And so on!

I plan to include routines for the minimum-cost flow, maximum flow,
assignment, and transportation problems, and some additional routines
for graph and network analysis.

> I also work with nested graphs.  I don't suppose there
> will be support for a graph of sub-graphs (as the
> Boost.Graph library does) (my client code should deal
> with that I guess!).

> On a design level, is this new graph type a stand-alone
> data structure?  Or is it a convenience data structure
> which is really a 'glp_prob' deep down?

Glp_graph is a separate data structure not related with glp_prob.
However, there may be a logical relation if the problem is formulated
on a graph and needs to be solved with glp_intopt.

> Will the user be able to solve their resulting
> least-cost flow network problem using both
> 'glp_simplex' and 'glp_netsolve' (or whatever the call
> will be)?  Or can one convert a graph object to a
> 'glp_prob' object to do so?  And vice-versa?

If the min-cost flow problem is formulated as a network problem,
there is no need to convert it to lp, though it is always possible.


Andrew Makhorin