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

Question

Для bipartite graph, вы можете заменить adjacency matrix с тем, что называется его biadjacency matrix:

смежности матрица А двудольный граф, части которого имеют г и х вершины имеет вид

 
    A = O B 
     BT O 

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

Теперь, ДАГ представляет собой двудольный граф, например, вы могли бы topologically sort его и множества U и V, являющиеся узлами, которые находятся на нечетном или даже топологическом уровне, соответственно.

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

Answer 1

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

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

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

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

Answer 2

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

На примере из Википедии:

матрицы смежности для этой группы 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 не транспонированная В. Безразлично Кажется возможным создать матрицу А, как описано. Тем не менее, вы можете создать матрицу А как это:

A = 0 B 
    C 0 

Это требует 2 * (п/2)^2 пространство, которое еще лучше, чем п^2.

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

Answer 3

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

Graph of the provided sample including its biadjacency matrix http://www.freeimagehosting.net/image.php?10e9b6a746.jpg

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

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; } 
    } 
} 

Answer 4

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

Если предположить, что на самом деле ваше намерение:

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

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

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

Далее вам необходимо повторно маркировать вершины так, что вершины всех г приходят первые, и вершины всех 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 х^матрицы В, индексированные по новых вершинных меток:

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; 

HTH.