
Boost Users : 
Subject: Re: [Boostusers] [BGL] Is it possible to control algorithm's behavior by visitor?
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 20090522 06:53:58
[snip]
>
> OK!
> Well, the problem come from telecom. In telecom, network element can be
> viewed as vertex. network element is a device that can be plug in
> "lines"(optic, ethernet or anything can transmit data). These "lines" have a
> character: composited by 2 transmition medium. So if 2 network element was
> connected by a line, you can send data from source to target or from target
> to source. But notice that 2 direction has independent band width. For
> example, a 5M line connect vertex A & B, you can establish a connection
> between A & B. This connection have 2 type: uni or bi.
> A bidirection connection means you can send data from A to B AND B to A at
> max width 5M.
> A unidirection connection means you can ONLY send data from A to B OR B to
> A(depend on connection's source & destination), the line between A & B has
> been used only one capacity. That is, only one transmition medium in this
> line has been used. So, a line can contain 2 uni connection(one is A to B,
> another is B to A) or 1 bi connection.
>
> This problem requires dijkstra algorithm accept one more parameter: Path's
> Direction.
At this point you still have not stated the problem!
Is it something like this? :
Given a graph G=(V,E,T,C), V is a set of vertices; E is the set of
edges. Each edge has two integer properties: edge type T: E > {UNI, BI}
and edge capacity C: E > INT. Given two vertices: "s" (start vertex)
and "f" (finish vertex) and a path_type (uni or bi). Your task is to
find a shortest path P from start vertex "s" to finish vertex "f" (the
weight map is C ??) such that all edges of this path are of the
corresponding type (uni or bi), i.e., for each edge e \in P, T(e) ==
path_type.
It is quite strange to be true. First of all because we are trying to
find a path with the smallest bandwidth. Something should be added to
this formulation. Does your graph have cycles? Please, provide a small
example (a graph with several vertices and edges).
> BGL have not this.
> This problem requires graph can not be a directedgraph. Because a bi
> connection can not go through different "line".
> This problem requires graph has it runtime type, that is, when routing
> uniconnection, graph should be a directedgraph. when routing
> biconnection, graph should be a undirectedgraph. If we need to avoid
> recreate graph when connection direction type changes, we must...customize
> BGL.
>
> The best solution I can figure out is reduce the problem to a undirectgraph
> but its edge has complex properties. These properties value affect algorithm
> behavior.
> The problem is: how to do this??
>
> recreation graph is easy. But this creation cost is high: based on a graph,
> routing 100,000 connections need to create graph 100,000 times in worst
> case.
Dmitry
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net