Misplaced Pages

#935064

57-636: Ubuntu Software Center , or simply Software Center , is a discontinued high-level graphical front end for the APT / dpkg package management system . It is free software written in Python , PyGTK / PyGObject based on GTK . The program was created for adding and managing repositories , as well as Ubuntu Personal Package Archives (PPA) and on Ubuntu, the Ubuntu Software Center also allowed users to purchase commercial applications. Development

114-483: A k − 1 {\displaystyle a_{k-1}} is the total number of processed vertices after step ⁠ k − 1 {\displaystyle k-1} ⁠ . This procedure repeats until there are no vertices left to process, hence ∑ i = 0 p − 1 | Q i D + 1 | = 0 {\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0} . Below

171-413: A prefix sum is calculated over the sizes of Q 0 1 , … , Q p − 1 1 {\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}} . So, each step, there are ∑ i = 0 p − 1 | Q i | {\textstyle \sum _{i=0}^{p-1}|Q_{i}|} vertices added to

228-472: A queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing . An alternative algorithm for topological sorting is based on depth-first search . The algorithm loops through each node of

285-404: A self-evident name and an interface anyone can use. There should be a coordinated system for developers and enthusiasts to improve the usefulness of descriptions and other metadata for software packages. The software updates interface should be honed to maximize the voluntary installation of updates across the millions of computers on which Ubuntu is installed. And projects and vendors whose software

342-400: A set S; at least one such node must exist in a non-empty (finite) acyclic graph. Then: If the graph is a DAG , a solution will be contained in the list L (although the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sort is impossible. Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or

399-440: A specific file, or to list all files included in a package on remote repositories. Topological sorting In computer science , a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v , u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and

456-543: A topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG . If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it

513-413: Is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time . Topological sorting has many applications, especially in ranking problems such as feedback arc set . Topological sorting is also possible when the DAG has disconnected components . The canonical application of topological sorting

570-695: Is a high level, single program, multiple data pseudo-code overview of this algorithm. Note that the prefix sum for the local offsets a k − 1 + ∑ i = 0 j − 1 | Q i k | , … , a k − 1 + ( ∑ i = 0 j | Q i k | ) − 1 {\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1} can be efficiently calculated in parallel. The communication cost depends heavily on

627-419: Is a partial order in which, for every two objects x and y in the set, either x  ≤  y or y  ≤  x . Total orders are familiar in computer science as the comparison operators needed to perform comparison sorting algorithms. For finite sets, total orders may be identified with linear sequences of objects, where the "≤" relation is true whenever the first object precedes the second object in

SECTION 10

#1732772328936

684-553: Is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP-hardness of the Hamiltonian path problem for more general directed graphs (i.e., cyclic directed graphs). Topological orderings are also closely related to

741-455: Is in scheduling a sequence of jobs or tasks based on their dependencies . The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs. A closely-related application of topological sorting algorithms

798-460: Is of " important " priority in all current Debian releases, and is therefore included in a default Debian installation. APT can be considered a front end to dpkg , friendlier than the older dselect front end. While dpkg performs actions on individual packages, APT manages relations (especially dependencies) between them, as well as sourcing and management of higher-level versioning decisions (release tracking and version pinning ). APT

855-479: Is often hailed as one of Debian's best features, which Debian developers attribute to the strict quality controls in Debian's policy. A major feature of APT is the way it calls dpkg — it does topological sorting of the list of packages to be installed or removed and calls dpkg in the best possible sequence. In some cases, it utilizes the --force options of dpkg . However, it only does this when it

912-624: Is packaged for Ubuntu should be encouraged to provide links to their software's presence in the Software Store, instead of command-line installation instructions." Canonical introduced the Software Center gradually, starting with Ubuntu 9.10 ( Karmic Koala ) with complete functionality expected by Ubuntu 11.10, in October 2011. By May 2011, the plan had mostly been completed: In August 2015 Chris Hoffman of PC World criticized

969-412: Is the idea of the following algorithm. In the following, it is assumed that the graph partition is stored on p processing elements (PE), which are labeled 0 , … , p − 1 {\displaystyle 0,\dots ,p-1} . Each PE i initializes a set of local vertices Q i 1 {\displaystyle Q_{i}^{1}} with indegree 0, where

1026-554: Is the one described by Cormen et al. (2001) ; it seems to have been first described in print by Tarjan in 1976. On a parallel random-access machine , a topological ordering can be constructed in O ((log n ) ) time using a polynomial number of processors, putting the problem into the complexity class NC . One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes

1083-514: Is to define a DAG that has a vertex for every object in the partially ordered set, and an edge xy for every pair of objects for which x  ≤  y . An alternative way of doing this is to use the transitive reduction of the partial ordering; in general, this produces DAGs with fewer edges, but the reachability relation in these DAGs is still the same partial order. By using these constructions, one can use topological ordering algorithms to find linear extensions of partial orders. By definition,

1140-419: Is unable to calculate how to avoid the reason dpkg requires the action to be forced. The user indicates one or more packages to be installed. Each package name is phrased as just the name portion of the package, not a fully qualified filename (for instance, in a Debian system, libc6 would be the argument provided, not libc6_1.9.6-2.deb ). Notably, APT automatically gets and installs packages upon which

1197-683: The -d option (i.e. a hard disk or a USB keydrive). The Debian CDs available for download contain Debian repositories. This allows non-networked machines to be upgraded. One can also use apt-zip . Problems may appear when several sources offer the same package(s). Systems that have such possibly conflicting sources can use APT pinning to control which sources should be preferred. The APT pinning feature allows users to force APT to choose particular versions of packages which may be available in different versions from different repositories. This allows administrators to ensure that packages are not upgraded to versions which may conflict with other packages on

SECTION 20

#1732772328936

1254-535: The apt_preferences mechanism allows the user to create an alternative installation policy for individual packages. The user can specify packages using a POSIX regular expression . APT searches its cached list of packages and lists the dependencies that must be installed or updated. APT retrieves, configures and installs the dependencies automatically. Triggers are the treatment of deferred actions. Usage modes of apt and apt-get that facilitate updating installed packages include: /etc/apt contains

1311-414: The longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering. An algorithm for parallel topological sorting on distributed memory machines parallelizes the algorithm of Kahn for a DAG G = ( V , E ) {\displaystyle G=(V,E)} . On a high level, the algorithm of Kahn repeatedly removes

1368-541: The APT configuration folders and files. apt-config is the APT Configuration Query program. apt-config dump shows the configuration. APT relies on the concept of repositories in order to find software and resolve dependencies. For APT, a repository is a directory containing packages along with an index file. This can be specified as a networked or CD-ROM location. As of 14 August 2021,

1425-422: The DAG, and defining x  ≤  y to be true, for any two vertices x and y , whenever there exists a directed path from x to y ; that is, whenever y is reachable from x . With these definitions, a topological ordering of the DAG is the same thing as a linear extension of this partial order. Conversely, any partial ordering may be defined as the reachability relation in a DAG. One way of doing this

1482-415: The Debian project keeps a central repository of over 50,000 software packages ready for download and installation. Any number of additional repositories can be added to APT's sources.list configuration file ( /etc/apt/sources.list ) and then be queried by APT. Graphical front ends often allow modifying sources.list more simply ( apt-setup ). Once a package repository has been specified (like during

1539-406: The algorithm adds node n , we are guaranteed that all nodes that depend on n are already in the output list L: they were added to L either by the recursive call to visit() that ended before the call to visit n , or by a call to visit() that started even before the call to visit n . Since each edge and node is visited once, the algorithm runs in linear time. This depth-first-search-based algorithm

1596-611: The application would be replaced by GNOME Software in Ubuntu 16.04 LTS . Other examples of a high-level graphical front end for APT : APT (Package Manager) APT is a collection of tools distributed in a package named apt . A significant part of APT is defined in a C++ library of functions; APT also includes command-line programs for dealing with packages, which use the library. Three such programs are apt , apt-get and apt-cache . They are commonly used in examples because they are simple and ubiquitous. The apt package

1653-426: The application, indicating that Canonical was not maintaining it properly while work on the replacement application was being pursued. In particular, he noted that paid applications were not being supported properly and that Canonical had not informed developers of this. The application still works for installing and managing free software applications. In November 2015 Canonical announced that development would end and

1710-580: The basic Add/Remove Applications or with the Synaptic Package Manager . The Software Updater provided updating for installed packages and Computer Janitor cleaned up packages that were no longer needed. The Software Sources application allowed user selection of the package download location. Ubuntu developers set as a goal: "... there should be one obvious mechanism for installing, removing, and updating software in Ubuntu, with

1767-437: The concept of a linear extension of a partial order in mathematics. A partially ordered set is just a set of objects together with a definition of the "≤" inequality relation, satisfying the axioms of reflexivity ( x  ≤  x ), antisymmetry (if x  ≤  y and y  ≤  x then x  =  y ) and transitivity (if x  ≤  y and y  ≤  z , then x  ≤  z ). A total order

Ubuntu Software Center - Misplaced Pages Continue

1824-438: The dependencies of packages being installed or upgraded, ask the administrator if packages recommended or suggested by newly installed packages should be installed too, automatically install dependencies and perform other operations on the system such as removing obsolete files and packages. The original effort that led to the apt-get program was the dselect replacement project known by its codename Deity . This project

1881-400: The edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited . A topological ordering is possible if and only if the graph has no directed cycles , that is, if it

1938-413: The given graph partition. As for runtime, on a CRCW-PRAM model that allows fetch-and-decrement in constant time, this algorithm runs in O ( m + n p + D ( Δ + log ⁡ n ) ) {\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)} , where D is again the longest path in G and Δ

1995-403: The graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e., a leaf node): Each node n gets prepended to the output list L only after considering all other nodes that depend on n (all descendants of n in the graph). Specifically, when

2052-670: The indegree drops to zero, v is added to Q j 2 {\displaystyle Q_{j}^{2}} . Then the next iteration starts. In step k , PE j assigns the indices a k − 1 + ∑ i = 0 j − 1 | Q i k | , … , a k − 1 + ( ∑ i = 0 j | Q i k | ) − 1 {\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1} , where

2109-434: The indicated package depends (if necessary). This was an original distinguishing characteristic of APT-based package management systems, as it avoided installation failure due to missing dependencies, a type of dependency hell . Another distinction is the retrieval of packages from remote repositories. APT uses a location configuration file ( /etc/apt/sources.list ) to locate the desired packages, which might be available on

2166-536: The length of the overall project schedule. In computer science, applications of this type arise in instruction scheduling , ordering of formula cell evaluation when recomputing formula values in spreadsheets , logic synthesis , determining the order of compilation tasks to perform in makefiles , data serialization , and resolving symbol dependencies in linkers . It is also used to decide in which order to load tables with foreign keys in databases. The usual algorithms for topological sorting have running time linear in

2223-463: The local vertices in Q j 1 {\displaystyle Q_{j}^{1}} . These vertices in Q j 1 {\displaystyle Q_{j}^{1}} are removed, together with their corresponding outgoing edges. For each outgoing edge ( u , v ) {\displaystyle (u,v)} with endpoint v in another PE l , j ≠ l {\displaystyle l,j\neq l} ,

2280-445: The major highlights. The 'Deity' name was abandoned as the official name for the project due to concerns over the religious nature of the name. The APT name was eventually decided after considerable internal and public discussion. Ultimately the name was proposed on IRC, accepted and then finalized on the mailing lists. APT was introduced in 1998 and original test builds were circulated on IRC. The first Debian version that included it

2337-449: The maximum degree. The topological ordering can also be used to quickly compute shortest paths through a weighted directed acyclic graph. Let V be the list of vertices in such a graph, in topological order. Then the following algorithm computes the shortest path from some source vertex s to all other vertices: Equivalently: On a graph of n vertices and m edges, this algorithm takes Θ( n + m ) , i.e., linear , time. If

Ubuntu Software Center - Misplaced Pages Continue

2394-410: The message ( u , v ) {\displaystyle (u,v)} is posted to PE l . After all vertices in Q j 1 {\displaystyle Q_{j}^{1}} are removed, the posted messages are sent to their corresponding PE. Each message ( u , v ) {\displaystyle (u,v)} received updates the indegree of the local vertex v . If

2451-422: The network or a removable storage medium, for example, and retrieve them, and also obtain information about available (but not installed) packages. APT provides other command options to override decisions made by apt-get's conflict resolution system. One option is to force a particular version of a package. This can downgrade a package and render dependent software inoperable, so the user must be careful. Finally,

2508-435: The number of nodes plus the number of edges, asymptotically, O ( | V | + | E | ) . {\displaystyle O(\left|{V}\right|+\left|{E}\right|).} One of these algorithms, first described by Kahn (1962) , works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" that have no incoming edges and insert them into

2565-406: The order; a comparison sorting algorithm may be used to convert a total order into a sequence in this way. A linear extension of a partial order is a total order that is compatible with it, in the sense that, if x  ≤  y in the partial order, then x  ≤  y in the total order as well. One can define a partial ordering from any DAG by letting the set of objects be the vertices of

2622-586: The package repositories. APT was originally designed as a front end for dpkg to work with Debian's .deb packages. A version of APT modified to also work with the RPM Package Manager system was released as APT-RPM . The Fink project has ported APT to Mac OS X for some of its own package management tasks, and APT is also available in OpenSolaris . apt-file is a command, packaged separately from APT, to find which package includes

2679-403: The solution of a scheduling problem that includes a precedence graph is a valid solution to topological sort (irrespective of the number of machines), however, topological sort in itself is not enough to optimally solve a scheduling optimisation problem. Hu's algorithm is a popular method used to solve scheduling problems that require a precedence graph and involve processing times (where the goal

2736-405: The system installation), packages in that repository can be installed without specifying a source and will be kept up-to-date automatically. In addition to network repositories, compact discs and other storage media (USB keydrive, hard disks...) can be used as well, using apt-cdrom or adding file:/ URI to the source list file. apt-cdrom can specify a folder other than a CD-ROM, using

2793-430: The system, or that have not been sufficiently tested for unwelcome changes. In order to do this, the pins in APT's preferences file ( /etc/apt/preferences ) must be modified, although graphical front ends often make pinning simpler. Several other front ends to APT exist, which provide more advanced installation functions and more intuitive interfaces. These include: APT front ends can: APT front ends can list

2850-446: The topological sorting. In the first step, PE j assigns the indices ∑ i = 0 j − 1 | Q i 1 | , … , ( ∑ i = 0 j | Q i 1 | ) − 1 {\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1} to

2907-409: The upper index represents the current iteration. Since all vertices in the local sets Q 0 1 , … , Q p − 1 1 {\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}} have indegree 0, i.e., they are not adjacent, they can be given in an arbitrary order for a valid topological sorting. To assign a global index to each vertex,

SECTION 50

#1732772328936

2964-460: The vertices of indegree 0 and adds them to the topological sorting in the order in which they were removed. Since the outgoing edges of the removed vertices are also removed, there will be a new set of vertices of indegree 0, where the procedure is repeated until no vertices are left. This algorithm performs D + 1 {\displaystyle D+1} iterations, where D is the longest path in G . Each iteration can be parallelized, which

3021-473: Was Debian 2.1, released on 9 March 1999. In the end the original goal of the Deity project of replacing the dselect user interface was a failure. Work on the user interface portion of the project was abandoned (the user interface directories were removed from the concurrent versions system ) after the first public release of apt-get . The response to APT as a dselect method and a command line utility

3078-441: Was commissioned in 1997 by Brian White, the Debian release manager at the time. The first functional version of apt-get was called dpkg-get and was only intended to be a test program for the core library functions that would underpin the new user interface (UI). Much of the original development of APT was done on Internet relay chat (IRC), so records have been lost. The 'Deity creation team' mailing list archives include only

3135-435: Was ended in 2015 and in Ubuntu 16.04 LTS . It was replaced with GNOME Software . In early 2009 Ubuntu developers noted that package management within Ubuntu could be improved and consolidated. Recent releases of Ubuntu, such as Ubuntu 9.04 (Jaunty Jackalope) included five applications for package management which consumed space and other resources, as well as provide confusion to users. Applications could be downloaded using

3192-497: Was first studied in the early 1960s in the context of the PERT technique for scheduling in project management . In this application, the vertices of a graph represent the milestones of a project, and the edges represent tasks that must be performed between one milestone and another. Topological sorting forms the basis of linear-time algorithms for finding the critical path of the project, a sequence of milestones and tasks that controls

3249-472: Was so great and positive that all development efforts focused on maintaining and improving the tool. It was not until much later that several independent people built user interfaces on top of libapt-pkg . Eventually, a new team picked up the project, began to build new features and released version 0.6 of APT which introduced the Secure APT feature, using strong cryptographic signing to authenticate

#935064