Как построить матрицу двунаправленности DAG? - PullRequest
Новая
       23

Как построить матрицу двунаправленности DAG?

2 голосов
/ 23 апреля 2009

Для двудольного графа вы можете заменить матрицу смежности на то, что называется матрицей двунаправленности :

Матрица смежности A двудольного графа, части которого имеют r и s вершины, имеет вид 

    A =  O  B
         B<sup>T</sup> O

где B - матрица r × s, а O - матрица со всеми нулями. Ясно, что матрица B однозначно представляет двудольные графы, и ее обычно называют матрицей двунаправленности.

Теперь DAG - это двудольный граф, например, вы можете топологически отсортировать его и иметь множества U и V, являющиеся узлами, которые находятся на нечетном или четном топологическом уровне соответственно.

Это означает, что для группы обеспечения доступности баз данных с n узлами мне нужна только (n / 2) 2 матрица (в среднем) вместо n 2 матрицы. Проблема в том, что я не знаю, как это построить. Есть намеки?

Ответы [ 4 ]

10 голосов
/ 28 апреля 2009

Я полагаю, что вы не можете построить матрицу двунаправленности для DAG, потому что не каждый DAG является двудольным графом.

Вот простой пример: рассмотрим ориентированный граф с 3 вершинами и обозначим их как A, B и C. Ребра соединяют A с B, B с C и A с C. Граф, очевидно, является DAG, поскольку оно направлено и циклов нет (A-> B-> C <-A - это не цикл). Тем не менее, график не является двудольным: нет никакого способа разделить A, B и C на два непересекающихся множества, где нет ребер между вершинами в одном наборе. </p>

Вывод состоит в том, что существуют графы, которые являются DAG, но не двудольными, поэтому не каждый DAG является двудольным.

Обратите внимание, что тот факт, что вы можете топологически отсортировать DAG и разделить вершины на два непересекающихся множества, не означает, что между вершинами одного и того же множества нет ребер.

5 голосов
/ 28 апреля 2009

Кажется, что матрица двунаправленности B для матрицы A может быть построена только в том случае, если график не ориентирован.

На основании примера из Википедии:

alt text

Матрицы смежности для этого DAG должны быть: 

Blue -> Red
B = 1 1 0 0
    0 0 1 0
    0 0 0 0
    0 0 0 0
    0 0 0 1

Red -> Blue
C = 0 1 0 0 0
    0 1 0 0 0
    0 0 1 1 1
    0 0 0 0 0

Как вы можете видеть, C не является транспонированной для B. Невозможно создать матрицу A, как описано. Тем не менее, вы можете создать матрицу A следующим образом: 

A = 0 B
    C 0

Для этого потребуется 2 * (n / 2) ^ 2 пробела, что все же лучше, чем n ^ 2.

Чтобы построить матрицы B и C, вам просто нужно зациклить каждый узел в U и V (соответственно), чтобы определить исходящие ребра.

0 голосов
/ 04 мая 2009

Обе указанные симметрии вашей матрицы двунаправленности A, и ваше намерение использовать топологическую сортировку для выделения двудольной структуры в графе - укажите, что вы на самом деле ссылаетесь на косвенную , ациклический, граф - т.е. дерево. (Существо симметричное явно говорит о том, что если у вас есть ребро от x до y, у вас должно быть ребро от y до x - следовательно, направленность становится бессмысленной).

Предполагая, что это действительно ваше намерение:

(1) Как и для любого косвенного графа, вы можете немедленно рассчитать примерно 0,5 * (n ^ 2) (точно: n (n-1) / 2), сохранив только верхний треугольник матрицы смежности.

(2) Предположим, вы должны хранить только B.

Сначала вы должны идентифицировать непересекающиеся подмножества, скажем, R & S, каждое из которых не имеет внутренних ребер. Топологическая сортировка является вероятным вариантом - в дереве она сводится к выбору корня и маркировке вершин, находясь на четных / нечетных уровнях выше корня (в отличие от общих визуализаций , я предпочитаю думать о дереве как на самом деле растет выше его корень ..). Из вашего вопроса я понимаю, что вам это удобно, поэтому я даже не буду давать псевдокод.

Затем вам нужно пометить вершины так, чтобы все вершины R были первыми, а все вершины S следовали: 

Allocate NewLabels(r + s);
CurRSize = 0;
CurSSize = 0;
for each (TreeLevel)
    if #CurLevel is even  // append to R vertices
       NewLabels(CurRSize : CurRsize + CurLevelSize - 1) = CurLevelVertexNums;
       CurRSize += CurLevelSize;
    else // append to S vertices
       NewLabels(r+s - (CurSSize+CurLevelSize) : r+s - (CurSSize + 1) = CurLevelVertexNums;
       CurSSize += CurLevelSize;

(сразу приходят на ум некоторые оптимизации, но они здесь не важны).

Затем вы можете последовательно сканировать ребра графа и сохранять их как записи в матрице r x s B, индексированные по новым меткам вершин: 

Allocate B(r,s);
Zero(B);
for each (edge = x<-->y)
   i = NewLabels(x);
   j = NewLabels(y) - r; // must adjust, to index just B
   B(i,j) = 1;

НТН.

0 голосов
/ 03 мая 2009

Следующий код создаст матрицу двунаправленности заданной матрицы смежности, если она двудольная (только двудольные графы имеют матрицу двунаправленности.) Если заданный граф не является двухсторонним, метод GetBiadjacencyMatrix () возвращает ноль.

График предоставленной выборки, включая матрицу двунаправленности http://www.freeimagehosting.net/image.php?10e9b6a746.jpg

Не можете увидеть изображение? Нажмите здесь 

public class Matrix
{
    private void Usage()
    {
        int[,] AdjacencyMatrix = new int[,] { 
                                        {0, 1, 1, 0, 0, 0, 0, 0, 0},
                                        {1, 0, 0, 1, 0, 0, 0, 0, 0},
                                        {1, 0, 0, 1, 0, 0, 0, 0, 0},
                                        {0, 1, 1, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 1, 0, 1, 1, 1, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 0},
                                        {0, 0, 0, 0, 1, 0, 0, 0, 1},
                                        {0, 0, 0, 0, 0, 0, 0, 1, 0}
                                       };

        int[,] BiadjacencyMatrix = GetBiadjacencyMatrix(AdjacencyMatrix);
    }

    public static int[,] GetBiadjacencyMatrix(int[,] adjacencyMatrix)
    {
        int NodeCount = adjacencyMatrix.GetLength(0);

        NodeInfo[] Nodes = new NodeInfo[NodeCount];
        for (int c = NodeCount - 1; c >= 0; c--)
            Nodes[c] = new NodeInfo(c);

        if (ColorNode(adjacencyMatrix, Nodes, 0, 1, -1) != NodeCount)
            return null; // Given graph is not bipatite.

        int Part1Count = 0, Part2Count = 0;
        foreach (NodeInfo Node in Nodes)
            Node.IndexInPart = Node.PartID == 1 ? Part1Count++ : Part2Count++;

        int[,] ToReturn = new int[Part1Count, Part2Count];
        foreach (NodeInfo NodeInPart1 in Nodes)
            if (NodeInPart1.PartID == 1)
                foreach (NodeInfo NodeInPart2 in Nodes)
                    if (NodeInPart2.PartID == 2)
                        ToReturn[NodeInPart1.IndexInPart, NodeInPart2.IndexInPart]
                            = adjacencyMatrix[NodeInPart1.IndexInGraph, NodeInPart2.IndexInGraph];

        return ToReturn;
    }

    private static int ColorNode(int[,] adjacencyMatrix, NodeInfo[] nodes, int currentNode, int currentPart, int parentNode)
    {
        if (nodes[currentNode].PartID != -1) 
            return nodes[currentNode].PartID != currentPart ? -1 : 0;
        int ToReturn = 1;
        nodes[currentNode].PartID = currentPart;
        for (int c = nodes.Length - 1; c >= 0; c--)
            if (adjacencyMatrix[currentNode, c] != 0 && c != parentNode)
            {
                int More = ColorNode(adjacencyMatrix, nodes, c, currentPart == 1 ? 2 : 1, currentNode);
                if (More == -1) return -1;
                ToReturn += More;
            }
        return ToReturn;
    }
}


public class NodeInfo
{
    private int _IndexInGraph;
    private int _PartID;
    private int _IndexInPart;
    private bool _IsVisited;

    public NodeInfo(int indexInGraph)
    {
        _IndexInGraph = indexInGraph;
        _PartID = -1;
        _IndexInPart = -1;
        _IsVisited = false;
    }

    public int IndexInGraph
    {
        get { return _IndexInGraph; }
        set { _IndexInGraph = value; }
    }

    public int PartID
    {
        get { return _PartID; }
        set { _PartID = value; }
    }

    public int IndexInPart
    {
        get { return _IndexInPart; }
        set { _IndexInPart = value; }
    }

    public bool IsVisited
    {
        get { return _IsVisited; }
        set { _IsVisited = value; }
    }
}
...