A dynamic time expanded network. More...

#include <Net.hxx>

Data Structures
class	BaseInIterator
	Iterator over the incoming arcs of a base node. More...

class	BaseInList
	Wrapper to provide an iterator over the incoming arcs of a base node. More...

class	BaseOutIterator
	Iterator over the outgoing arcs of a base node. More...

class	BaseOutList
	Wrapper to provide an iterator over the outgoing arcs of a base node. More...

class	InIterator
	Iterator over the incoming arcs of a node. More...

class	InList
	Wrapper to provide an iterator over the incoming arcs of a node. More...

class	OutIterator
	Iterator over the outgoing arcs of a node. More...

class	OutList
	Wrapper to provide an iterator over the outgoing arcs of a node. More...

Public Types
enum	Result { Result::Solved =1, Result::Expanded =2 }
	Return states of the shortest path computation. More...

typedef index_type	Group
	Type of groups.

typedef index_type	BaseNode
	Type of base nodes.

typedef index_type	BaseArc
	Type of base arcs.

typedef index_type	Node
	Type of nodes.

typedef index_type	Arc
	Type of arcs.

typedef index_type	Time
	Type of time indices.

typedef index_type	RunTime
	Type of running times.

Public Member Functions
	Net ()
	Constructor. More...

	~Net ()
	Destructor.

	Net (const Net &net)=delete
	No copy constructor.

Net &	operator= (const Net &net)=delete
	No assignment operator.

	Net (Net &&net)
	Move constructor.

Net &	operator= (Net &&net)
	Move assignment operator.

Base graph functions
index_type	n_groups () const
	Return the number of groups in the base graph. More...

Group	add_group ()
	Add one group to the base graph. More...

Group	add_groups (index_type ngroups)
	Add several groups to the base graph. More...

index_type	n_basenodes () const
	Return the number of base nodes. More...

BaseNode	add_basenode (Group group)
	Add a base node to the network. More...

Group	base_group (BaseNode bnode) const
	Returns the index of the group of a base node. More...

index_type	base_groupidx (BaseNode bnode) const
	Returns the number of the node in its group. More...

bool	base_waitnode (BaseNode bnode) const
	Returns true if the base node is a wait node. More...

BaseArc	base_firstout (BaseNode bnode) const
	Return first outgoing arc of a node in the base graph. More...

BaseArc	base_firstin (BaseNode bnode) const
	Return first incoming arc of a node in the base graph. More...

index_type	n_basearcs () const
	Return the number of base arcs. More...

BaseArc	add_basearc (BaseNode bsrc, BaseNode bsnk)
	Add an arc to the base graph. More...

BaseArc	base_arc (BaseNode bsrc, BaseNode bsnk) const
	Returns the id of a base arc. More...

void	add_runningtime (BaseArc arc, RunTime running_time)
	Add one possible running time to a base arc. More...

void	add_runningtimes (BaseArc arc, std::size_t ntimes, const RunTime running_times[])
	Add several possible running times to a base arc. More...

void	add_runningtimes (BaseArc arc, const std::vector< RunTime > &running_times)

BaseArc	base_nextout (BaseArc arc) const
	Return the next outgoing base arc. More...

BaseArc	base_nextin (BaseArc arc) const
	Return the next incoming base arc. More...

BaseNode	base_src (BaseArc arc) const
	Return the number of the source base node of a base arc. More...

BaseNode	base_snk (BaseArc arc) const
	Return the number of the sink base node of a base arc. More...

BaseOutList	base_outarcs (BaseNode bnode) const
	Return a list of outgoing arcs of a base node.

BaseInList	base_inarcs (BaseNode bnode) const
	Return a list of incoming arcs of a base node.

Time expansion functions
void	init ()
	Initializes the time expansion. More...

Time	group_mintime (Group group) const
	Return the minimal possible time associated with a group. More...

Time	basenode_mintime (BaseNode bnode) const
	Return the minimal possible time associated with a basenode. More...

index_type	n_nodes () const
	Returns the number of nodes in the time expansion. More...

Node	node (BaseNode bnode, Time time) const
	Returns the id of a node in the time expansion. More...

BaseNode	basenode (Node node) const
	Returns the id of the base node associated with a node. More...

Time	time (Node node) const
	Returns the time index associated with a node in the time expansion. More...

Arc	firstout (Node node) const
	Returns the id of the first outgoing arc in the time expansion. More...

Arc	firstin (Node node) const
	Returns the id of the first incoming arc in the time expansion. More...

index_type	n_arcs () const
	Returns the number of arcs in the time expansion. More...

Arc	arc (Node src, Node snk) const
	Returns the id of an arc in the time expansion. More...

Arc	find_arc (BaseNode bsrc, Time srctime, BaseNode bsnk, Time snktime) const
	Returns the id of an arc in the time expansion. More...

bool	isactive (Arc arc) const
	Returns true iff the given arc is contained in the active subgraph. More...

Node	src (Arc arc) const
	Returns the id of the source node of an arc in the time expansion. More...

Node	snk (Arc arc) const
	Returns the id of the sink node of an arc in the time expansion. More...

Arc	nextout (Arc arc) const
	Returns the id of the next outgoing arc in the time expansion. More...

Arc	nextin (Arc arc) const
	Returns the id of the next incoming arc in the time expansion. More...

OutList	outarcs (BaseNode bnode) const
	Return a list of outgoing arcs of a node.

InList	inarcs (BaseNode bnode) const
	Return a list of incoming arcs of a node.

Shortest path functions
void	force_active (Group grp, Time time_active)
	Forces the active subgraph to contain certain arcs. More...

Time	active_time (Group grp) const
	Return the active subgraph boundary for the given group.

Result	shortest_path (const double basecosts[], const double augcosts[], index_type &nnodes, index_type &narcs)
	Solve the shortest path problem. More...

Result	shortest_path (const std::vector< double > &basecosts, const std::vector< double > &augcosts, index_type &nnodes, index_type &narcs)

Result	shortest_path (const double basecosts[], const double augcosts[])

Result	shortest_path (const std::vector< double > &basecosts, const std::vector< double > &augcosts)

index_type	get_n_newnodes () const
	Return number of new nodes of last expansion.

index_type	get_n_newarcs () const
	Return number of new arcs of last expansion.

index_type	get_pathlen () const
	Return the length of the shortest path. More...

double	get_path (Arc path[]) const
	Returns the latest computed shortest path. More...

double	get_path (std::vector< Arc > &path) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

index_type	get_num_new_active () const
	Return the number of newly activated arcs. More...

void	get_new_active (Arc active[]) const
	Return the list of newly activated arcs. More...

void	get_new_active (std::vector< Arc > &active) const
	Return the list of newly activated arcs. More...

Static Public Attributes
static const Node	nonode = -1
	ID of a non-existing node.

static const Arc	noarc = -2
	ID of a non-existing arc.

Detailed Description

A dynamic time expanded network.

This is the central class representing a time expanded network. In the following we give a formal definition of time expanded networks as they are understood by this class as well as the problems to be solved with the help of this class. For an in-depth discussion on the topic of dynamic graph generation we refer to [1].

Warning: The current implementation only supports base graphs that are paths up to groups (i.e. the group graph must be a path).

Contents:

Theoretical Background

In this section we give a short overview over the theoretical ideas behind the dynamic graph generation approach implemented in this class.

Time expanded networks

A time expanded network is defined as follows.

Let $G=(V,A)$ be a finite, acyclic (except for loops), connected, directed graph with a unique source node $\usrc$ and a sink node $\usnk$ . Furthermore, assume that the nodes can be partitioned into so called groups (or equivalence classes) $[u], u \in V$ . The groups must satisfy the following three properties:

$u,v\in [w], u \neq v \then (u,v) \notin A$ (note, loops are allowed inside a class),
$(u,v) \in A \then [u] \times [v] \subseteq A$ , -# $[\usrc] = \{\usrc\}, [\usnk] = \{\usnk\}$ .

The graph $G$ is called the base graph of the time expanded network. In order to define the time expansion of $G$ let $\T=\{0,1,2,\dotsc\}$ be the set of (discrete) time steps. Each arc of the base graph is assigned a non-empty, finite set of non-negative transfer times

$\tr\colon A \to 2^{\N_0} \setminus \{\emptyset\},$

such that $\tr((u,u)) = \{1\}$ for each loop $(u,u) \in A$ .

The follow picture shows an example of a base graph with exactly one running time assigned to each arc.

Fig1: Example base graph with alternative routes. The numbers at the arcs are the (single) transfer times for that arc. The dashed boxes mark the groups of base nodes. Each group consists of up to two nodes and waiting (loops) is allowed only at the black nodes.

The time expansion of $G$

is the graph $\Gt=(\Vt,\At)$ with

$\begin{align*} \Vt & := \left\{(u,t_u)\colon u \in V, t_u \in \T\right\} \\ \At & := \left\{((u,t_u),(v,t_v)) \in \Vt\times\Vt\colon (u,v) \in A, t_v - t_u \in \tr((u,v))\right\} \\ \end{align*}$

The following picture shows the time expansion of the above base graph.

Fig2: Time expansion of the previous base graph.

The shortest path problem in time expanded networks

The problem to be solved in $\Gt$ is a to find a minimum-cost path from a node $(\usrc,0) \in \Vt$ to a node $(\usnk,t) \in \Vt$ . For this, the user has to provide a weight function that assigns each arc of $\Gt$ a weight:

$c\colon \At \to \R.$

Note that $\Gt$ is acyclic, so negative weights are allowed. The problem to be solved is then

$\begin{align*} \operatorname{minimize}\quad & \sum_{a \in \At} c(P), \\ \text{subject to}\quad & P \in \Pths, \end{align*}$

where

$\Pths := \{P \subset \Gt\colon P \text{ is $(\usrc,0)$-$(\usnk,t)$ path in \Gt}\},$

and

$c(P) := \sum_{a \in \At(P)} c(a)$

denotes the sum of the weights of the edges in the path $P \in \Pths$ .

There are several difficulties in solving this problem mainly related to the fact that the time expansion $ $\Gt$ is extremely large, even infinite in the definition above. This has several theoretical and practical consequences:

the shortest path problem might not have an optimal solution,
the memory requirements to store $\Gt$ or even only the weight function might be very high.

Dynamic Graph Generation

In order to overcome these problems, the dynamic graph generation approach has been developed in [1]. The idea is to store only a small finite subgraph $\Gcur \subseteq \Gt$ and to solve the shortest path problem only on $\Gcur$ . The algorithm then automatically detects whether the resulting path is a solution of the shortest path problem on the whole graph $\Gt$ or otherwise enlarges $\Gcur$ by adding further nodes and arcs. Then the shortest path problem is resolved on the enlarged graph. It can be shown that, under some conditions, this approach finds a shortest path in $\Gt$ after a finite number of iterations.

In order to be able to apply the dynamic graph generation approach, several conditions on the weight function $c$ must be satisfied.

there must exist a finite optimal solution of the shortest path problem in $\Gt$ (e.g. if the weights grow for $t\to\infty$ )
the weight functions must have the form such that -# for all arcs that are not contained in the so called active subgraph , which is managed by this Net class.
1. $\cbase(P) \le \cbase(Q)$ for any path that visits no group later than (for the exact condition see [1]).

The most important condition to ensure is the last one, which is a structural assumption on the basic objective function. The non-negativity condition on $\caug$ , however, is often met easily depending on the problem context. For instance, dynamic graph generation is designed to be used in Lagrangian relaxation approaches, where $\caug$ corresponds to the augmented costs induced by the Lagrangian multipliers of some coupling constraints. If these coupling constraints are inequalities with non-negative coefficients (which is typically the case for resource constraints), these augmented costs are automatically non-negative.

Remark: although the split of $c$ into $\cbase$ and $\caug$ is often defined by the problem context, any valid decomposition works. In fact, one only has to ensure that $\cbase$ is a lower bound (but increasing) on the real objective functions so that the residual term $\caug = c - \cbase$ is non-negative. In fact, $\cbase$ can be thought of a well behaving, convex lower bound on $c$ . However, a tighter (larger) $\cbase$ typically leads to less iterations of the dynamic graph generation cycle until the shortest path in $\Gt$ is found (and keeps the stored subgraph $\Gcur$ smaller). Hence, it is favorable to choose $\cbase$ as large as possible.

Using the class Net

In this section we describe how to use the Net class for implementing a dynamic graph generation approach. The Net class consists of the following three components:

It represents the base graph : Defining the Base Graph -# It creates and handles the time expansion $\Gt$ : Working with the Time Expanded Network
In particular, it tracks the current subgraph $\Gcur \subseteq \Gt$ and the active subgraph $\Gact \subseteq \Gcur$ , possibly enlarging them automatically during shortest path computations.
It provides methods to solve the shortest path problem on $\Gt$ w.r.t. a user defined objective function: Solving the Shortest Path Problem

Defining the Base Graph

The first step in using Net is to specify the base graph $G=(V,A)$ . The base graph consists of a finite set of nodes $V=\{0,...,n-1\}$ and arcs $A=\{0,...,m-1\}$ . Nodes and arcs are always numbered starting at 0, a new node or arc is assigned the smallest unused integer number. Furthermore, the set of base nodes is partitioned into a family of groups, also numbered from $i=0,\dotsc,g-1$ . Finally, each base arc is associated with a finite number of non-negative integer running times.

In order to specify the base graph one has to do the following steps: -# add the required number of groups $i=0,\dotsc,g-1$ using the methods Net::add_group and Net::add_groups,

add the required base nodes $u=0,\dotsc,n-1$ with their associated group using Net::add_basenode
add the base arcs $a=0,\dotsc,m-1$ by specifying their source and sink nodes using Net::add_basearc,
specify the set of running times for each arc $a=0,\dotsc,m-1$ using Net::add_runningtimes.

A wait node $u$ is specified by adding a loop $(u,u)$ . Note that the only valid running time for loops is $1$ .

The base graph can be queried by iterating over the incoming and outgoing arcs of a node using the methods Net::base_firstin, Net::base_nextin, Net::base_inarcs and Net::base_firstout, Net::base_nextout, Net::base_outarcs.

The following code demonstrates how to create the base graph shown in Fig1.

using namespace Dyng;
Net net;
// add groups
net.add_groups(8);
// List of all running times of transfer arcs.
enum What { Run=0, Wait=1 };
typedef std::tuple<Net::Group, What, Net::Group, What, Net::RunTime> R;
const auto RTimes = {
    R{0, Run, 1, Run, 0},
    R{0, Run, 1, Wait, 0},
    R{1, Run, 2, Run, 1},
    R{1, Run, 2, Wait, 2},
    R{1, Wait, 2, Run, 2},
    R{1, Wait, 2, Wait, 3},
    R{2, Run, 3, Run, 0},
    R{2, Run, 3, Wait, 1},
    R{2, Wait, 3, Run, 1},
    R{2, Wait, 3, Wait, 2},
    R{3, Run, 4, Wait, 1},
    R{3, Wait, 4, Wait, 2},
    R{4, Wait, 6, Run, 0},
    R{4, Wait, 6, Wait, 1},
    R{2, Run, 5, Run, 1},
    R{2, Wait, 5, Run, 3},
    R{5, Run, 6, Run, 0},
    R{5, Run, 6, Wait, 1},
    R{6, Run, 7, Run, 0},
    R{6, Wait, 7, Run, 0}
};
// add nodes
std::vector<std::vector<Net::Node> > nodes(8, {Net::nonode, Net::nonode});
for (auto rt : RTimes) {
    auto i = std::get<0>(rt);
    auto what = std::get<1>(rt);
    if (nodes[i][what] == Net::nonode) nodes[i][what] = net.add_basenode(i);
}
// add the final node
nodes[7][Run] = net.add_basenode(7);
// add wait arcs (loops)
for (auto n : nodes) {
    auto u = n[Wait];
    if (u != Net::nonode) net.add_basearc(u, u);
}
// add transfer arcs and running times
for (auto rt : RTimes) {
    Net::Group i, j;
    What wi, wj;
    Net::RunTime t;
    std::tie(i, wi, j, wj, t) = rt;
    auto u = nodes[i][wi];
    auto v = nodes[j][wj];
    auto a = net.add_basearc(u, v);
    net.add_runningtimes(a, {t});
}

Working with the Time Expanded Network

The time expansion $\Gt$ or, more accurately, the subgraph $\Gcur$ , is generated automatically. The graph is initialized by calling Net::init after creating the base graph. After calling Net::init the base graph must not be modified anymore.

The nodes and arcs of the time expansion may be queried in very much the same way as the base graph. Furthermore Net contains methods to query attributes of the nodes and arcs, e.g., the associated base node and time indices associated with a node. In particular, the attribute Net::isactive returns a flag indicating whether an arc is contained in the active subgraph $\Gact$ or not.

The following code prints some information about all nodes and arcs in the time expansion.

Net net;
...
net.init();
for (auto u = 0; u < net.n_nodes(); u++) {
    std::cout << "node:" << u
              << " basenode:" << net.basenode(u)
              << " time:" << net.time(u)
              << " wait:" << net.base_waitnode(net.basenode(u))
              << std::endl;
    std::cout << "  incoming arcs";
    for (auto a : net.inarcs(u)) {
        std::cout << "    arc:" << a << " to:" << net.snk(a) << std::endl;
    }
    std::cout << "  outgoing arcs";
    for (auto a : net.outarcs(u)) {
        std::cout << "    arc:" << a << " from:" << net.src(a) << std::endl;
    }
}
for (auto a = 0; a < net.n_arcs(); a++) {
    std::cout << "arc:" << a
              << " source:" << net.src(a)
              << " sink:" << net.snk(a)
              << " wait:" << (net.src(a) == net.snk(a))
              << std::endl;
}

Solving the Shortest Path Problem

The basic function to solve the shortest path problem is Net::shortest_path. This function is called with four arguments: the basic objective function basecosts ( $\cbase(a), a\in\Acur$ ), the augmented costs augcosts ( $\caug, a \in \Acur$ ) and two output parameters nnodes and narcs. The two objective functions are arrays of weight values for each existing arc (i.e. the weights of an arc $a \in \Acur$ are basecosts[a] and augcosts[a], respectively). The function returns either Result::Solved, if the shortest path problem in $\Gt$ has been solved successfully, or Result::Expanded if the stored subgraph was too small and has been enlarged.

The interpretation of the variables nnodes and narcs depends on the return value of Net::shortest_path. If the return value is Result::Solved, they contain the number of nodes and arcs in the shortest path. The shortest path itself can be queried using Net::get_path.

If the return value is Result::Expanded, the shortest path problem could not be solved. In this case the graph $\Gcur$ has been enlarged by adding further nodes and arcs. The number of new nodes and arcs is returned in the two variables nnodes and narcs.

In order to solve the shortest path problem, the user must call Net::shortest_path in loop as long as the return value is Result::Expanded. In that case the arrays containing the objective function basecosts and augcosts must be enlarged by the user to contain the values for the new arcs. Then the shortest path problem must be resolved.

If the problem has been solved, the shortest path as well as its length can be retrieved using the Net::get_path method.

The following example demonstrates how to solve the shortest path problem.

std::vector<double> basecosts, augcost;
compute_costs(basecosts, augcosts); // compute the objective function
while (1) {
  index_type nnodes, narcs;
  if (net.shortest_path(basecosts, augcosts, nnodes, narcs) == Net::Result::Solved) break;
  update_costs(basecosts, augcosts, nnodes, narcs); // enlarge objective
}
// get the shortest path
std::vector<index_type> path;
double len = net.get_path(path);
...

Member Enumeration Documentation

◆ Result

enum Dyng::Net::Result

strong

Return states of the shortest path computation.

See also: Net::shortest_path

Enumerator
Solved	The shortest path problem has been solved.
Expanded	The shortest path problem has not been solved because the algorithm detected that the time expansion is too small.

Constructor & Destructor Documentation

◆ Net()

Dyng::Net::Net ( )

Constructor.

Exceptions

std::bad_alloc

Member Function Documentation

◆ add_basearc()

BaseArc Dyng::Net::add_basearc	(	BaseNode	bsrc,
		BaseNode	bsnk
	)

Add an arc to the base graph.

Parameters

bsrc	the source base node
bsnk	the sink base node

Precondition: bsrc and bsnk must be valid node numbers

Returns: number of the new arc

Exceptions

std::bad_alloc
std::invalid_argument	a precondition is violated

◆ add_basenode()

BaseNode Dyng::Net::add_basenode ( Group group )

Add a base node to the network.

Parameters

group the group number of the new node

Precondition: group must be a valid group number

Returns: the number of the new node

Exceptions

std::bad_alloc
std::invalid_argument	a precondition is violated

◆ add_group()

Group Dyng::Net::add_group ( )

Add one group to the base graph.

Returns: the number of the new group

Exceptions

std::bad_alloc

◆ add_groups()

Group Dyng::Net::add_groups ( index_type ngroups )

Add several groups to the base graph.

The new groups are numbered in ascending order, the number of the first group is returned.

Parameters

ngroups the number of new groups to be added.

Precondition: ngroups > 0

Returns: The new groups are numbered $\{i,i+1,\ldots,i+\mbox{ngroups} - 1\}$ , where is the returned number.

Exceptions

std::bad_alloc

◆ add_runningtime()

void Dyng::Net::add_runningtime	(	BaseArc	arc,
		RunTime	running_time
	)

Add one possible running time to a base arc.

Parameters

arc	the base arc
running_time	a possible running time

Precondition: arc must be a valid arc number; running_time >= 0; running_time == 1 if the arc is a loop

Exceptions

std::bad_alloc
std::invalid_argument	a precondition is violated

◆ add_runningtimes() [1/2]

void Dyng::Net::add_runningtimes	(	BaseArc	arc,
		std::size_t	ntimes,
		const RunTime	running_times[]
	)

Add several possible running times to a base arc.

Parameters

arc	the base arc
ntimes	the number of new running times
running_times	an array of new running times

Precondition: arc must be a valid arc number; ntimes >= 0; running_times[i] >= 0 for all i; running_times[i] == 1 for all i if arc is a loop; the array running_times must contain at least ntimes values, otherwise the behaviour is undefined

Exceptions

std::bad_alloc
std::invalid_argument	a precondition is violated

◆ add_runningtimes() [2/2]

void Dyng::Net::add_runningtimes	(	BaseArc	arc,
		const std::vector< RunTime > &	running_times
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ arc()

Arc Dyng::Net::arc	(	Node	src,
		Node	snk
	)		const

Returns the id of an arc in the time expansion.

The arc is identified by its source and sink nodes.

See also: node; find_arc

Parameters

src	the id of the source node in the time expansion
snk	the id of the sink node in the time expansion

Precondition: net must be initialized; src and snk must be valid node ids.

Returns: the id of the arc if exists

Return values

<tt>noarc</tt> if the arc does not exist

Exceptions

std::invalid_argument a precondition is violated

◆ base_arc()

BaseArc Dyng::Net::base_arc	(	BaseNode	bsrc,
		BaseNode	bsnk
	)		const

Returns the id of a base arc.

The arc is identified by its source and sink nodes.

See also: node; find_arc

Parameters

bsrc	the id of the source node
bsnk	the id of the sink node

Precondition: bsrc and bsnk must be valid node ids.

Returns: the id of the arc if exists

Return values

<tt>noarc</tt> if the arc does not exist

Exceptions

std::invalid_argument a precondition is violated

◆ base_firstin()

BaseArc Dyng::Net::base_firstin ( BaseNode bnode ) const

Return first incoming arc of a node in the base graph.

Parameters

bnode the base node

Precondition: bnode must be a valid node number

Returns: the number of the incoming first arc or noarc if no such arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ base_firstout()

BaseArc Dyng::Net::base_firstout ( BaseNode bnode ) const

Return first outgoing arc of a node in the base graph.

Parameters

bnode the base node

Precondition: bnode must be a valid node number

Returns: the number of the outgoing first arc or noarc if no such arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ base_group()

Group Dyng::Net::base_group ( BaseNode bnode ) const

Returns the index of the group of a base node.

Parameters

bnode the ID of the base node

Precondition: bnode must be a valid

Returns: the group of the base node

Exceptions

std::invalid_argument if bnode is invalid

◆ base_groupidx()

index_type Dyng::Net::base_groupidx ( BaseNode bnode ) const

Returns the number of the node in its group.

The bases nodes contained in the same group are numbered in the order they have been added to the network. This function returns this index.

Parameters

bnode the ID of the base node

Precondition: bnode must be valid

Returns: the number of the base node in its group

Exceptions

std::invalid_argument if bnode is invalid

◆ base_nextin()

BaseArc Dyng::Net::base_nextin ( BaseArc arc ) const

Return the next incoming base arc.

The next incoming arc is an arc with the same sink node.

Parameters

arc	the base arc

Precondition: arc must be a valid arc number

Returns: the number of the next incoming arc, noarc if no such arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ base_nextout()

BaseArc Dyng::Net::base_nextout ( BaseArc arc ) const

Return the next outgoing base arc.

The next outgoing arc is an arc with the same source node.

Parameters

arc	the base arc

Precondition: arc must be a valid arc number

Returns: the number of the next outgoing arc, noarc if no such arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ base_snk()

BaseNode Dyng::Net::base_snk ( BaseArc arc ) const

Return the number of the sink base node of a base arc.

Parameters

arc	the base arc

Precondition: arc must be a valid arc number

Returns: on success, the number of the sink node

Exceptions

std::invalid_argument a precondition is violated

◆ base_src()

BaseNode Dyng::Net::base_src ( BaseArc arc ) const

Return the number of the source base node of a base arc.

Parameters

arc	the base arc

Precondition: arc must be a valid arc number

Returns: on success, the number of the source node

Exceptions

std::invalid_argument a precondition is violated

◆ base_waitnode()

bool Dyng::Net::base_waitnode ( BaseNode bnode ) const

Returns true if the base node is a wait node.

Parameters

bnode the ID of the base node

Precondition: bnode must be valid

Returns: true iff the base node is a wait node

Exceptions

std::invalid_argument if bnode is invalid

◆ basenode()

BaseNode Dyng::Net::basenode ( Node node ) const

Returns the id of the base node associated with a node.

See also: node; time

Parameters

node	the id of the node

Precondition: net must be initialized; node must be a valid

Returns: the id of the associated base node

Exceptions

std::invalid_argument a precondition is violated

◆ basenode_mintime()

Time Dyng::Net::basenode_mintime ( BaseNode bnode ) const

Return the minimal possible time associated with a basenode.

See also: basenode

Parameters

bnode the id of the base node

Precondition: net must be initialized; bnode must be a valid base node id

Returns: the minimal time associated with the base node

Exceptions

std::invalid_argument a precondition is violated

◆ find_arc()

Arc Dyng::Net::find_arc	(	BaseNode	bsrc,
		Time	srctime,
		BaseNode	bsnk,
		Time	snktime
	)		const

Returns the id of an arc in the time expansion.

The arc is specified by id and time index of its source and sink Nodes.

See also: arc

Parameters

bsrc	the id of the source base node
srctime	the time of the source node
bsnk	the id of the sink base node
snktime	the time of the sink node

Precondition: net must be initialized

Returns: the id of the arc in the time expansion

Return values

nonode	if source or sink node are not (yet) contained in the network
noarc	if the arc is not contained in the time expansion. Note that if DYNG_NOARC is returned then both nodes do exist, so the requested arc will never be contained in the time expansion.

Exceptions

std::invalid_argument a precondition is violated

◆ firstin()

Arc Dyng::Net::firstin ( Node node ) const

Returns the id of the first incoming arc in the time expansion.

See also: firstout; nextit

Parameters

node	the id of the node

Precondition: net must be initialized; node must be a valid node id

Returns: the id if the first incoming arc

Return values

<tt>noarc</tt> if no incoming arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ firstout()

Arc Dyng::Net::firstout ( Node node ) const

Returns the id of the first outgoing arc in the time expansion.

See also: firstin; nextout

Parameters

node	the id of the node

Precondition: net must be initialized; node must be a valid node id

Returns: the id if the first outgoing arc

Return values

<tt>noarc</tt> if no outgoing arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ force_active()

void Dyng::Net::force_active	(	Group	grp,
		Time	time_active
	)

Forces the active subgraph to contain certain arcs.

All arcs leaving a base node of the given group up to a certain time index are forced to be contained in the active subgraph.

The graph will not be expanded immediately but at the next shortest path computation. Note that this might enlarge the graph at the next iteration.

Parameters

grp	the group from which the new active arcs will leave
time	first time index not contained in the active subgraph

◆ get_new_active() [1/2]

void Dyng::Net::get_new_active ( Arc active[] ) const

Return the list of newly activated arcs.

These are the arcs that have become active in the last expansion. The number of new active arcs can be queried using get_num_new_active.

◆ get_new_active() [2/2]

void Dyng::Net::get_new_active ( std::vector< Arc > & active ) const

Return the list of newly activated arcs.

These are the arcs that have become active in the last expansion.

◆ get_num_new_active()

index_type Dyng::Net::get_num_new_active ( ) const

Return the number of newly activated arcs.

These are the arcs that have become active in the last expansion.

◆ get_path() [1/2]

double Dyng::Net::get_path ( Arc path[] ) const

Returns the latest computed shortest path.

See also: shortest_path

Parameters

[out] path an array containing the arcs of the path in order

Returns: the costs of the shortest path, i.e., the sum of the arc weights

Precondition: net must be initialized; path must have at least the size of the path length (the path length has been returned by shortest_path).

Exceptions

DyngError if no path is available (called shortest_path?)

◆ get_path() [2/2]

double Dyng::Net::get_path ( std::vector< Arc > & path ) const

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Exceptions

std::bad_alloc

◆ get_pathlen()

index_type Dyng::Net::get_pathlen ( ) const

Return the length of the shortest path.

Returns: the length of the shortest path

Exceptions

DyngError if no path is available (called shortest path?)

◆ group_mintime()

Time Dyng::Net::group_mintime ( Group group ) const

Return the minimal possible time associated with a group.

See also: basenode_mintime

Parameters

grp	the id of the group

Precondition: net must be initialized; grp must be a valid group id

Returns: the minimal time associated with a group

Exceptions

std::invalid_argument a precondition is violated

◆ init()

void Dyng::Net::init ( )

Initializes the time expansion.

This function initializes the necessary data structures for the time expansion. After calling this function, the base graph must not modified anymore, and each attempt to do so will raise an error.

Precondition

the group graph must be a path
the base graph must have a unique source
the each two nodes of successive groups must be connected
each non-wait arc must have at least one running time

Exceptions

DyngError if the base graph does not satisfy all conditions

◆ isactive()

bool Dyng::Net::isactive ( Arc arc ) const

Returns true iff the given arc is contained in the active subgraph.

Parameters

arc	the id of the arc

Precondition: arc must be a valid arc id

Returns: true iff the arc is active, false otherwise

Exceptions

std::invalid_argument a precondition is violated

◆ n_arcs()

index_type Dyng::Net::n_arcs ( ) const

Returns the number of arcs in the time expansion.

Precondition: net must be initialized

Returns: the number of arcs in the time expansion

◆ n_basearcs()

index_type Dyng::Net::n_basearcs ( ) const

Return the number of base arcs.

Returns: number of base arcs

◆ n_basenodes()

index_type Dyng::Net::n_basenodes ( ) const

Return the number of base nodes.

Returns: the number of base nodes

◆ n_groups()

index_type Dyng::Net::n_groups ( ) const

Return the number of groups in the base graph.

Returns: the number of groups in the base graph

◆ n_nodes()

index_type Dyng::Net::n_nodes ( ) const

Returns the number of nodes in the time expansion.

Precondition: net must be initialized

Returns: the number of nodes in the time expansion

◆ nextin()

Arc Dyng::Net::nextin ( Arc arc ) const

Returns the id of the next incoming arc in the time expansion.

The next incoming arc is an arc with the same sink node.

See also: firstin; nextout

Parameters

arc	the id of the arc

Precondition: net must be initialized; arc must be a valid arc id

Returns: the id if the next incoming arc

Return values

<tt>noarc</tt> if no next incoming arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ nextout()

Arc Dyng::Net::nextout ( Arc arc ) const

Returns the id of the next outgoing arc in the time expansion.

The next outgoing arc is an arc with the same source node.

See also: firstout; nextin

Parameters

arc	the id of the arc

Precondition: net must be initialized; arc must be a valid arc id

Returns: the id if the next outgoing arc

Return values

<tt>noarc</tt> if no next outgoing arc exists

Exceptions

std::invalid_argument a precondition is violated

◆ node()

Node Dyng::Net::node	(	BaseNode	bnode,
		Time	time
	)		const

Returns the id of a node in the time expansion.

The node is identified by its base node id and time index.

See also: arc

Parameters

bnode	the id of the base node
time	the time index of the node

Precondition: net must be initialized; time must be nonnegative

Returns: the id of the node if exists

Return values

nonode if the node does not (yet) exist

Exceptions

std::invalid_argument a precondition is violated

◆ shortest_path() [1/4]

Result Dyng::Net::shortest_path	(	const double	basecosts[],
		const double	augcosts[],
		index_type &	nnodes,
		index_type &	narcs
	)

Solve the shortest path problem.

The shortest path problem is solved w.r.t. the cost values given in basecosts and augcosts. If an arc is contained in the active subgraph then its weight is basecosts[arc] + augcosts[arc], otherwise it is basecosts[arc]. The solution may fail if the resulting path is not contained in the active subgraph. In this case the time expansion is enlarged and nnodes and narcs are set to the number of new node and arcs, respectively, and Result::Expanded is returned. The shortest path problem must be solved again with enlarged cost vectors. If the resulting path is contained in the active subgraph then the solution succeeds. Then narcs is set to the number of arcs in the shortest path and Result::Solved is returned.

The computed shortest path can be obtained by Net::get_path.

Parameters

[in]	basecosts	the basic objective function
[in]	augcosts	the augmented cost terms
[out]	nnodes	the number of newly generated nodes
[out]	narcs	the number of newly generated arcs or the length of the shortest path

Return values

Result::Solved	if the shortest path problem could be solved
Result::Expanded	if the time expansion must be expanded

Exceptions

DyngError if the time expansion has not been initialized

◆ shortest_path() [2/4]

Result Dyng::Net::shortest_path	(	const std::vector< double > &	basecosts,
		const std::vector< double > &	augcosts,
		index_type &	nnodes,
		index_type &	narcs
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ shortest_path() [3/4]

Result Dyng::Net::shortest_path	(	const double	basecosts[],
		const double	augcosts[]
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ shortest_path() [4/4]

Result Dyng::Net::shortest_path	(	const std::vector< double > &	basecosts,
		const std::vector< double > &	augcosts
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ snk()

Node Dyng::Net::snk ( Arc arc ) const

Returns the id of the sink node of an arc in the time expansion.

See also: arc

Parameters

arc	the id of the arc

Precondition: net must be initialized; arc must be a valid arc id

Returns: the id of the sink node in the time expansion

Exceptions

std::invalid_argument a precondition is violated

◆ src()

Node Dyng::Net::src ( Arc arc ) const

Returns the id of the source node of an arc in the time expansion.

See also: arc

Parameters

arc	the id of the arc

Precondition: net must be initialized; arc must be a valid arc id

Returns: the id of the source node in the time expansion

Exceptions

std::invalid_argument a precondition is violated

◆ time()

Time Dyng::Net::time ( Node node ) const

Returns the time index associated with a node in the time expansion.

See also: node; basenode

Parameters

node	the id of the node

Precondition: net must be initialized; node must be a valid

Returns: the time associated with the node

Exceptions

std::invalid_argument a precondition is violated

The documentation for this class was generated from the following file:

include/dyng/Net.hxx

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Theoretical Background

Time expanded networks

The shortest path problem in time expanded networks

Dynamic Graph Generation

Using the class Net

Defining the Base Graph

Working with the Time Expanded Network

Solving the Shortest Path Problem

Member Enumeration Documentation

◆ Result

Constructor & Destructor Documentation

◆ Net()

Member Function Documentation

◆ add_basearc()

◆ add_basenode()

◆ add_group()

◆ add_groups()

◆ add_runningtime()

◆ add_runningtimes() [1/2]

◆ add_runningtimes() [2/2]

◆ arc()

◆ base_arc()

◆ base_firstin()

◆ base_firstout()

◆ base_group()

◆ base_groupidx()

◆ base_nextin()

◆ base_nextout()

◆ base_snk()

◆ base_src()

◆ base_waitnode()

◆ basenode()

◆ basenode_mintime()

◆ find_arc()

◆ firstin()

◆ firstout()

◆ force_active()

◆ get_new_active() [1/2]

◆ get_new_active() [2/2]

◆ get_num_new_active()

◆ get_path() [1/2]

◆ get_path() [2/2]

◆ get_pathlen()

◆ group_mintime()

◆ init()

◆ isactive()

◆ n_arcs()

◆ n_basearcs()

◆ n_basenodes()

◆ n_groups()

◆ n_nodes()

◆ nextin()

◆ nextout()

◆ node()

◆ shortest_path() [1/4]

◆ shortest_path() [2/4]

◆ shortest_path() [3/4]

◆ shortest_path() [4/4]

◆ snk()

◆ src()

◆ time()